LCOV - code coverage report
Current view: top level - gcc - lra-assigns.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 918 957 95.9 %
Date: 2020-04-04 11:58:09 Functions: 29 30 96.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Assign reload pseudos.
       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                 :            : /* This file's main objective is to assign hard registers to reload
      23                 :            :    pseudos.  It also tries to allocate hard registers to other
      24                 :            :    pseudos, but at a lower priority than the reload pseudos.  The pass
      25                 :            :    does not transform the RTL.
      26                 :            : 
      27                 :            :    We must allocate a hard register to every reload pseudo.  We try to
      28                 :            :    increase the chances of finding a viable allocation by assigning
      29                 :            :    the pseudos in order of fewest available hard registers first.  If
      30                 :            :    we still fail to find a hard register, we spill other (non-reload)
      31                 :            :    pseudos in order to make room.
      32                 :            : 
      33                 :            :    find_hard_regno_for finds hard registers for allocation without
      34                 :            :    spilling.  spill_for does the same with spilling.  Both functions
      35                 :            :    use a cost model to determine the most profitable choice of hard
      36                 :            :    and spill registers.
      37                 :            : 
      38                 :            :    Once we have finished allocating reload pseudos, we also try to
      39                 :            :    assign registers to other (non-reload) pseudos.  This is useful if
      40                 :            :    hard registers were freed up by the spilling just described.
      41                 :            : 
      42                 :            :    We try to assign hard registers by collecting pseudos into threads.
      43                 :            :    These threads contain reload and inheritance pseudos that are
      44                 :            :    connected by copies (move insns).  Doing this improves the chances
      45                 :            :    of pseudos in the thread getting the same hard register and, as a
      46                 :            :    result, of allowing some move insns to be deleted.
      47                 :            : 
      48                 :            :    When we assign a hard register to a pseudo, we decrease the cost of
      49                 :            :    using the same hard register for pseudos that are connected by
      50                 :            :    copies.
      51                 :            : 
      52                 :            :    If two hard registers have the same frequency-derived cost, we
      53                 :            :    prefer hard registers with higher priorities.  The mapping of
      54                 :            :    registers to priorities is controlled by the register_priority
      55                 :            :    target hook.  For example, x86-64 has a few register priorities:
      56                 :            :    hard registers with and without REX prefixes have different
      57                 :            :    priorities.  This permits us to generate smaller code as insns
      58                 :            :    without REX prefixes are shorter.
      59                 :            : 
      60                 :            :    If a few hard registers are still equally good for the assignment,
      61                 :            :    we choose the least used hard register.  It is called leveling and
      62                 :            :    may be profitable for some targets.
      63                 :            : 
      64                 :            :    Only insns with changed allocation pseudos are processed on the
      65                 :            :    next constraint pass.
      66                 :            : 
      67                 :            :    The pseudo live-ranges are used to find conflicting pseudos.
      68                 :            : 
      69                 :            :    For understanding the code, it is important to keep in mind that
      70                 :            :    inheritance, split, and reload pseudos created since last
      71                 :            :    constraint pass have regno >= lra_constraint_new_regno_start.
      72                 :            :    Inheritance and split pseudos created on any pass are in the
      73                 :            :    corresponding bitmaps.  Inheritance and split pseudos since the
      74                 :            :    last constraint pass have also the corresponding non-negative
      75                 :            :    restore_regno.  */
      76                 :            : 
      77                 :            : #include "config.h"
      78                 :            : #include "system.h"
      79                 :            : #include "coretypes.h"
      80                 :            : #include "backend.h"
      81                 :            : #include "target.h"
      82                 :            : #include "rtl.h"
      83                 :            : #include "tree.h"
      84                 :            : #include "predict.h"
      85                 :            : #include "df.h"
      86                 :            : #include "memmodel.h"
      87                 :            : #include "tm_p.h"
      88                 :            : #include "insn-config.h"
      89                 :            : #include "regs.h"
      90                 :            : #include "ira.h"
      91                 :            : #include "recog.h"
      92                 :            : #include "rtl-error.h"
      93                 :            : #include "sparseset.h"
      94                 :            : #include "lra.h"
      95                 :            : #include "lra-int.h"
      96                 :            : #include "function-abi.h"
      97                 :            : 
      98                 :            : /* Current iteration number of the pass and current iteration number
      99                 :            :    of the pass after the latest spill pass when any former reload
     100                 :            :    pseudo was spilled.  */
     101                 :            : int lra_assignment_iter;
     102                 :            : int lra_assignment_iter_after_spill;
     103                 :            : 
     104                 :            : /* Flag of spilling former reload pseudos on this pass.  */
     105                 :            : static bool former_reload_pseudo_spill_p;
     106                 :            : 
     107                 :            : /* Array containing corresponding values of function
     108                 :            :    lra_get_allocno_class.  It is used to speed up the code.  */
     109                 :            : static enum reg_class *regno_allocno_class_array;
     110                 :            : 
     111                 :            : /* Array containing lengths of pseudo live ranges.  It is used to
     112                 :            :    speed up the code.  */
     113                 :            : static int *regno_live_length;
     114                 :            : 
     115                 :            : /* Information about the thread to which a pseudo belongs.  Threads are
     116                 :            :    a set of connected reload and inheritance pseudos with the same set of
     117                 :            :    available hard registers.  Lone registers belong to their own threads.  */
     118                 :            : struct regno_assign_info
     119                 :            : {
     120                 :            :   /* First/next pseudo of the same thread.  */
     121                 :            :   int first, next;
     122                 :            :   /* Frequency of the thread (execution frequency of only reload
     123                 :            :      pseudos in the thread when the thread contains a reload pseudo).
     124                 :            :      Defined only for the first thread pseudo.  */
     125                 :            :   int freq;
     126                 :            : };
     127                 :            : 
     128                 :            : /* Map regno to the corresponding regno assignment info.  */
     129                 :            : static struct regno_assign_info *regno_assign_info;
     130                 :            : 
     131                 :            : /* All inherited, subreg or optional pseudos created before last spill
     132                 :            :    sub-pass.  Such pseudos are permitted to get memory instead of hard
     133                 :            :    regs.  */
     134                 :            : static bitmap_head non_reload_pseudos;
     135                 :            : 
     136                 :            : /* Process a pseudo copy with execution frequency COPY_FREQ connecting
     137                 :            :    REGNO1 and REGNO2 to form threads.  */
     138                 :            : static void
     139                 :    1119410 : process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
     140                 :            : {
     141                 :    1119410 :   int last, regno1_first, regno2_first;
     142                 :            : 
     143                 :    1119410 :   lra_assert (regno1 >= lra_constraint_new_regno_start
     144                 :            :               && regno2 >= lra_constraint_new_regno_start);
     145                 :    1119410 :   regno1_first = regno_assign_info[regno1].first;
     146                 :    1119410 :   regno2_first = regno_assign_info[regno2].first;
     147                 :    1119410 :   if (regno1_first != regno2_first)
     148                 :            :     {
     149                 :    4476890 :       for (last = regno2_first;
     150                 :    5596300 :            regno_assign_info[last].next >= 0;
     151                 :    4476890 :            last = regno_assign_info[last].next)
     152                 :    4476890 :         regno_assign_info[last].first = regno1_first;
     153                 :    1119410 :       regno_assign_info[last].first = regno1_first;
     154                 :    1119410 :       regno_assign_info[last].next = regno_assign_info[regno1_first].next;
     155                 :    1119410 :       regno_assign_info[regno1_first].next = regno2_first;
     156                 :    1119410 :       regno_assign_info[regno1_first].freq
     157                 :    1119410 :         += regno_assign_info[regno2_first].freq;
     158                 :            :     }
     159                 :    1119410 :   regno_assign_info[regno1_first].freq -= 2 * copy_freq;
     160                 :    1119410 :   lra_assert (regno_assign_info[regno1_first].freq >= 0);
     161                 :    1119410 : }
     162                 :            : 
     163                 :            : /* Initialize REGNO_ASSIGN_INFO and form threads.  */
     164                 :            : static void
     165                 :     984870 : init_regno_assign_info (void)
     166                 :            : {
     167                 :     984870 :   int i, regno1, regno2, max_regno = max_reg_num ();
     168                 :     984870 :   lra_copy_t cp;
     169                 :            : 
     170                 :     984870 :   regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
     171                 :   61876300 :   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
     172                 :            :     {
     173                 :   60891400 :       regno_assign_info[i].first = i;
     174                 :   60891400 :       regno_assign_info[i].next = -1;
     175                 :   60891400 :       regno_assign_info[i].freq = lra_reg_info[i].freq;
     176                 :            :     }
     177                 :            :   /* Form the threads.  */
     178                 :    3003780 :   for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
     179                 :    2018910 :     if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
     180                 :    2018910 :         && (regno2 = cp->regno2) >= lra_constraint_new_regno_start
     181                 :    2018910 :         && reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
     182                 :    1128300 :         && reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
     183                 :    2018910 :         && (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
     184                 :    1128150 :             == ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
     185                 :    1119410 :       process_copy_to_form_thread (regno1, regno2, cp->freq);
     186                 :     984870 : }
     187                 :            : 
     188                 :            : /* Free REGNO_ASSIGN_INFO.  */
     189                 :            : static void
     190                 :     984870 : finish_regno_assign_info (void)
     191                 :            : {
     192                 :     984870 :   free (regno_assign_info);
     193                 :          0 : }
     194                 :            : 
     195                 :            : /* The function is used to sort *reload* and *inheritance* pseudos to
     196                 :            :    try to assign them hard registers.  We put pseudos from the same
     197                 :            :    thread always nearby.  */
     198                 :            : static int
     199                 :  182211000 : reload_pseudo_compare_func (const void *v1p, const void *v2p)
     200                 :            : {
     201                 :  182211000 :   int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
     202                 :  182211000 :   enum reg_class cl1 = regno_allocno_class_array[r1];
     203                 :  182211000 :   enum reg_class cl2 = regno_allocno_class_array[r2];
     204                 :  182211000 :   int diff;
     205                 :            : 
     206                 :  182211000 :   lra_assert (r1 >= lra_constraint_new_regno_start
     207                 :            :               && r2 >= lra_constraint_new_regno_start);
     208                 :            : 
     209                 :            :   /* Prefer to assign reload registers with smaller classes first to
     210                 :            :      guarantee assignment to all reload registers.  */
     211                 :  182211000 :   if ((diff = (ira_class_hard_regs_num[cl1]
     212                 :  182211000 :                - ira_class_hard_regs_num[cl2])) != 0)
     213                 :            :     return diff;
     214                 :            :   /* Allocate bigger pseudos first to avoid register file
     215                 :            :      fragmentation.  */
     216                 :  172876000 :   if ((diff
     217                 :  172876000 :        = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
     218                 :  172876000 :           - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
     219                 :            :     return diff;
     220                 :  171547000 :   if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
     221                 :  171547000 :                - regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
     222                 :            :     return diff;
     223                 :            :   /* Put pseudos from the thread nearby.  */
     224                 :  100651000 :   if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
     225                 :            :     return diff;
     226                 :            :   /* Prefer pseudos with longer live ranges.  It sets up better
     227                 :            :      prefered hard registers for the thread pseudos and decreases
     228                 :            :      register-register moves between the thread pseudos.  */
     229                 :   15986500 :   if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0)
     230                 :            :     return diff;
     231                 :            :   /* If regs are equally good, sort by their numbers, so that the
     232                 :            :      results of qsort leave nothing to chance.  */
     233                 :    8398450 :   return r1 - r2;
     234                 :            : }
     235                 :            : 
     236                 :            : /* The function is used to sort *non-reload* pseudos to try to assign
     237                 :            :    them hard registers.  The order calculation is simpler than in the
     238                 :            :    previous function and based on the pseudo frequency usage.  */
     239                 :            : static int
     240                 :  647165000 : pseudo_compare_func (const void *v1p, const void *v2p)
     241                 :            : {
     242                 :  647165000 :   int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
     243                 :  647165000 :   int diff;
     244                 :            : 
     245                 :            :   /* Assign hard reg to static chain pointer first pseudo when
     246                 :            :      non-local goto is used.  */
     247                 : 1294330000 :   if ((diff = (non_spilled_static_chain_regno_p (r2)
     248                 :  647165000 :                - non_spilled_static_chain_regno_p (r1))) != 0)
     249                 :            :     return diff;
     250                 :            : 
     251                 :            :   /* Prefer to assign more frequently used registers first.  */
     252                 :  647161000 :   if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
     253                 :            :     return diff;
     254                 :            : 
     255                 :            :   /* If regs are equally good, sort by their numbers, so that the
     256                 :            :      results of qsort leave nothing to chance.  */
     257                 :  379923000 :   return r1 - r2;
     258                 :            : }
     259                 :            : 
     260                 :            : /* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
     261                 :            :    pseudo live ranges with given start point.  We insert only live
     262                 :            :    ranges of pseudos interesting for assignment purposes.  They are
     263                 :            :    reload pseudos and pseudos assigned to hard registers.  */
     264                 :            : static lra_live_range_t *start_point_ranges;
     265                 :            : 
     266                 :            : /* Used as a flag that a live range is not inserted in the start point
     267                 :            :    chain.  */
     268                 :            : static struct lra_live_range not_in_chain_mark;
     269                 :            : 
     270                 :            : /* Create and set up START_POINT_RANGES.  */
     271                 :            : static void
     272                 :     984870 : create_live_range_start_chains (void)
     273                 :            : {
     274                 :     984870 :   int i, max_regno;
     275                 :     984870 :   lra_live_range_t r;
     276                 :            : 
     277                 :     984870 :   start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
     278                 :     984870 :   max_regno = max_reg_num ();
     279                 :   61876300 :   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
     280                 :   60891400 :     if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
     281                 :            :       {
     282                 :   64096400 :         for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
     283                 :            :           {
     284                 :   33710800 :             r->start_next = start_point_ranges[r->start];
     285                 :   33710800 :             start_point_ranges[r->start] = r;
     286                 :            :           }
     287                 :            :       }
     288                 :            :     else
     289                 :            :       {
     290                 :   32313200 :         for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
     291                 :    1807400 :           r->start_next = &not_in_chain_mark;
     292                 :            :       }
     293                 :     984870 : }
     294                 :            : 
     295                 :            : /* Insert live ranges of pseudo REGNO into start chains if they are
     296                 :            :    not there yet.  */
     297                 :            : static void
     298                 :  280550000 : insert_in_live_range_start_chain (int regno)
     299                 :            : {
     300                 :  280550000 :   lra_live_range_t r = lra_reg_info[regno].live_ranges;
     301                 :            : 
     302                 :  280550000 :   if (r->start_next != &not_in_chain_mark)
     303                 :            :     return;
     304                 :      33629 :   for (; r != NULL; r = r->next)
     305                 :            :     {
     306                 :      20449 :       r->start_next = start_point_ranges[r->start];
     307                 :      20449 :       start_point_ranges[r->start] = r;
     308                 :            :     }
     309                 :            : }
     310                 :            : 
     311                 :            : /* Free START_POINT_RANGES.  */
     312                 :            : static void
     313                 :     984870 : finish_live_range_start_chains (void)
     314                 :            : {
     315                 :     984870 :   gcc_assert (start_point_ranges != NULL);
     316                 :     984870 :   free (start_point_ranges);
     317                 :     984870 :   start_point_ranges = NULL;
     318                 :     984870 : }
     319                 :            : 
     320                 :            : /* Map: program point -> bitmap of all pseudos living at the point and
     321                 :            :    assigned to hard registers.  */
     322                 :            : static bitmap_head *live_hard_reg_pseudos;
     323                 :            : static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
     324                 :            : 
     325                 :            : /* reg_renumber corresponding to pseudos marked in
     326                 :            :    live_hard_reg_pseudos.  reg_renumber might be not matched to
     327                 :            :    live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
     328                 :            :    live_hard_reg_pseudos.  */
     329                 :            : static int *live_pseudos_reg_renumber;
     330                 :            : 
     331                 :            : /* Sparseset used to calculate living hard reg pseudos for some program
     332                 :            :    point range.  */
     333                 :            : static sparseset live_range_hard_reg_pseudos;
     334                 :            : 
     335                 :            : /* Sparseset used to calculate living reload/inheritance pseudos for
     336                 :            :    some program point range.  */
     337                 :            : static sparseset live_range_reload_inheritance_pseudos;
     338                 :            : 
     339                 :            : /* Allocate and initialize the data about living pseudos at program
     340                 :            :    points.  */
     341                 :            : static void
     342                 :     984870 : init_lives (void)
     343                 :            : {
     344                 :     984870 :   int i, max_regno = max_reg_num ();
     345                 :            : 
     346                 :     984870 :   live_range_hard_reg_pseudos = sparseset_alloc (max_regno);
     347                 :     984870 :   live_range_reload_inheritance_pseudos = sparseset_alloc (max_regno);
     348                 :     984870 :   live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
     349                 :     984870 :   bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
     350                 :   54250200 :   for (i = 0; i < lra_live_max_point; i++)
     351                 :   53265300 :     bitmap_initialize (&live_hard_reg_pseudos[i],
     352                 :            :                        &live_hard_reg_pseudos_bitmap_obstack);
     353                 :     984870 :   live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
     354                 :  136726000 :   for (i = 0; i < max_regno; i++)
     355                 :  135742000 :     live_pseudos_reg_renumber[i] = -1;
     356                 :     984870 : }
     357                 :            : 
     358                 :            : /* Free the data about living pseudos at program points.  */
     359                 :            : static void
     360                 :     984870 : finish_lives (void)
     361                 :            : {
     362                 :     984870 :   sparseset_free (live_range_hard_reg_pseudos);
     363                 :     984870 :   sparseset_free (live_range_reload_inheritance_pseudos);
     364                 :     984870 :   free (live_hard_reg_pseudos);
     365                 :     984870 :   bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
     366                 :     984870 :   free (live_pseudos_reg_renumber);
     367                 :     984870 : }
     368                 :            : 
     369                 :            : /* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
     370                 :            :    entries for pseudo REGNO.  Assume that the register has been
     371                 :            :    spilled if FREE_P, otherwise assume that it has been assigned
     372                 :            :    reg_renumber[REGNO] (if >= 0).  We also insert the pseudo live
     373                 :            :    ranges in the start chains when it is assumed to be assigned to a
     374                 :            :    hard register because we use the chains of pseudos assigned to hard
     375                 :            :    registers during allocation.  */
     376                 :            : static void
     377                 :   29451700 : update_lives (int regno, bool free_p)
     378                 :            : {
     379                 :   29451700 :   int p;
     380                 :   29451700 :   lra_live_range_t r;
     381                 :            : 
     382                 :   29451700 :   if (reg_renumber[regno] < 0)
     383                 :            :     return;
     384                 :   29451700 :   live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
     385                 :   63192900 :   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
     386                 :            :     {
     387                 :  348850000 :       for (p = r->start; p <= r->finish; p++)
     388                 :  315109000 :         if (free_p)
     389                 :   37480000 :           bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
     390                 :            :         else
     391                 :            :           {
     392                 :  277629000 :             bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
     393                 :  277629000 :             insert_in_live_range_start_chain (regno);
     394                 :            :           }
     395                 :            :     }
     396                 :            : }
     397                 :            : 
     398                 :            : /* Sparseset used to calculate reload pseudos conflicting with a given
     399                 :            :    pseudo when we are trying to find a hard register for the given
     400                 :            :    pseudo.  */
     401                 :            : static sparseset conflict_reload_and_inheritance_pseudos;
     402                 :            : 
     403                 :            : /* Map: program point -> bitmap of all reload and inheritance pseudos
     404                 :            :    living at the point.  */
     405                 :            : static bitmap_head *live_reload_and_inheritance_pseudos;
     406                 :            : static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
     407                 :            : 
     408                 :            : /* Allocate and initialize data about living reload pseudos at any
     409                 :            :    given program point.  */
     410                 :            : static void
     411                 :     984870 : init_live_reload_and_inheritance_pseudos (void)
     412                 :            : {
     413                 :     984870 :   int i, p, max_regno = max_reg_num ();
     414                 :     984870 :   lra_live_range_t r;
     415                 :            : 
     416                 :     984870 :   conflict_reload_and_inheritance_pseudos = sparseset_alloc (max_regno);
     417                 :     984870 :   live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
     418                 :     984870 :   bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
     419                 :   54250200 :   for (p = 0; p < lra_live_max_point; p++)
     420                 :   53265300 :     bitmap_initialize (&live_reload_and_inheritance_pseudos[p],
     421                 :            :                        &live_reload_and_inheritance_pseudos_bitmap_obstack);
     422                 :    9423840 :   for (i = lra_constraint_new_regno_start; i < max_regno; i++)
     423                 :            :     {
     424                 :   16366600 :       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
     425                 :  190589000 :         for (p = r->start; p <= r->finish; p++)
     426                 :  182661000 :           bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
     427                 :            :     }
     428                 :     984870 : }
     429                 :            : 
     430                 :            : /* Finalize data about living reload pseudos at any given program
     431                 :            :    point.  */
     432                 :            : static void
     433                 :     984870 : finish_live_reload_and_inheritance_pseudos (void)
     434                 :            : {
     435                 :     984870 :   sparseset_free (conflict_reload_and_inheritance_pseudos);
     436                 :     984870 :   free (live_reload_and_inheritance_pseudos);
     437                 :     984870 :   bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
     438                 :     984870 : }
     439                 :            : 
     440                 :            : /* The value used to check that cost of given hard reg is really
     441                 :            :    defined currently.  */
     442                 :            : static int curr_hard_regno_costs_check = 0;
     443                 :            : /* Array used to check that cost of the corresponding hard reg (the
     444                 :            :    array element index) is really defined currently.  */
     445                 :            : static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
     446                 :            : /* The current costs of allocation of hard regs.  Defined only if the
     447                 :            :    value of the corresponding element of the previous array is equal to
     448                 :            :    CURR_HARD_REGNO_COSTS_CHECK.  */
     449                 :            : static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
     450                 :            : 
     451                 :            : /* Adjust cost of HARD_REGNO by INCR.  Reset the cost first if it is
     452                 :            :    not defined yet.  */
     453                 :            : static inline void
     454                 :   25698700 : adjust_hard_regno_cost (int hard_regno, int incr)
     455                 :            : {
     456                 :   25698700 :   if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
     457                 :    7002480 :     hard_regno_costs[hard_regno] = 0;
     458                 :   25698700 :   hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
     459                 :   25698700 :   hard_regno_costs[hard_regno] += incr;
     460                 :    8417130 : }
     461                 :            : 
     462                 :            : /* Try to find a free hard register for pseudo REGNO.  Return the
     463                 :            :    hard register on success and set *COST to the cost of using
     464                 :            :    that register.  (If several registers have equal cost, the one with
     465                 :            :    the highest priority wins.)  Return -1 on failure.
     466                 :            : 
     467                 :            :    If FIRST_P, return the first available hard reg ignoring other
     468                 :            :    criteria, e.g. allocation cost.  This approach results in less hard
     469                 :            :    reg pool fragmentation and permit to allocate hard regs to reload
     470                 :            :    pseudos in complicated situations where pseudo sizes are different.
     471                 :            : 
     472                 :            :    If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
     473                 :            :    otherwise consider all hard registers in REGNO's class.
     474                 :            : 
     475                 :            :    If REGNO_SET is not empty, only hard registers from the set are
     476                 :            :    considered.  */
     477                 :            : static int
     478                 :    8875190 : find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
     479                 :            :                        bool first_p, HARD_REG_SET regno_set)
     480                 :            : {
     481                 :    8875190 :   HARD_REG_SET conflict_set;
     482                 :    8875190 :   int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
     483                 :    8875190 :   lra_live_range_t r;
     484                 :    8875190 :   int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
     485                 :    8875190 :   int hr, conflict_hr, nregs;
     486                 :    8875190 :   machine_mode biggest_mode;
     487                 :    8875190 :   unsigned int k, conflict_regno;
     488                 :    8875190 :   poly_int64 offset;
     489                 :            :   int val, biggest_nregs, nregs_diff;
     490                 :            :   enum reg_class rclass;
     491                 :            :   bitmap_iterator bi;
     492                 :            :   bool *rclass_intersect_p;
     493                 :            :   HARD_REG_SET impossible_start_hard_regs, available_regs;
     494                 :            : 
     495                 :   26625600 :   if (hard_reg_set_empty_p (regno_set))
     496                 :    8787560 :     conflict_set = lra_no_alloc_regs;
     497                 :            :   else
     498                 :     350500 :     conflict_set = ~regno_set | lra_no_alloc_regs;
     499                 :    8875190 :   rclass = regno_allocno_class_array[regno];
     500                 :    8875190 :   rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
     501                 :    8875190 :   curr_hard_regno_costs_check++;
     502                 :    8875190 :   sparseset_clear (conflict_reload_and_inheritance_pseudos);
     503                 :    8875190 :   sparseset_clear (live_range_hard_reg_pseudos);
     504                 :    8875190 :   conflict_set |= lra_reg_info[regno].conflict_hard_regs;
     505                 :    8875190 :   biggest_mode = lra_reg_info[regno].biggest_mode;
     506                 :   18823200 :   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
     507                 :            :     {
     508                 :   74335500 :       EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
     509                 :   64387500 :         if (rclass_intersect_p[regno_allocno_class_array[k]])
     510                 :   58131000 :           sparseset_set_bit (live_range_hard_reg_pseudos, k);
     511                 :  135330000 :       EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
     512                 :            :                                 0, k, bi)
     513                 :  125382000 :         if (lra_reg_info[k].preferred_hard_regno1 >= 0
     514                 :   46673000 :             && live_pseudos_reg_renumber[k] < 0
     515                 :   44893900 :             && rclass_intersect_p[regno_allocno_class_array[k]])
     516                 :   43846600 :           sparseset_set_bit (conflict_reload_and_inheritance_pseudos, k);
     517                 : 1552520000 :       for (p = r->start + 1; p <= r->finish; p++)
     518                 :            :         {
     519                 : 1542570000 :           lra_live_range_t r2;
     520                 :            : 
     521                 : 1542570000 :           for (r2 = start_point_ranges[p];
     522                 : 2489920000 :                r2 != NULL;
     523                 :  947350000 :                r2 = r2->start_next)
     524                 :            :             {
     525                 :  947350000 :               if (r2->regno >= lra_constraint_new_regno_start
     526                 :  360506000 :                   && lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
     527                 :  119464000 :                   && live_pseudos_reg_renumber[r2->regno] < 0
     528                 :   44615700 :                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
     529                 :   40245100 :                 sparseset_set_bit (conflict_reload_and_inheritance_pseudos,
     530                 :            :                                    r2->regno);
     531                 :  947350000 :               if (live_pseudos_reg_renumber[r2->regno] >= 0
     532                 :  831239000 :                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]])
     533                 :  739372000 :                 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
     534                 :            :             }
     535                 :            :         }
     536                 :            :     }
     537                 :    8875190 :   if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
     538                 :            :     {
     539                 :    3428410 :       adjust_hard_regno_cost
     540                 :    3428410 :         (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit1);
     541                 :    3428410 :       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
     542                 :    1058840 :         adjust_hard_regno_cost
     543                 :    1058840 :           (hard_regno, -lra_reg_info[regno].preferred_hard_regno_profit2);
     544                 :            :     }
     545                 :            : #ifdef STACK_REGS
     546                 :    8875190 :   if (lra_reg_info[regno].no_stack_p)
     547                 :     236862 :     for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
     548                 :     210544 :       SET_HARD_REG_BIT (conflict_set, i);
     549                 :            : #endif
     550                 :    8875190 :   sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
     551                 :    8875190 :   val = lra_reg_info[regno].val;
     552                 :    8875190 :   offset = lra_reg_info[regno].offset;
     553                 :    8875190 :   CLEAR_HARD_REG_SET (impossible_start_hard_regs);
     554                 :  454739000 :   EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
     555                 :            :     {
     556                 :  224336000 :       conflict_hr = live_pseudos_reg_renumber[conflict_regno];
     557                 :  224336000 :       if (lra_reg_val_equal_p (conflict_regno, val, offset))
     558                 :            :         {
     559                 :     603170 :           conflict_hr = live_pseudos_reg_renumber[conflict_regno];
     560                 :     603170 :           nregs = hard_regno_nregs (conflict_hr,
     561                 :     603170 :                                     lra_reg_info[conflict_regno].biggest_mode);
     562                 :            :           /* Remember about multi-register pseudos.  For example, 2
     563                 :            :              hard register pseudos can start on the same hard register
     564                 :            :              but cannot start on HR and HR+1/HR-1.  */
     565                 :     612189 :           for (hr = conflict_hr + 1;
     566                 :     612189 :                hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
     567                 :            :                hr++)
     568                 :       9019 :             SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
     569                 :     609865 :           for (hr = conflict_hr - 1;
     570                 :     609865 :                hr >= 0 && (int) end_hard_regno (biggest_mode, hr) > conflict_hr;
     571                 :            :                hr--)
     572                 :       6695 :             SET_HARD_REG_BIT (impossible_start_hard_regs, hr);
     573                 :            :         }
     574                 :            :       else
     575                 :            :         {
     576                 :  223733000 :           machine_mode biggest_conflict_mode
     577                 :  223733000 :             = lra_reg_info[conflict_regno].biggest_mode;
     578                 :  223733000 :           int biggest_conflict_nregs
     579                 :  223733000 :             = hard_regno_nregs (conflict_hr, biggest_conflict_mode);
     580                 :            :           
     581                 :  223733000 :           nregs_diff
     582                 :  223733000 :             = (biggest_conflict_nregs
     583                 :  223733000 :                - hard_regno_nregs (conflict_hr,
     584                 :  223733000 :                                    PSEUDO_REGNO_MODE (conflict_regno)));
     585                 :  223733000 :           add_to_hard_reg_set (&conflict_set,
     586                 :            :                                biggest_conflict_mode,
     587                 :            :                                conflict_hr
     588                 :            :                                - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
     589                 :  447466000 :           if (hard_reg_set_subset_p (reg_class_contents[rclass],
     590                 :            :                                      conflict_set))
     591                 :            :             return -1;
     592                 :            :         }
     593                 :            :     }
     594                 :   34166000 :   EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
     595                 :            :                                conflict_regno)
     596                 :   14049500 :     if (!lra_reg_val_equal_p (conflict_regno, val, offset))
     597                 :            :       {
     598                 :   13853200 :         lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
     599                 :   13853200 :         if ((hard_regno
     600                 :   13853200 :              = lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
     601                 :            :           {
     602                 :   13853200 :             adjust_hard_regno_cost
     603                 :   13853200 :               (hard_regno,
     604                 :            :                lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
     605                 :   13853200 :             if ((hard_regno
     606                 :   13853200 :                  = lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
     607                 :    7358290 :               adjust_hard_regno_cost
     608                 :   21407800 :                 (hard_regno,
     609                 :            :                  lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
     610                 :            :           }
     611                 :            :       }
     612                 :            :   /* Make sure that all registers in a multi-word pseudo belong to the
     613                 :            :      required class.  */
     614                 :   12133900 :   conflict_set |= ~reg_class_contents[rclass];
     615                 :    6066940 :   lra_assert (rclass != NO_REGS);
     616                 :    6066940 :   rclass_size = ira_class_hard_regs_num[rclass];
     617                 :    6066940 :   best_hard_regno = -1;
     618                 :    6066940 :   hard_regno = ira_class_hard_regs[rclass][0];
     619                 :    6066940 :   biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
     620                 :    6066940 :   nregs_diff = (biggest_nregs
     621                 :    6066940 :                 - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno)));
     622                 :   12133900 :   available_regs = reg_class_contents[rclass] & ~lra_no_alloc_regs;
     623                 :   77315500 :   for (i = 0; i < rclass_size; i++)
     624                 :            :     {
     625                 :   71304500 :       if (try_only_hard_regno >= 0)
     626                 :            :         hard_regno = try_only_hard_regno;
     627                 :            :       else
     628                 :   71248600 :         hard_regno = ira_class_hard_regs[rclass][i];
     629                 :  185287000 :       if (! overlaps_hard_reg_set_p (conflict_set,
     630                 :   71304500 :                                      PSEUDO_REGNO_MODE (regno), hard_regno)
     631                 :   42360000 :           && targetm.hard_regno_mode_ok (hard_regno,
     632                 :            :                                          PSEUDO_REGNO_MODE (regno))
     633                 :            :           /* We cannot use prohibited_class_mode_regs for all classes
     634                 :            :              because it is not defined for all classes.  */
     635                 :   42306200 :           && (ira_allocno_class_translate[rclass] != rclass
     636                 :   23974100 :               || ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
     637                 :   23974100 :                                       [rclass][PSEUDO_REGNO_MODE (regno)],
     638                 :            :                                       hard_regno))
     639                 :   42306200 :           && ! TEST_HARD_REG_BIT (impossible_start_hard_regs, hard_regno)
     640                 :   84980300 :           && (nregs_diff == 0
     641                 :       3301 :               || (WORDS_BIG_ENDIAN
     642                 :            :                   ? (hard_regno - nregs_diff >= 0
     643                 :            :                      && TEST_HARD_REG_BIT (available_regs,
     644                 :            :                                            hard_regno - nregs_diff))
     645                 :       3301 :                   : TEST_HARD_REG_BIT (available_regs,
     646                 :       3301 :                                        hard_regno + nregs_diff))))
     647                 :            :         {
     648                 :   42301200 :           if (hard_regno_costs_check[hard_regno]
     649                 :   42301200 :               != curr_hard_regno_costs_check)
     650                 :            :             {
     651                 :   38742100 :               hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
     652                 :   38742100 :               hard_regno_costs[hard_regno] = 0;
     653                 :            :             }
     654                 :   42900900 :           for (j = 0;
     655                 :   85202100 :                j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
     656                 :            :                j++)
     657                 :   42900900 :             if (! crtl->abi->clobbers_full_reg_p (hard_regno + j)
     658                 :   42900900 :                 && ! df_regs_ever_live_p (hard_regno + j))
     659                 :            :               /* It needs save restore.  */
     660                 :    3345540 :               hard_regno_costs[hard_regno]
     661                 :    3345540 :                 += (2
     662                 :    9620990 :                     * REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
     663                 :    9620990 :                     + 1);
     664                 :   42301200 :           priority = targetm.register_priority (hard_regno);
     665                 :   36336600 :           if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
     666                 :   77251100 :               || (hard_regno_costs[hard_regno] == best_cost
     667                 :   19183200 :                   && (priority > best_priority
     668                 :   19149100 :                       || (targetm.register_usage_leveling_p ()
     669                 :   19149100 :                           && priority == best_priority
     670                 :    5384720 :                           && best_usage > lra_hard_reg_usage[hard_regno]))))
     671                 :            :             {
     672                 :    9290780 :               best_hard_regno = hard_regno;
     673                 :    9290780 :               best_cost = hard_regno_costs[hard_regno];
     674                 :    9290780 :               best_priority = priority;
     675                 :    9290780 :               best_usage = lra_hard_reg_usage[hard_regno];
     676                 :            :             }
     677                 :            :         }
     678                 :   71304500 :       if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
     679                 :            :         break;
     680                 :            :     }
     681                 :    6066940 :   if (best_hard_regno >= 0)
     682                 :    5964620 :     *cost = best_cost - lra_reg_info[regno].freq;
     683                 :            :   return best_hard_regno;
     684                 :            : }
     685                 :            : 
     686                 :            : /* A wrapper for find_hard_regno_for_1 (see comments for that function
     687                 :            :    description).  This function tries to find a hard register for
     688                 :            :    preferred class first if it is worth.  */
     689                 :            : static int
     690                 :    8788170 : find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
     691                 :            : {
     692                 :    8788170 :   int hard_regno;
     693                 :    8788170 :   HARD_REG_SET regno_set;
     694                 :            : 
     695                 :            :   /* Only original pseudos can have a different preferred class.  */
     696                 :    8788170 :   if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
     697                 :            :     {
     698                 :     838356 :       enum reg_class pref_class = reg_preferred_class (regno);
     699                 :            :       
     700                 :     838356 :       if (regno_allocno_class_array[regno] != pref_class)
     701                 :            :         {
     702                 :     175250 :           hard_regno = find_hard_regno_for_1 (regno, cost, -1, first_p,
     703                 :      87625 :                                               reg_class_contents[pref_class]);
     704                 :      87625 :           if (hard_regno >= 0)
     705                 :            :             return hard_regno;
     706                 :            :         }
     707                 :            :     }
     708                 :   26362700 :   CLEAR_HARD_REG_SET (regno_set);
     709                 :    8787560 :   return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
     710                 :    8787560 :                                 regno_set);
     711                 :            : }
     712                 :            : 
     713                 :            : /* Current value used for checking elements in
     714                 :            :    update_hard_regno_preference_check.  */
     715                 :            : static int curr_update_hard_regno_preference_check;
     716                 :            : /* If an element value is equal to the above variable value, then the
     717                 :            :    corresponding regno has been processed for preference
     718                 :            :    propagation.  */
     719                 :            : static int *update_hard_regno_preference_check;
     720                 :            : 
     721                 :            : /* Update the preference for using HARD_REGNO for pseudos that are
     722                 :            :    connected directly or indirectly with REGNO.  Apply divisor DIV
     723                 :            :    to any preference adjustments.
     724                 :            : 
     725                 :            :    The more indirectly a pseudo is connected, the smaller its effect
     726                 :            :    should be.  We therefore increase DIV on each "hop".  */
     727                 :            : static void
     728                 :    7046230 : update_hard_regno_preference (int regno, int hard_regno, int div)
     729                 :            : {
     730                 :    7046230 :   int another_regno, cost;
     731                 :    7046230 :   lra_copy_t cp, next_cp;
     732                 :            : 
     733                 :            :   /* Search depth 5 seems to be enough.  */
     734                 :    7046230 :   if (div > (1 << 5))
     735                 :            :     return;
     736                 :   12983700 :   for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
     737                 :            :     {
     738                 :    6045240 :       if (cp->regno1 == regno)
     739                 :            :         {
     740                 :    2777530 :           next_cp = cp->regno1_next;
     741                 :    2777530 :           another_regno = cp->regno2;
     742                 :            :         }
     743                 :    3267710 :       else if (cp->regno2 == regno)
     744                 :            :         {
     745                 :    3267710 :           next_cp = cp->regno2_next;
     746                 :    3267710 :           another_regno = cp->regno1;
     747                 :            :         }
     748                 :            :       else
     749                 :          0 :         gcc_unreachable ();
     750                 :    6045240 :       if (reg_renumber[another_regno] < 0
     751                 :    3514220 :           && (update_hard_regno_preference_check[another_regno]
     752                 :    3514220 :               != curr_update_hard_regno_preference_check))
     753                 :            :         {
     754                 :    2336650 :           update_hard_regno_preference_check[another_regno]
     755                 :    2336650 :             = curr_update_hard_regno_preference_check;
     756                 :    2336650 :           cost = cp->freq < div ? 1 : cp->freq / div;
     757                 :    2336650 :           lra_setup_reload_pseudo_preferenced_hard_reg
     758                 :    2336650 :             (another_regno, hard_regno, cost);
     759                 :    2336650 :           update_hard_regno_preference (another_regno, hard_regno, div * 2);
     760                 :            :         }
     761                 :            :     }
     762                 :            : }
     763                 :            : 
     764                 :            : /* Return prefix title for pseudo REGNO.  */
     765                 :            : static const char *
     766                 :        252 : pseudo_prefix_title (int regno)
     767                 :            : {
     768                 :        252 :   return
     769                 :        252 :     (regno < lra_constraint_new_regno_start ? ""
     770                 :        245 :      : bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
     771                 :        224 :      : bitmap_bit_p (&lra_split_regs, regno) ? "split "
     772                 :        224 :      : bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
     773                 :        210 :      : bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
     774                 :        252 :      : "reload ");
     775                 :            : }
     776                 :            : 
     777                 :            : /* Update REG_RENUMBER and other pseudo preferences by assignment of
     778                 :            :    HARD_REGNO to pseudo REGNO and print about it if PRINT_P.  */
     779                 :            : void
     780                 :    4788840 : lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
     781                 :            : {
     782                 :    4788840 :   int i, hr;
     783                 :            : 
     784                 :            :   /* We cannot just reassign hard register.  */
     785                 :    4788840 :   lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
     786                 :    4788840 :   if ((hr = hard_regno) < 0)
     787                 :      79266 :     hr = reg_renumber[regno];
     788                 :    4788840 :   reg_renumber[regno] = hard_regno;
     789                 :    4788840 :   lra_assert (hr >= 0);
     790                 :    9684910 :   for (i = 0; i < hard_regno_nregs (hr, PSEUDO_REGNO_MODE (regno)); i++)
     791                 :    4896070 :     if (hard_regno < 0)
     792                 :      81295 :       lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
     793                 :            :     else
     794                 :    4814770 :       lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
     795                 :    4788840 :   if (print_p && lra_dump_file != NULL)
     796                 :        490 :     fprintf (lra_dump_file, "         Assign %d to %sr%d (freq=%d)\n",
     797                 :        245 :              reg_renumber[regno], pseudo_prefix_title (regno),
     798                 :        245 :              regno, lra_reg_info[regno].freq);
     799                 :    4788840 :   if (hard_regno >= 0)
     800                 :            :     {
     801                 :    4709580 :       curr_update_hard_regno_preference_check++;
     802                 :    4709580 :       update_hard_regno_preference (regno, hard_regno, 1);
     803                 :            :     }
     804                 :    4788840 : }
     805                 :            : 
     806                 :            : /* Pseudos which occur in insns containing a particular pseudo.  */
     807                 :            : static bitmap_head insn_conflict_pseudos;
     808                 :            : 
     809                 :            : /* Bitmaps used to contain spill pseudos for given pseudo hard regno
     810                 :            :    and best spill pseudos for given pseudo (and best hard regno).  */
     811                 :            : static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
     812                 :            : 
     813                 :            : /* Current pseudo check for validity of elements in
     814                 :            :    TRY_HARD_REG_PSEUDOS.  */
     815                 :            : static int curr_pseudo_check;
     816                 :            : /* Array used for validity of elements in TRY_HARD_REG_PSEUDOS.  */
     817                 :            : static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
     818                 :            : /* Pseudos who hold given hard register at the considered points.  */
     819                 :            : static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
     820                 :            : 
     821                 :            : /* Set up try_hard_reg_pseudos for given program point P and class
     822                 :            :    RCLASS.  Those are pseudos living at P and assigned to a hard
     823                 :            :    register of RCLASS.  In other words, those are pseudos which can be
     824                 :            :    spilled to assign a hard register of RCLASS to a pseudo living at
     825                 :            :    P.  */
     826                 :            : static void
     827                 :      48605 : setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
     828                 :            : {
     829                 :      48605 :   int i, hard_regno;
     830                 :      48605 :   machine_mode mode;
     831                 :      48605 :   unsigned int spill_regno;
     832                 :      48605 :   bitmap_iterator bi;
     833                 :            : 
     834                 :            :   /* Find what pseudos could be spilled.  */
     835                 :     385160 :   EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
     836                 :            :     {
     837                 :     336555 :       mode = PSEUDO_REGNO_MODE (spill_regno);
     838                 :     336555 :       hard_regno = live_pseudos_reg_renumber[spill_regno];
     839                 :     403035 :       if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
     840                 :            :                                    mode, hard_regno))
     841                 :            :         {
     842                 :     548908 :           for (i = hard_regno_nregs (hard_regno, mode) - 1; i >= 0; i--)
     843                 :            :             {
     844                 :     278787 :               if (try_hard_reg_pseudos_check[hard_regno + i]
     845                 :     278787 :                   != curr_pseudo_check)
     846                 :            :                 {
     847                 :     135246 :                   try_hard_reg_pseudos_check[hard_regno + i]
     848                 :     135246 :                     = curr_pseudo_check;
     849                 :     135246 :                   bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
     850                 :            :                 }
     851                 :     278787 :               bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
     852                 :            :                               spill_regno);
     853                 :            :             }
     854                 :            :         }
     855                 :            :     }
     856                 :      48605 : }
     857                 :            : 
     858                 :            : /* Assign temporarily HARD_REGNO to pseudo REGNO.  Temporary
     859                 :            :    assignment means that we might undo the data change.  */
     860                 :            : static void
     861                 :    1091110 : assign_temporarily (int regno, int hard_regno)
     862                 :            : {
     863                 :    1091110 :   int p;
     864                 :    1091110 :   lra_live_range_t r;
     865                 :            : 
     866                 :    2192200 :   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
     867                 :            :     {
     868                 :    6943370 :       for (p = r->start; p <= r->finish; p++)
     869                 :    5842280 :         if (hard_regno < 0)
     870                 :    2921140 :           bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
     871                 :            :         else
     872                 :            :           {
     873                 :    2921140 :             bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
     874                 :    2921140 :             insert_in_live_range_start_chain (regno);
     875                 :            :           }
     876                 :            :     }
     877                 :    1091110 :   live_pseudos_reg_renumber[regno] = hard_regno;
     878                 :    1091110 : }
     879                 :            : 
     880                 :            : /* Return true iff there is a reason why pseudo SPILL_REGNO should not
     881                 :            :    be spilled.  */
     882                 :            : static bool
     883                 :     137723 : must_not_spill_p (unsigned spill_regno)
     884                 :            : {
     885                 :     137723 :   if ((pic_offset_table_rtx != NULL
     886                 :      42193 :        && spill_regno == REGNO (pic_offset_table_rtx))
     887                 :     177256 :       || ((int) spill_regno >= lra_constraint_new_regno_start
     888                 :      10195 :           && ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
     889                 :       3580 :           && ! bitmap_bit_p (&lra_split_regs, spill_regno)
     890                 :       3135 :           && ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
     891                 :       3135 :           && ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
     892                 :       5002 :     return true;
     893                 :            :   /* A reload pseudo that requires a singleton register class should
     894                 :            :      not be spilled.
     895                 :            :      FIXME: this mitigates the issue on certain i386 patterns, but
     896                 :            :      does not solve the general case where existing reloads fully
     897                 :            :      cover a limited register class.  */
     898                 :     132721 :   if (!bitmap_bit_p (&non_reload_pseudos, spill_regno)
     899                 :     124868 :       && reg_class_size [reg_preferred_class (spill_regno)] == 1
     900                 :     137721 :       && reg_alternate_class (spill_regno) == NO_REGS)
     901                 :          7 :     return true;
     902                 :            :   return false;
     903                 :            : }
     904                 :            : 
     905                 :            : /* Array used for sorting reload pseudos for subsequent allocation
     906                 :            :    after spilling some pseudo.  */
     907                 :            : static int *sorted_reload_pseudos;
     908                 :            : 
     909                 :            : /* Spill some pseudos for a reload pseudo REGNO and return hard
     910                 :            :    register which should be used for pseudo after spilling.  The
     911                 :            :    function adds spilled pseudos to SPILLED_PSEUDO_BITMAP.  When we
     912                 :            :    choose hard register (and pseudos occupying the hard registers and
     913                 :            :    to be spilled), we take into account not only how REGNO will
     914                 :            :    benefit from the spills but also how other reload pseudos not yet
     915                 :            :    assigned to hard registers benefit from the spills too.  In very
     916                 :            :    rare cases, the function can fail and return -1.
     917                 :            : 
     918                 :            :    If FIRST_P, return the first available hard reg ignoring other
     919                 :            :    criteria, e.g. allocation cost and cost of spilling non-reload
     920                 :            :    pseudos.  This approach results in less hard reg pool fragmentation
     921                 :            :    and permit to allocate hard regs to reload pseudos in complicated
     922                 :            :    situations where pseudo sizes are different.  */
     923                 :            : static int
     924                 :      23153 : spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
     925                 :            : {
     926                 :      23153 :   int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
     927                 :      23153 :   int reload_hard_regno, reload_cost;
     928                 :      23153 :   bool static_p, best_static_p;
     929                 :      23153 :   machine_mode mode;
     930                 :      23153 :   enum reg_class rclass;
     931                 :      23153 :   unsigned int spill_regno, reload_regno, uid;
     932                 :      23153 :   int insn_pseudos_num, best_insn_pseudos_num;
     933                 :      23153 :   int bad_spills_num, smallest_bad_spills_num;
     934                 :      23153 :   lra_live_range_t r;
     935                 :      23153 :   bitmap_iterator bi;
     936                 :            : 
     937                 :      23153 :   rclass = regno_allocno_class_array[regno];
     938                 :      23153 :   lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
     939                 :      23153 :   bitmap_clear (&insn_conflict_pseudos);
     940                 :      23153 :   bitmap_clear (&best_spill_pseudos_bitmap);
     941                 :      71255 :   EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
     942                 :            :     {
     943                 :      48102 :       struct lra_insn_reg *ir;
     944                 :            : 
     945                 :     160605 :       for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
     946                 :     112503 :         if (ir->regno >= FIRST_PSEUDO_REGISTER)
     947                 :     107993 :           bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
     948                 :            :     }
     949                 :      23153 :   best_hard_regno = -1;
     950                 :      23153 :   best_cost = INT_MAX;
     951                 :      23153 :   best_static_p = TRUE;
     952                 :      23153 :   best_insn_pseudos_num = INT_MAX;
     953                 :      23153 :   smallest_bad_spills_num = INT_MAX;
     954                 :      23153 :   rclass_size = ira_class_hard_regs_num[rclass];
     955                 :      23153 :   mode = PSEUDO_REGNO_MODE (regno);
     956                 :            :   /* Invalidate try_hard_reg_pseudos elements.  */
     957                 :      23153 :   curr_pseudo_check++;
     958                 :      46317 :   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
     959                 :      71769 :     for (p = r->start; p <= r->finish; p++)
     960                 :      48605 :       setup_try_hard_regno_pseudos (p, rclass);
     961                 :     163652 :   for (i = 0; i < rclass_size; i++)
     962                 :            :     {
     963                 :     140499 :       hard_regno = ira_class_hard_regs[rclass][i];
     964                 :     140499 :       bitmap_clear (&spill_pseudos_bitmap);
     965                 :     289385 :       for (j = hard_regno_nregs (hard_regno, mode) - 1; j >= 0; j--)
     966                 :            :         {
     967                 :     148886 :           if (hard_regno + j >= FIRST_PSEUDO_REGISTER)
     968                 :            :             break;
     969                 :     148886 :           if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
     970                 :      10376 :             continue;
     971                 :     138510 :           lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
     972                 :     138510 :           bitmap_ior_into (&spill_pseudos_bitmap,
     973                 :            :                            &try_hard_reg_pseudos[hard_regno + j]);
     974                 :            :         }
     975                 :            :       /* Spill pseudos.  */
     976                 :     140499 :       static_p = false;
     977                 :     273213 :       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
     978                 :     137723 :         if (must_not_spill_p (spill_regno))
     979                 :       5009 :           goto fail;
     980                 :     134454 :         else if (non_spilled_static_chain_regno_p (spill_regno))
     981                 :            :           static_p = true;
     982                 :     135490 :       insn_pseudos_num = 0;
     983                 :     135490 :       bad_spills_num = 0;
     984                 :     135490 :       if (lra_dump_file != NULL)
     985                 :        105 :         fprintf (lra_dump_file, "   Trying %d:", hard_regno);
     986                 :     135490 :       sparseset_clear (live_range_reload_inheritance_pseudos);
     987                 :     268057 :       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
     988                 :            :         {
     989                 :     132567 :           if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
     990                 :      25077 :             insn_pseudos_num++;
     991                 :     132567 :           if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
     992                 :          0 :             bad_spills_num++;
     993                 :     132567 :           for (r = lra_reg_info[spill_regno].live_ranges;
     994                 :     405882 :                r != NULL;
     995                 :     273315 :                r = r->next)
     996                 :            :             {
     997                 :   35608100 :               for (p = r->start; p <= r->finish; p++)
     998                 :            :                 {
     999                 :   35334800 :                   lra_live_range_t r2;
    1000                 :            : 
    1001                 :   35334800 :                   for (r2 = start_point_ranges[p];
    1002                 :   63793300 :                        r2 != NULL;
    1003                 :   28458500 :                        r2 = r2->start_next)
    1004                 :   28458500 :                     if (r2->regno >= lra_constraint_new_regno_start)
    1005                 :   22968100 :                       sparseset_set_bit (live_range_reload_inheritance_pseudos,
    1006                 :            :                                          r2->regno);
    1007                 :            :                 }
    1008                 :            :             }
    1009                 :            :         }
    1010                 :     135490 :       n = 0;
    1011                 :     135490 :       if (sparseset_cardinality (live_range_reload_inheritance_pseudos)
    1012                 :     135490 :           <= (unsigned)param_lra_max_considered_reload_pseudos)
    1013                 :    6687880 :         EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
    1014                 :            :                                      reload_regno)
    1015                 :    3272910 :           if ((int) reload_regno != regno
    1016                 :    3150900 :               && (ira_reg_classes_intersect_p
    1017                 :    3150900 :                   [rclass][regno_allocno_class_array[reload_regno]])
    1018                 :    2709280 :               && live_pseudos_reg_renumber[reload_regno] < 0
    1019                 :    4926490 :               && find_hard_regno_for (reload_regno, &cost, -1, first_p) < 0)
    1020                 :     883951 :             sorted_reload_pseudos[n++] = reload_regno;
    1021                 :     268057 :       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
    1022                 :            :         {
    1023                 :     132567 :           update_lives (spill_regno, true);
    1024                 :     132567 :           if (lra_dump_file != NULL)
    1025                 :        105 :             fprintf (lra_dump_file, " spill %d(freq=%d)",
    1026                 :        105 :                      spill_regno, lra_reg_info[spill_regno].freq);
    1027                 :            :         }
    1028                 :     135490 :       hard_regno = find_hard_regno_for (regno, &cost, -1, first_p);
    1029                 :     135490 :       if (hard_regno >= 0)
    1030                 :            :         {
    1031                 :     130674 :           assign_temporarily (regno, hard_regno);
    1032                 :     130674 :           qsort (sorted_reload_pseudos, n, sizeof (int),
    1033                 :            :                  reload_pseudo_compare_func);
    1034                 :    1012210 :           for (j = 0; j < n; j++)
    1035                 :            :             {
    1036                 :     881539 :               reload_regno = sorted_reload_pseudos[j];
    1037                 :     881539 :               lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
    1038                 :    1763080 :               if ((reload_hard_regno
    1039                 :     881539 :                    = find_hard_regno_for (reload_regno,
    1040                 :            :                                           &reload_cost, -1, first_p)) >= 0)
    1041                 :            :                 {
    1042                 :     414883 :                   if (lra_dump_file != NULL)
    1043                 :        196 :                     fprintf (lra_dump_file, " assign %d(cost=%d)",
    1044                 :            :                              reload_regno, reload_cost);
    1045                 :     414883 :                   assign_temporarily (reload_regno, reload_hard_regno);
    1046                 :     414883 :                   cost += reload_cost;
    1047                 :            :                 }
    1048                 :            :             }
    1049                 :     262892 :           EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
    1050                 :            :             {
    1051                 :     132218 :               rtx_insn_list *x;
    1052                 :            : 
    1053                 :     132218 :               cost += lra_reg_info[spill_regno].freq;
    1054                 :     132218 :               if (ira_reg_equiv[spill_regno].memory != NULL
    1055                 :     123052 :                   || ira_reg_equiv[spill_regno].constant != NULL)
    1056                 :      11613 :                 for (x = ira_reg_equiv[spill_regno].init_insns;
    1057                 :      11613 :                      x != NULL;
    1058                 :     142303 :                      x = x->next ())
    1059                 :      10085 :                   cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
    1060                 :            :             }
    1061                 :            :           /* Avoid spilling static chain pointer pseudo when non-local
    1062                 :            :              goto is used.  */
    1063                 :     130674 :           if ((! static_p && best_static_p)
    1064                 :     107547 :               || (static_p == best_static_p
    1065                 :     107547 :                   && (best_insn_pseudos_num > insn_pseudos_num
    1066                 :     102942 :                       || (best_insn_pseudos_num == insn_pseudos_num
    1067                 :      92671 :                           && (bad_spills_num < smallest_bad_spills_num
    1068                 :      92671 :                               || (bad_spills_num == smallest_bad_spills_num
    1069                 :      92671 :                                   && best_cost > cost))))))
    1070                 :            :             {
    1071                 :      50914 :               best_insn_pseudos_num = insn_pseudos_num;
    1072                 :      50914 :               smallest_bad_spills_num = bad_spills_num;
    1073                 :      50914 :               best_static_p = static_p;
    1074                 :      50914 :               best_cost = cost;
    1075                 :      50914 :               best_hard_regno = hard_regno;
    1076                 :      50914 :               bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
    1077                 :      50914 :               if (lra_dump_file != NULL)
    1078                 :         35 :                 fprintf (lra_dump_file,
    1079                 :            :                          "  Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
    1080                 :            :                          hard_regno, cost, bad_spills_num, insn_pseudos_num);
    1081                 :            :             }
    1082                 :     130674 :           assign_temporarily (regno, -1);
    1083                 :    1012210 :           for (j = 0; j < n; j++)
    1084                 :            :             {
    1085                 :     881539 :               reload_regno = sorted_reload_pseudos[j];
    1086                 :     881539 :               if (live_pseudos_reg_renumber[reload_regno] >= 0)
    1087                 :     414883 :                 assign_temporarily (reload_regno, -1);
    1088                 :            :             }
    1089                 :            :         }
    1090                 :     135490 :       if (lra_dump_file != NULL)
    1091                 :        105 :         fprintf (lra_dump_file, "\n");
    1092                 :            :       /* Restore the live hard reg pseudo info for spilled pseudos.  */
    1093                 :     268057 :       EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
    1094                 :     132567 :         update_lives (spill_regno, false);
    1095                 :     135490 :     fail:
    1096                 :     140499 :       ;
    1097                 :            :     }
    1098                 :            :   /* Spill: */
    1099                 :      46447 :   EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
    1100                 :            :     {
    1101                 :      23294 :       if ((int) spill_regno >= lra_constraint_new_regno_start)
    1102                 :       1098 :         former_reload_pseudo_spill_p = true;
    1103                 :      23294 :       if (lra_dump_file != NULL)
    1104                 :          7 :         fprintf (lra_dump_file, "      Spill %sr%d(hr=%d, freq=%d) for r%d\n",
    1105                 :            :                  pseudo_prefix_title (spill_regno),
    1106                 :          7 :                  spill_regno, reg_renumber[spill_regno],
    1107                 :          7 :                  lra_reg_info[spill_regno].freq, regno);
    1108                 :      23294 :       update_lives (spill_regno, true);
    1109                 :      23294 :       lra_setup_reg_renumber (spill_regno, -1, false);
    1110                 :            :     }
    1111                 :      23153 :   bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
    1112                 :      23153 :   return best_hard_regno;
    1113                 :            : }
    1114                 :            : 
    1115                 :            : /* Assign HARD_REGNO to REGNO.  */
    1116                 :            : static void
    1117                 :    4709570 : assign_hard_regno (int hard_regno, int regno)
    1118                 :            : {
    1119                 :    4709570 :   int i;
    1120                 :            : 
    1121                 :    4709570 :   lra_assert (hard_regno >= 0);
    1122                 :    4709570 :   lra_setup_reg_renumber (regno, hard_regno, true);
    1123                 :    4709570 :   update_lives (regno, false);
    1124                 :    9524870 :   for (i = 0;
    1125                 :    9524870 :        i < hard_regno_nregs (hard_regno, lra_reg_info[regno].biggest_mode);
    1126                 :            :        i++)
    1127                 :    4815310 :     df_set_regs_ever_live (hard_regno + i, true);
    1128                 :    4709570 : }
    1129                 :            : 
    1130                 :            : /* Array used for sorting different pseudos.  */
    1131                 :            : static int *sorted_pseudos;
    1132                 :            : 
    1133                 :            : /* The constraints pass is allowed to create equivalences between
    1134                 :            :    pseudos that make the current allocation "incorrect" (in the sense
    1135                 :            :    that pseudos are assigned to hard registers from their own conflict
    1136                 :            :    sets).  The global variable check_and_force_assignment_correctness_p says
    1137                 :            :    whether this might have happened.
    1138                 :            : 
    1139                 :            :    Process pseudos assigned to hard registers (less frequently used
    1140                 :            :    first), spill if a conflict is found, and mark the spilled pseudos
    1141                 :            :    in SPILLED_PSEUDO_BITMAP.  Set up LIVE_HARD_REG_PSEUDOS from
    1142                 :            :    pseudos, assigned to hard registers.  */
    1143                 :            : static void
    1144                 :     984870 : setup_live_pseudos_and_spill_after_risky_transforms (bitmap
    1145                 :            :                                                      spilled_pseudo_bitmap)
    1146                 :            : {
    1147                 :     984870 :   int p, i, j, n, regno, hard_regno, biggest_nregs, nregs_diff;
    1148                 :     984870 :   unsigned int k, conflict_regno;
    1149                 :     984870 :   poly_int64 offset;
    1150                 :     984870 :   int val;
    1151                 :     984870 :   HARD_REG_SET conflict_set;
    1152                 :     984870 :   machine_mode mode, biggest_mode;
    1153                 :     984870 :   lra_live_range_t r;
    1154                 :     984870 :   bitmap_iterator bi;
    1155                 :     984870 :   int max_regno = max_reg_num ();
    1156                 :            : 
    1157                 :     984870 :   if (! check_and_force_assignment_correctness_p)
    1158                 :            :     {
    1159                 :   12872700 :       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    1160                 :   12837800 :         if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
    1161                 :    6134100 :           update_lives (i, false);
    1162                 :      34956 :       return;
    1163                 :            :     }
    1164                 :   49003600 :   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    1165                 :   48053700 :     if ((pic_offset_table_rtx == NULL_RTX
    1166                 :    4966290 :          || i != (int) REGNO (pic_offset_table_rtx))
    1167                 :   52983600 :         && (hard_regno = reg_renumber[i]) >= 0 && lra_reg_info[i].nrefs > 0)
    1168                 :            :       {
    1169                 :   18239300 :         biggest_mode = lra_reg_info[i].biggest_mode;
    1170                 :   18239300 :         biggest_nregs = hard_regno_nregs (hard_regno, biggest_mode);
    1171                 :   18239300 :         nregs_diff = (biggest_nregs
    1172                 :   18239300 :                       - hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (i)));
    1173                 :   18239300 :         enum reg_class rclass = lra_get_allocno_class (i);
    1174                 :            : 
    1175                 :   18239300 :         if ((WORDS_BIG_ENDIAN
    1176                 :            :              && (hard_regno - nregs_diff < 0
    1177                 :            :                  || !TEST_HARD_REG_BIT (reg_class_contents[rclass],
    1178                 :            :                                         hard_regno - nregs_diff)))
    1179                 :            :             || (!WORDS_BIG_ENDIAN
    1180                 :   18239300 :                 && (hard_regno + nregs_diff >= FIRST_PSEUDO_REGISTER
    1181                 :   18239300 :                     || !TEST_HARD_REG_BIT (reg_class_contents[rclass],
    1182                 :            :                                            hard_regno + nregs_diff))))
    1183                 :            :           {
    1184                 :            :             /* Hard registers of paradoxical sub-registers are out of
    1185                 :            :                range of pseudo register class.  Spill the pseudo.  */
    1186                 :          0 :             reg_renumber[i] = -1;
    1187                 :          0 :             continue;
    1188                 :            :           }
    1189                 :   18239300 :         sorted_pseudos[n++] = i;
    1190                 :            :       }
    1191                 :     949914 :   qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
    1192                 :     949914 :   if (pic_offset_table_rtx != NULL_RTX
    1193                 :      36353 :       && (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
    1194                 :     986267 :       && reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
    1195                 :      32526 :     sorted_pseudos[n++] = regno;
    1196                 :   19221700 :   for (i = n - 1; i >= 0; i--)
    1197                 :            :     {
    1198                 :   18271800 :       regno = sorted_pseudos[i];
    1199                 :   18271800 :       hard_regno = reg_renumber[regno];
    1200                 :   18271800 :       lra_assert (hard_regno >= 0);
    1201                 :   18271800 :       mode = lra_reg_info[regno].biggest_mode;
    1202                 :   18271800 :       sparseset_clear (live_range_hard_reg_pseudos);
    1203                 :   39174100 :       for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
    1204                 :            :         {
    1205                 :   45475400 :           EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
    1206                 :   24573100 :             sparseset_set_bit (live_range_hard_reg_pseudos, k);
    1207                 :  150047000 :           for (p = r->start + 1; p <= r->finish; p++)
    1208                 :            :             {
    1209                 :  129145000 :               lra_live_range_t r2;
    1210                 :            : 
    1211                 :  129145000 :               for (r2 = start_point_ranges[p];
    1212                 :  197708000 :                    r2 != NULL;
    1213                 :   68563200 :                    r2 = r2->start_next)
    1214                 :   68563200 :                 if (live_pseudos_reg_renumber[r2->regno] >= 0)
    1215                 :   34447300 :                   sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
    1216                 :            :             }
    1217                 :            :         }
    1218                 :   18271800 :       conflict_set = lra_no_alloc_regs;
    1219                 :   18271800 :       conflict_set |= lra_reg_info[regno].conflict_hard_regs;
    1220                 :   18271800 :       val = lra_reg_info[regno].val;
    1221                 :   18271800 :       offset = lra_reg_info[regno].offset;
    1222                 :  119680000 :       EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
    1223                 :   50704100 :         if (!lra_reg_val_equal_p (conflict_regno, val, offset)
    1224                 :            :             /* If it is multi-register pseudos they should start on
    1225                 :            :                the same hard register.  */
    1226                 :      52629 :             || hard_regno != reg_renumber[conflict_regno])
    1227                 :            :           {
    1228                 :   50655800 :             int conflict_hard_regno = reg_renumber[conflict_regno];
    1229                 :            :             
    1230                 :   50655800 :             biggest_mode = lra_reg_info[conflict_regno].biggest_mode;
    1231                 :   50655800 :             biggest_nregs = hard_regno_nregs (conflict_hard_regno,
    1232                 :            :                                               biggest_mode);
    1233                 :   50655800 :             nregs_diff
    1234                 :   50655800 :               = (biggest_nregs
    1235                 :   50655800 :                  - hard_regno_nregs (conflict_hard_regno,
    1236                 :   50655800 :                                      PSEUDO_REGNO_MODE (conflict_regno)));
    1237                 :  101360000 :             add_to_hard_reg_set (&conflict_set,
    1238                 :            :                                  biggest_mode,
    1239                 :            :                                  conflict_hard_regno
    1240                 :            :                                  - (WORDS_BIG_ENDIAN ? nregs_diff : 0));
    1241                 :            :           }
    1242                 :   36539400 :       if (! overlaps_hard_reg_set_p (conflict_set, mode, hard_regno))
    1243                 :            :         {
    1244                 :   18263700 :           update_lives (regno, false);
    1245                 :   18263700 :           continue;
    1246                 :            :         }
    1247                 :       8123 :       bitmap_set_bit (spilled_pseudo_bitmap, regno);
    1248                 :       8123 :       for (j = 0;
    1249                 :      23491 :            j < hard_regno_nregs (hard_regno, PSEUDO_REGNO_MODE (regno));
    1250                 :            :            j++)
    1251                 :      15368 :         lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
    1252                 :       8123 :       reg_renumber[regno] = -1;
    1253                 :       8123 :       if (regno >= lra_constraint_new_regno_start)
    1254                 :          0 :         former_reload_pseudo_spill_p = true;
    1255                 :       8123 :       if (lra_dump_file != NULL)
    1256                 :          0 :         fprintf (lra_dump_file, "    Spill r%d after risky transformations\n",
    1257                 :            :                  regno);
    1258                 :            :     }
    1259                 :            : }
    1260                 :            : 
    1261                 :            : /* Improve allocation by assigning the same hard regno of inheritance
    1262                 :            :    pseudos to the connected pseudos.  We need this because inheritance
    1263                 :            :    pseudos are allocated after reload pseudos in the thread and when
    1264                 :            :    we assign a hard register to a reload pseudo we don't know yet that
    1265                 :            :    the connected inheritance pseudos can get the same hard register.
    1266                 :            :    Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS.  */
    1267                 :            : static void
    1268                 :     984870 : improve_inheritance (bitmap changed_pseudos)
    1269                 :            : {
    1270                 :     984870 :   unsigned int k;
    1271                 :     984870 :   int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
    1272                 :     984870 :   lra_copy_t cp, next_cp;
    1273                 :     984870 :   bitmap_iterator bi;
    1274                 :            : 
    1275                 :     984870 :   if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
    1276                 :       1377 :     return;
    1277                 :     983493 :   n = 0;
    1278                 :    2295820 :   EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
    1279                 :    1312330 :     if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
    1280                 :     920126 :       sorted_pseudos[n++] = k;
    1281                 :     983493 :   qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
    1282                 :    1903620 :   for (i = 0; i < n; i++)
    1283                 :            :     {
    1284                 :     920126 :       regno = sorted_pseudos[i];
    1285                 :     920126 :       hard_regno = reg_renumber[regno];
    1286                 :     920126 :       lra_assert (hard_regno >= 0);
    1287                 :    2757080 :       for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
    1288                 :            :         {
    1289                 :    1836960 :           if (cp->regno1 == regno)
    1290                 :            :             {
    1291                 :     366429 :               next_cp = cp->regno1_next;
    1292                 :     366429 :               another_regno = cp->regno2;
    1293                 :            :             }
    1294                 :    1470530 :           else if (cp->regno2 == regno)
    1295                 :            :             {
    1296                 :    1470530 :               next_cp = cp->regno2_next;
    1297                 :    1470530 :               another_regno = cp->regno1;
    1298                 :            :             }
    1299                 :            :           else
    1300                 :          0 :             gcc_unreachable ();
    1301                 :            :           /* Don't change reload pseudo allocation.  It might have
    1302                 :            :              this allocation for a purpose and changing it can result
    1303                 :            :              in LRA cycling.  */
    1304                 :    1836960 :           if ((another_regno < lra_constraint_new_regno_start
    1305                 :    1836960 :                || bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
    1306                 :     714551 :               && (another_hard_regno = reg_renumber[another_regno]) >= 0
    1307                 :    2476990 :               && another_hard_regno != hard_regno)
    1308                 :            :             {
    1309                 :      55842 :               if (lra_dump_file != NULL)
    1310                 :          7 :                 fprintf
    1311                 :          7 :                   (lra_dump_file,
    1312                 :            :                    "       Improving inheritance for %d(%d) and %d(%d)...\n",
    1313                 :            :                    regno, hard_regno, another_regno, another_hard_regno);
    1314                 :      55842 :               update_lives (another_regno, true);
    1315                 :      55842 :               lra_setup_reg_renumber (another_regno, -1, false);
    1316                 :      55842 :               if (hard_regno == find_hard_regno_for (another_regno, &cost,
    1317                 :            :                                                      hard_regno, false))
    1318                 :      18840 :                 assign_hard_regno (hard_regno, another_regno);
    1319                 :            :               else
    1320                 :      37002 :                 assign_hard_regno (another_hard_regno, another_regno);
    1321                 :      55842 :               bitmap_set_bit (changed_pseudos, another_regno);
    1322                 :            :             }
    1323                 :            :         }
    1324                 :            :     }
    1325                 :            : }
    1326                 :            : 
    1327                 :            : 
    1328                 :            : /* Bitmap finally containing all pseudos spilled on this assignment
    1329                 :            :    pass.  */
    1330                 :            : static bitmap_head all_spilled_pseudos;
    1331                 :            : /* All pseudos whose allocation was changed.  */
    1332                 :            : static bitmap_head changed_pseudo_bitmap;
    1333                 :            : 
    1334                 :            : 
    1335                 :            : /* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
    1336                 :            :    REGNO and whose hard regs can be assigned to REGNO.  */
    1337                 :            : static void
    1338                 :         14 : find_all_spills_for (int regno)
    1339                 :            : {
    1340                 :         14 :   int p;
    1341                 :         14 :   lra_live_range_t r;
    1342                 :         14 :   unsigned int k;
    1343                 :         14 :   bitmap_iterator bi;
    1344                 :         14 :   enum reg_class rclass;
    1345                 :         14 :   bool *rclass_intersect_p;
    1346                 :            : 
    1347                 :         14 :   rclass = regno_allocno_class_array[regno];
    1348                 :         14 :   rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
    1349                 :         28 :   for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
    1350                 :            :     {
    1351                 :        144 :       EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
    1352                 :        130 :         if (rclass_intersect_p[regno_allocno_class_array[k]])
    1353                 :        130 :           sparseset_set_bit (live_range_hard_reg_pseudos, k);
    1354                 :         28 :       for (p = r->start + 1; p <= r->finish; p++)
    1355                 :            :         {
    1356                 :         14 :           lra_live_range_t r2;
    1357                 :            : 
    1358                 :         14 :           for (r2 = start_point_ranges[p];
    1359                 :         14 :                r2 != NULL;
    1360                 :          0 :                r2 = r2->start_next)
    1361                 :            :             {
    1362                 :          0 :               if (live_pseudos_reg_renumber[r2->regno] >= 0
    1363                 :          0 :                   && ! sparseset_bit_p (live_range_hard_reg_pseudos, r2->regno)
    1364                 :          0 :                   && rclass_intersect_p[regno_allocno_class_array[r2->regno]]
    1365                 :          0 :                   && ((int) r2->regno < lra_constraint_new_regno_start
    1366                 :          0 :                       || bitmap_bit_p (&lra_inheritance_pseudos, r2->regno)
    1367                 :          0 :                       || bitmap_bit_p (&lra_split_regs, r2->regno)
    1368                 :          0 :                       || bitmap_bit_p (&lra_optional_reload_pseudos, r2->regno)
    1369                 :            :                       /* There is no sense to consider another reload
    1370                 :            :                          pseudo if it has the same class.  */
    1371                 :          0 :                       || regno_allocno_class_array[r2->regno] != rclass))
    1372                 :          0 :                 sparseset_set_bit (live_range_hard_reg_pseudos, r2->regno);
    1373                 :            :             }
    1374                 :            :         }
    1375                 :            :     }
    1376                 :         14 : }
    1377                 :            : 
    1378                 :            : /* Assign hard registers to reload pseudos and other pseudos.  Return
    1379                 :            :    true if we was not able to assign hard registers to all reload
    1380                 :            :    pseudos.  */
    1381                 :            : static bool
    1382                 :     984870 : assign_by_spills (void)
    1383                 :            : {
    1384                 :     984870 :   int i, n, nfails, iter, regno, regno2, hard_regno, cost;
    1385                 :     984870 :   rtx restore_rtx;
    1386                 :     984870 :   bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
    1387                 :     984870 :   unsigned int u, conflict_regno;
    1388                 :     984870 :   bitmap_iterator bi;
    1389                 :     984870 :   bool reload_p, fails_p = false;
    1390                 :     984870 :   int max_regno = max_reg_num ();
    1391                 :            : 
    1392                 :    9423840 :   for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
    1393                 :    8438970 :     if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
    1394                 :    5307310 :         && regno_allocno_class_array[i] != NO_REGS)
    1395                 :    4912730 :       sorted_pseudos[n++] = i;
    1396                 :     984870 :   bitmap_initialize (&insn_conflict_pseudos, &reg_obstack);
    1397                 :     984870 :   bitmap_initialize (&spill_pseudos_bitmap, &reg_obstack);
    1398                 :     984870 :   bitmap_initialize (&best_spill_pseudos_bitmap, &reg_obstack);
    1399                 :     984870 :   update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
    1400                 :     984870 :   curr_update_hard_regno_preference_check = 0;
    1401                 :     984870 :   memset (try_hard_reg_pseudos_check, 0, sizeof (try_hard_reg_pseudos_check));
    1402                 :   75835000 :   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    1403                 :   74850100 :     bitmap_initialize (&try_hard_reg_pseudos[i], &reg_obstack);
    1404                 :     984870 :   curr_pseudo_check = 0;
    1405                 :     984870 :   bitmap_initialize (&changed_insns, &reg_obstack);
    1406                 :     984870 :   bitmap_initialize (&non_reload_pseudos, &reg_obstack);
    1407                 :     984870 :   bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
    1408                 :     984870 :   bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
    1409                 :     984870 :   bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
    1410                 :     984884 :   for (iter = 0; iter <= 1; iter++)
    1411                 :            :     {
    1412                 :     984884 :       qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
    1413                 :     984884 :       nfails = 0;
    1414                 :    5897890 :       for (i = 0; i < n; i++)
    1415                 :            :         {
    1416                 :    4913000 :           regno = sorted_pseudos[i];
    1417                 :    4913000 :           if (reg_renumber[regno] >= 0)
    1418                 :        109 :             continue;
    1419                 :    4912900 :           if (lra_dump_file != NULL)
    1420                 :        476 :             fprintf (lra_dump_file, "       Assigning to %d "
    1421                 :            :                      "(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
    1422                 :        238 :                      regno, reg_class_names[regno_allocno_class_array[regno]],
    1423                 :        238 :                      ORIGINAL_REGNO (regno_reg_rtx[regno]),
    1424                 :        238 :                      lra_reg_info[regno].freq, regno_assign_info[regno].first,
    1425                 :        238 :                      regno_assign_info[regno_assign_info[regno].first].freq);
    1426                 :    4912900 :           hard_regno = find_hard_regno_for (regno, &cost, -1, iter == 1);
    1427                 :    4912900 :           reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
    1428                 :    4912900 :           if (hard_regno < 0 && reload_p)
    1429                 :      23153 :             hard_regno = spill_for (regno, &all_spilled_pseudos, iter == 1);
    1430                 :    4912900 :           if (hard_regno < 0)
    1431                 :            :             {
    1432                 :     309855 :               if (reload_p) {
    1433                 :            :                 /* Put unassigned reload pseudo first in the
    1434                 :            :                    array.  */
    1435                 :         26 :                 regno2 = sorted_pseudos[nfails];
    1436                 :         26 :                 sorted_pseudos[nfails++] = regno;
    1437                 :         26 :                 sorted_pseudos[i] = regno2;
    1438                 :            :               }
    1439                 :            :             }
    1440                 :            :           else
    1441                 :            :             {
    1442                 :            :               /* This register might have been spilled by the previous
    1443                 :            :                  pass.  Indicate that it is no longer spilled.  */
    1444                 :    4603040 :               bitmap_clear_bit (&all_spilled_pseudos, regno);
    1445                 :    4603040 :               assign_hard_regno (hard_regno, regno);
    1446                 :    4603040 :               if (! reload_p)
    1447                 :            :                 /* As non-reload pseudo assignment is changed we
    1448                 :            :                    should reconsider insns referring for the
    1449                 :            :                    pseudo.  */
    1450                 :    1043800 :                 bitmap_set_bit (&changed_pseudo_bitmap, regno);
    1451                 :            :             }
    1452                 :            :         }
    1453                 :     984884 :       if (nfails == 0 || iter > 0)
    1454                 :            :         {
    1455                 :     984870 :           fails_p = nfails != 0;
    1456                 :     984870 :           break;
    1457                 :            :         }
    1458                 :            :       /* This is a very rare event.  We cannot assign a hard register
    1459                 :            :          to reload pseudo because the hard register was assigned to
    1460                 :            :          another reload pseudo on a previous assignment pass.  For x86
    1461                 :            :          example, on the 1st pass we assigned CX (although another
    1462                 :            :          hard register could be used for this) to reload pseudo in an
    1463                 :            :          insn, on the 2nd pass we need CX (and only this) hard
    1464                 :            :          register for a new reload pseudo in the same insn.  Another
    1465                 :            :          possible situation may occur in assigning to multi-regs
    1466                 :            :          reload pseudos when hard regs pool is too fragmented even
    1467                 :            :          after spilling non-reload pseudos.
    1468                 :            : 
    1469                 :            :          We should do something radical here to succeed.  Here we
    1470                 :            :          spill *all* conflicting pseudos and reassign them.  */
    1471                 :         14 :       if (lra_dump_file != NULL)
    1472                 :          0 :         fprintf (lra_dump_file, "  2nd iter for reload pseudo assignments:\n");
    1473                 :         14 :       sparseset_clear (live_range_hard_reg_pseudos);
    1474                 :         28 :       for (i = 0; i < nfails; i++)
    1475                 :            :         {
    1476                 :         14 :           if (lra_dump_file != NULL)
    1477                 :          0 :             fprintf (lra_dump_file, "       Reload r%d assignment failure\n",
    1478                 :          0 :                      sorted_pseudos[i]);
    1479                 :         14 :           find_all_spills_for (sorted_pseudos[i]);
    1480                 :            :         }
    1481                 :        274 :       EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
    1482                 :            :         {
    1483                 :        130 :           if ((int) conflict_regno >= lra_constraint_new_regno_start)
    1484                 :            :             {
    1485                 :         98 :               sorted_pseudos[nfails++] = conflict_regno;
    1486                 :         98 :               former_reload_pseudo_spill_p = true;
    1487                 :            :             }
    1488                 :            :           else
    1489                 :            :             /* It is better to do reloads before spilling as after the
    1490                 :            :                spill-subpass we will reload memory instead of pseudos
    1491                 :            :                and this will make reusing reload pseudos more
    1492                 :            :                complicated.  Going directly to the spill pass in such
    1493                 :            :                case might result in worse code performance or even LRA
    1494                 :            :                cycling if we have few registers.  */
    1495                 :         32 :             bitmap_set_bit (&all_spilled_pseudos, conflict_regno);
    1496                 :        130 :           if (lra_dump_file != NULL)
    1497                 :          0 :             fprintf (lra_dump_file, "        Spill %s r%d(hr=%d, freq=%d)\n",
    1498                 :            :                      pseudo_prefix_title (conflict_regno), conflict_regno,
    1499                 :          0 :                      reg_renumber[conflict_regno],
    1500                 :          0 :                      lra_reg_info[conflict_regno].freq);
    1501                 :        130 :           update_lives (conflict_regno, true);
    1502                 :        130 :           lra_setup_reg_renumber (conflict_regno, -1, false);
    1503                 :            :         }
    1504                 :         14 :       if (n < nfails)
    1505                 :            :         n = nfails;
    1506                 :            :     }
    1507                 :     984870 :   improve_inheritance (&changed_pseudo_bitmap);
    1508                 :     984870 :   bitmap_clear (&non_reload_pseudos);
    1509                 :     984870 :   bitmap_clear (&changed_insns);
    1510                 :     984870 :   if (! lra_simple_p)
    1511                 :            :     {
    1512                 :            :       /* We should not assign to original pseudos of inheritance
    1513                 :            :          pseudos or split pseudos if any its inheritance pseudo did
    1514                 :            :          not get hard register or any its split pseudo was not split
    1515                 :            :          because undo inheritance/split pass will extend live range of
    1516                 :            :          such inheritance or split pseudos.  */
    1517                 :     984863 :       bitmap_initialize (&do_not_assign_nonreload_pseudos, &reg_obstack);
    1518                 :    2406130 :       EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
    1519                 :    1421270 :         if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
    1520                 :     795467 :             && REG_P (restore_rtx)
    1521                 :     787095 :             && reg_renumber[u] < 0
    1522                 :    1701770 :             && bitmap_bit_p (&lra_inheritance_pseudos, u))
    1523                 :     280503 :           bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
    1524                 :    1386260 :       EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
    1525                 :     401394 :         if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
    1526                 :     401394 :             && reg_renumber[u] >= 0)
    1527                 :            :           {
    1528                 :        507 :             lra_assert (REG_P (restore_rtx));
    1529                 :        507 :             bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
    1530                 :            :           }
    1531                 :   61679900 :       for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    1532                 :   60695000 :         if (((i < lra_constraint_new_regno_start
    1533                 :   52256000 :               && ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
    1534                 :    8613160 :              || (bitmap_bit_p (&lra_inheritance_pseudos, i)
    1535                 :    1421270 :                  && lra_reg_info[i].restore_rtx != NULL_RTX)
    1536                 :    7817690 :              || (bitmap_bit_p (&lra_split_regs, i)
    1537                 :     401394 :                  && lra_reg_info[i].restore_rtx != NULL_RTX)
    1538                 :    7571360 :              || bitmap_bit_p (&lra_subreg_reload_pseudos, i)
    1539                 :    7569940 :              || bitmap_bit_p (&lra_optional_reload_pseudos, i))
    1540                 :   54077900 :             && reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
    1541                 :   62125900 :             && regno_allocno_class_array[i] != NO_REGS)
    1542                 :    1148820 :           sorted_pseudos[n++] = i;
    1543                 :     984863 :       bitmap_clear (&do_not_assign_nonreload_pseudos);
    1544                 :     984863 :       if (n != 0 && lra_dump_file != NULL)
    1545                 :         14 :         fprintf (lra_dump_file, "  Reassigning non-reload pseudos\n");
    1546                 :     984863 :       qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
    1547                 :    2133690 :       for (i = 0; i < n; i++)
    1548                 :            :         {
    1549                 :    1148820 :           regno = sorted_pseudos[i];
    1550                 :    1148820 :           hard_regno = find_hard_regno_for (regno, &cost, -1, false);
    1551                 :    1148820 :           if (hard_regno >= 0)
    1552                 :            :             {
    1553                 :      50684 :               assign_hard_regno (hard_regno, regno);
    1554                 :            :               /* We change allocation for non-reload pseudo on this
    1555                 :            :                  iteration -- mark the pseudo for invalidation of used
    1556                 :            :                  alternatives of insns containing the pseudo.  */
    1557                 :      50684 :               bitmap_set_bit (&changed_pseudo_bitmap, regno);
    1558                 :            :             }
    1559                 :            :           else
    1560                 :            :             {
    1561                 :    1098140 :               enum reg_class rclass = lra_get_allocno_class (regno);
    1562                 :    1098140 :               enum reg_class spill_class;
    1563                 :            :               
    1564                 :    2196280 :               if (targetm.spill_class == NULL
    1565                 :    1098140 :                   || lra_reg_info[regno].restore_rtx == NULL_RTX
    1566                 :     287511 :                   || ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
    1567                 :    1098140 :                   || (spill_class
    1568                 :     268599 :                       = ((enum reg_class)
    1569                 :     268599 :                          targetm.spill_class
    1570                 :     268599 :                          ((reg_class_t) rclass,
    1571                 :     268599 :                           PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
    1572                 :    1098140 :                 continue;
    1573                 :          0 :               regno_allocno_class_array[regno] = spill_class;
    1574                 :          0 :               hard_regno = find_hard_regno_for (regno, &cost, -1, false);
    1575                 :          0 :               if (hard_regno < 0)
    1576                 :          0 :                 regno_allocno_class_array[regno] = rclass;
    1577                 :            :               else
    1578                 :            :                 {
    1579                 :          0 :                   setup_reg_classes
    1580                 :          0 :                     (regno, spill_class, spill_class, spill_class);
    1581                 :          0 :                   assign_hard_regno (hard_regno, regno);
    1582                 :          0 :                   bitmap_set_bit (&changed_pseudo_bitmap, regno);
    1583                 :            :                 }
    1584                 :            :             }
    1585                 :            :         }
    1586                 :            :     }
    1587                 :     984870 :   free (update_hard_regno_preference_check);
    1588                 :     984870 :   bitmap_clear (&best_spill_pseudos_bitmap);
    1589                 :     984870 :   bitmap_clear (&spill_pseudos_bitmap);
    1590                 :     984870 :   bitmap_clear (&insn_conflict_pseudos);
    1591                 :     984870 :   return fails_p;
    1592                 :            : }
    1593                 :            : 
    1594                 :            : /* Entry function to assign hard registers to new reload pseudos
    1595                 :            :    starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
    1596                 :            :    of old pseudos) and possibly to the old pseudos.  The function adds
    1597                 :            :    what insns to process for the next constraint pass.  Those are all
    1598                 :            :    insns who contains non-reload and non-inheritance pseudos with
    1599                 :            :    changed allocation.
    1600                 :            : 
    1601                 :            :    Return true if we did not spill any non-reload and non-inheritance
    1602                 :            :    pseudos.  Set up FAILS_P if we failed to assign hard registers to
    1603                 :            :    all reload pseudos.  */
    1604                 :            : bool
    1605                 :     984870 : lra_assign (bool &fails_p)
    1606                 :            : {
    1607                 :     984870 :   int i;
    1608                 :     984870 :   unsigned int u;
    1609                 :     984870 :   bitmap_iterator bi;
    1610                 :     984870 :   bitmap_head insns_to_process;
    1611                 :     984870 :   bool no_spills_p;
    1612                 :     984870 :   int max_regno = max_reg_num ();
    1613                 :            : 
    1614                 :     984870 :   timevar_push (TV_LRA_ASSIGN);
    1615                 :     984870 :   lra_assignment_iter++;
    1616                 :     984870 :   if (lra_dump_file != NULL)
    1617                 :        116 :     fprintf (lra_dump_file, "\n********** Assignment #%d: **********\n\n",
    1618                 :            :              lra_assignment_iter);
    1619                 :     984870 :   init_lives ();
    1620                 :     984870 :   sorted_pseudos = XNEWVEC (int, max_regno);
    1621                 :     984870 :   sorted_reload_pseudos = XNEWVEC (int, max_regno);
    1622                 :     984870 :   regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
    1623                 :     984870 :   regno_live_length = XNEWVEC (int, max_regno);
    1624                 :   61876300 :   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    1625                 :            :     {
    1626                 :   60891400 :       int l;
    1627                 :   60891400 :       lra_live_range_t r;
    1628                 :            : 
    1629                 :   60891400 :       regno_allocno_class_array[i] = lra_get_allocno_class (i);
    1630                 :   96409600 :       for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
    1631                 :   35518200 :         l  += r->finish - r->start + 1;
    1632                 :   60891400 :       regno_live_length[i] = l;
    1633                 :            :     }
    1634                 :     984870 :   former_reload_pseudo_spill_p = false;
    1635                 :     984870 :   init_regno_assign_info ();
    1636                 :     984870 :   bitmap_initialize (&all_spilled_pseudos, &reg_obstack);
    1637                 :     984870 :   create_live_range_start_chains ();
    1638                 :     984870 :   setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
    1639                 :     984870 :   if (! lra_asm_error_p && flag_checking)
    1640                 :            :     /* Check correctness of allocation for call-crossed pseudos but
    1641                 :            :        only when there are no asm errors as in the case of errors the
    1642                 :            :        asm is removed and it can result in incorrect allocation.  */
    1643                 :   61875800 :     for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    1644                 :   60891000 :       if (lra_reg_info[i].nrefs != 0
    1645                 :   30625000 :           && reg_renumber[i] >= 0
    1646                 :   85288600 :           && overlaps_hard_reg_set_p (lra_reg_info[i].conflict_hard_regs,
    1647                 :   24397600 :                                       PSEUDO_REGNO_MODE (i), reg_renumber[i]))
    1648                 :          0 :         gcc_unreachable ();
    1649                 :            :   /* Setup insns to process on the next constraint pass.  */
    1650                 :     984870 :   bitmap_initialize (&changed_pseudo_bitmap, &reg_obstack);
    1651                 :     984870 :   init_live_reload_and_inheritance_pseudos ();
    1652                 :     984870 :   fails_p = assign_by_spills ();
    1653                 :     984870 :   finish_live_reload_and_inheritance_pseudos ();
    1654                 :     984870 :   bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
    1655                 :     984870 :   no_spills_p = true;
    1656                 :     985066 :   EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
    1657                 :            :     /* We ignore spilled pseudos created on last inheritance pass
    1658                 :            :        because they will be removed.  */
    1659                 :      17675 :     if (lra_reg_info[u].restore_rtx == NULL_RTX)
    1660                 :            :       {
    1661                 :            :         no_spills_p = false;
    1662                 :            :         break;
    1663                 :            :       }
    1664                 :     984870 :   finish_live_range_start_chains ();
    1665                 :     984870 :   bitmap_clear (&all_spilled_pseudos);
    1666                 :     984870 :   bitmap_initialize (&insns_to_process, &reg_obstack);
    1667                 :    2114670 :   EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
    1668                 :    1129800 :     bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
    1669                 :     984870 :   bitmap_clear (&changed_pseudo_bitmap);
    1670                 :    3635720 :   EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
    1671                 :            :     {
    1672                 :    2650840 :       lra_push_insn_by_uid (u);
    1673                 :            :       /* Invalidate alternatives for insn should be processed.  */
    1674                 :    2650840 :       lra_set_used_insn_alternative_by_uid (u, -1);
    1675                 :            :     }
    1676                 :     984870 :   bitmap_clear (&insns_to_process);
    1677                 :     984870 :   finish_regno_assign_info ();
    1678                 :     984870 :   free (regno_live_length);
    1679                 :     984870 :   free (regno_allocno_class_array);
    1680                 :     984870 :   free (sorted_pseudos);
    1681                 :     984870 :   free (sorted_reload_pseudos);
    1682                 :     984870 :   finish_lives ();
    1683                 :     984870 :   timevar_pop (TV_LRA_ASSIGN);
    1684                 :     984870 :   if (former_reload_pseudo_spill_p)
    1685                 :        643 :     lra_assignment_iter_after_spill++;
    1686                 :            :   /* This is conditional on flag_checking because valid code can take
    1687                 :            :      more than this maximum number of iteration, but at the same time
    1688                 :            :      the test can uncover errors in machine descriptions.  */
    1689                 :     984870 :   if (flag_checking
    1690                 :     984858 :       && (lra_assignment_iter_after_spill
    1691                 :     984858 :           > LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
    1692                 :          0 :     internal_error
    1693                 :          0 :       ("maximum number of LRA assignment passes is achieved (%d)",
    1694                 :            :        LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
    1695                 :            :   /* Reset the assignment correctness flag: */
    1696                 :     984870 :   check_and_force_assignment_correctness_p = false;
    1697                 :     984870 :   return no_spills_p;
    1698                 :            : }
    1699                 :            : 
    1700                 :            : /* Find start and finish insns for reload pseudo REGNO.  Return true
    1701                 :            :    if we managed to find the expected insns.  Return false,
    1702                 :            :    otherwise.  */
    1703                 :            : static bool
    1704                 :         12 : find_reload_regno_insns (int regno, rtx_insn * &start, rtx_insn * &finish)
    1705                 :            : {
    1706                 :         12 :   unsigned int uid;
    1707                 :         12 :   bitmap_iterator bi;
    1708                 :         12 :   int n = 0;
    1709                 :         12 :   rtx_insn *prev_insn, *next_insn;
    1710                 :         12 :   rtx_insn *start_insn = NULL, *first_insn = NULL, *second_insn = NULL;
    1711                 :            :   
    1712                 :         37 :   EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
    1713                 :            :     {
    1714                 :         25 :       if (start_insn == NULL)
    1715                 :         12 :         start_insn = lra_insn_recog_data[uid]->insn;
    1716                 :         25 :       n++;
    1717                 :            :     }
    1718                 :            :   /* For reload pseudo we should have at most 3 insns referring for it:
    1719                 :            :      input/output reload insns and the original insn.  */
    1720                 :         12 :   if (n > 3)
    1721                 :            :     return false;
    1722                 :         12 :   if (n > 1)
    1723                 :            :     {
    1724                 :         12 :       for (prev_insn = PREV_INSN (start_insn),
    1725                 :         12 :              next_insn = NEXT_INSN (start_insn);
    1726                 :         26 :            n != 1 && (prev_insn != NULL || next_insn != NULL); )
    1727                 :            :         {
    1728                 :         14 :           if (prev_insn != NULL && first_insn == NULL)
    1729                 :            :             {
    1730                 :         28 :               if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
    1731                 :         14 :                                   INSN_UID (prev_insn)))
    1732                 :          3 :                 prev_insn = PREV_INSN (prev_insn);
    1733                 :            :               else
    1734                 :            :                 {
    1735                 :         11 :                   first_insn = prev_insn;
    1736                 :         11 :                   n--;
    1737                 :            :                 }
    1738                 :            :             }
    1739                 :         14 :           if (next_insn != NULL && second_insn == NULL)
    1740                 :            :             {
    1741                 :         28 :               if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
    1742                 :         14 :                                 INSN_UID (next_insn)))
    1743                 :         12 :                 next_insn = NEXT_INSN (next_insn);
    1744                 :            :               else
    1745                 :            :                 {
    1746                 :          2 :                   second_insn = next_insn;
    1747                 :          2 :                   n--;
    1748                 :            :                 }
    1749                 :            :             }
    1750                 :            :         }
    1751                 :         12 :       if (n > 1)
    1752                 :            :         return false;
    1753                 :            :     }
    1754                 :         12 :   start = first_insn != NULL ? first_insn : start_insn;
    1755                 :         12 :   finish = second_insn != NULL ? second_insn : start_insn;
    1756                 :         12 :   return true;
    1757                 :            : }
    1758                 :            : 
    1759                 :            : /* Process reload pseudos which did not get a hard reg, split a hard
    1760                 :            :    reg live range in live range of a reload pseudo, and then return
    1761                 :            :    TRUE.  If we did not split a hard reg live range, report an error,
    1762                 :            :    and return FALSE.  */
    1763                 :            : bool
    1764                 :         10 : lra_split_hard_reg_for (void)
    1765                 :            : {
    1766                 :         10 :   int i, regno;
    1767                 :         10 :   rtx_insn *insn, *first, *last;
    1768                 :         10 :   unsigned int u;
    1769                 :         10 :   bitmap_iterator bi;
    1770                 :         10 :   enum reg_class rclass;
    1771                 :         10 :   int max_regno = max_reg_num ();
    1772                 :            :   /* We did not assign hard regs to reload pseudos after two
    1773                 :            :      iterations.  Either it's an asm and something is wrong with the
    1774                 :            :      constraints, or we have run out of spill registers; error out in
    1775                 :            :      either case.  */
    1776                 :         10 :   bool asm_p = false;
    1777                 :         10 :   bitmap_head failed_reload_insns, failed_reload_pseudos;
    1778                 :            :   
    1779                 :         10 :   if (lra_dump_file != NULL)
    1780                 :          0 :     fprintf (lra_dump_file,
    1781                 :            :              "\n****** Splitting a hard reg after assignment #%d: ******\n\n",
    1782                 :            :              lra_assignment_iter);
    1783                 :         10 :   bitmap_initialize (&failed_reload_pseudos, &reg_obstack);
    1784                 :         10 :   bitmap_initialize (&non_reload_pseudos, &reg_obstack);
    1785                 :         10 :   bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
    1786                 :         10 :   bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
    1787                 :         10 :   bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
    1788                 :        326 :   for (i = lra_constraint_new_regno_start; i < max_regno; i++)
    1789                 :         15 :     if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
    1790                 :         12 :         && (rclass = lra_get_allocno_class (i)) != NO_REGS
    1791                 :        330 :         && ! bitmap_bit_p (&non_reload_pseudos, i))
    1792                 :            :       {
    1793                 :         12 :         if (! find_reload_regno_insns (i, first, last))
    1794                 :          0 :           continue;
    1795                 :         12 :         if (spill_hard_reg_in_range (i, rclass, first, last))
    1796                 :            :           {
    1797                 :          2 :             bitmap_clear (&failed_reload_pseudos);
    1798                 :          2 :             return true;
    1799                 :            :           }
    1800                 :         10 :         bitmap_set_bit (&failed_reload_pseudos, i);
    1801                 :            :       }
    1802                 :          8 :   bitmap_clear (&non_reload_pseudos);
    1803                 :          8 :   bitmap_initialize (&failed_reload_insns, &reg_obstack);
    1804                 :         18 :   EXECUTE_IF_SET_IN_BITMAP (&failed_reload_pseudos, 0, u, bi)
    1805                 :            :     {
    1806                 :         10 :       regno = u;
    1807                 :         10 :       bitmap_ior_into (&failed_reload_insns,
    1808                 :         10 :                        &lra_reg_info[regno].insn_bitmap);
    1809                 :         10 :       lra_setup_reg_renumber
    1810                 :         20 :         (regno, ira_class_hard_regs[lra_get_allocno_class (regno)][0], false);
    1811                 :            :     }
    1812                 :         27 :   EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
    1813                 :            :     {
    1814                 :         19 :       insn = lra_insn_recog_data[u]->insn;
    1815                 :         19 :       if (asm_noperands (PATTERN (insn)) >= 0)
    1816                 :            :         {
    1817                 :          8 :           lra_asm_error_p = asm_p = true;
    1818                 :          8 :           error_for_asm (insn,
    1819                 :            :                          "%<asm%> operand has impossible constraints");
    1820                 :            :           /* Avoid further trouble with this insn.
    1821                 :            :              For asm goto, instead of fixing up all the edges
    1822                 :            :              just clear the template and clear input operands
    1823                 :            :              (asm goto doesn't have any output operands).  */
    1824                 :          8 :           if (JUMP_P (insn))
    1825                 :            :             {
    1826                 :          6 :               rtx asm_op = extract_asm_operands (PATTERN (insn));
    1827                 :          6 :               ASM_OPERANDS_TEMPLATE (asm_op) = ggc_strdup ("");
    1828                 :          6 :               ASM_OPERANDS_INPUT_VEC (asm_op) = rtvec_alloc (0);
    1829                 :          6 :               ASM_OPERANDS_INPUT_CONSTRAINT_VEC (asm_op) = rtvec_alloc (0);
    1830                 :          6 :               lra_update_insn_regno_info (insn);
    1831                 :            :             }
    1832                 :            :           else
    1833                 :            :             {
    1834                 :          2 :               PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
    1835                 :          2 :               lra_set_insn_deleted (insn);
    1836                 :            :             }
    1837                 :            :         }
    1838                 :         11 :       else if (!asm_p)
    1839                 :            :         {
    1840                 :          0 :           error ("unable to find a register to spill");
    1841                 :          0 :           fatal_insn ("this is the insn:", insn);
    1842                 :            :         }
    1843                 :            :     }
    1844                 :          8 :   bitmap_clear (&failed_reload_pseudos);
    1845                 :          8 :   bitmap_clear (&failed_reload_insns);
    1846                 :          8 :   return false;
    1847                 :            : }

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.