LCOV - code coverage report
Current view: top level - gcc - lra-lives.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 642 691 92.9 %
Date: 2020-04-04 11:58:09 Functions: 28 38 73.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Build live ranges for 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 contains code to build pseudo live-ranges (analogous
      23                 :            :    structures used in IRA, so read comments about the live-ranges
      24                 :            :    there) and other info necessary for other passes to assign
      25                 :            :    hard-registers to pseudos, coalesce the spilled pseudos, and assign
      26                 :            :    stack memory slots to spilled pseudos.  */
      27                 :            : 
      28                 :            : #include "config.h"
      29                 :            : #include "system.h"
      30                 :            : #include "coretypes.h"
      31                 :            : #include "backend.h"
      32                 :            : #include "rtl.h"
      33                 :            : #include "tree.h"
      34                 :            : #include "predict.h"
      35                 :            : #include "df.h"
      36                 :            : #include "memmodel.h"
      37                 :            : #include "tm_p.h"
      38                 :            : #include "insn-config.h"
      39                 :            : #include "regs.h"
      40                 :            : #include "ira.h"
      41                 :            : #include "recog.h"
      42                 :            : #include "cfganal.h"
      43                 :            : #include "sparseset.h"
      44                 :            : #include "lra-int.h"
      45                 :            : #include "target.h"
      46                 :            : #include "function-abi.h"
      47                 :            : 
      48                 :            : /* Program points are enumerated by numbers from range
      49                 :            :    0..LRA_LIVE_MAX_POINT-1.  There are approximately two times more
      50                 :            :    program points than insns.  Program points are places in the
      51                 :            :    program where liveness info can be changed.  In most general case
      52                 :            :    (there are more complicated cases too) some program points
      53                 :            :    correspond to places where input operand dies and other ones
      54                 :            :    correspond to places where output operands are born.  */
      55                 :            : int lra_live_max_point;
      56                 :            : 
      57                 :            : /* Accumulated execution frequency of all references for each hard
      58                 :            :    register.  */
      59                 :            : int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
      60                 :            : 
      61                 :            : /* A global flag whose true value says to build live ranges for all
      62                 :            :    pseudos, otherwise the live ranges only for pseudos got memory is
      63                 :            :    build.  True value means also building copies and setting up hard
      64                 :            :    register preferences.  The complete info is necessary only for the
      65                 :            :    assignment pass.  The complete info is not needed for the
      66                 :            :    coalescing and spill passes.  */
      67                 :            : static bool complete_info_p;
      68                 :            : 
      69                 :            : /* Pseudos live at current point in the RTL scan.  */
      70                 :            : static sparseset pseudos_live;
      71                 :            : 
      72                 :            : /* Pseudos probably living through calls and setjumps.  As setjump is
      73                 :            :    a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
      74                 :            :    then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
      75                 :            :    too.  These data are necessary for cases when only one subreg of a
      76                 :            :    multi-reg pseudo is set up after a call.  So we decide it is
      77                 :            :    probably live when traversing bb backward.  We are sure about
      78                 :            :    living when we see its usage or definition of the pseudo.  */
      79                 :            : static sparseset pseudos_live_through_calls;
      80                 :            : static sparseset pseudos_live_through_setjumps;
      81                 :            : 
      82                 :            : /* Set of hard regs (except eliminable ones) currently live.  */
      83                 :            : static HARD_REG_SET hard_regs_live;
      84                 :            : 
      85                 :            : /* Set of pseudos and hard registers start living/dying in the current
      86                 :            :    insn.  These sets are used to update REG_DEAD and REG_UNUSED notes
      87                 :            :    in the insn.  */
      88                 :            : static sparseset start_living, start_dying;
      89                 :            : 
      90                 :            : /* Set of pseudos and hard regs dead and unused in the current
      91                 :            :    insn.  */
      92                 :            : static sparseset unused_set, dead_set;
      93                 :            : 
      94                 :            : /* Bitmap used for holding intermediate bitmap operation results.  */
      95                 :            : static bitmap_head temp_bitmap;
      96                 :            : 
      97                 :            : /* Pool for pseudo live ranges.  */
      98                 :            : static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
      99                 :            : 
     100                 :            : /* Free live range list LR.  */
     101                 :            : static void
     102                 :          0 : free_live_range_list (lra_live_range_t lr)
     103                 :            : {
     104                 :  247535000 :   lra_live_range_t next;
     105                 :            : 
     106                 :  247535000 :   while (lr != NULL)
     107                 :            :     {
     108                 :   60061100 :       next = lr->next;
     109                 :   60061100 :       lra_live_range_pool.remove (lr);
     110                 :   60061100 :       lr = next;
     111                 :            :     }
     112                 :          0 : }
     113                 :            : 
     114                 :            : /* Create and return pseudo live range with given attributes.  */
     115                 :            : static lra_live_range_t
     116                 :   66190800 : create_live_range (int regno, int start, int finish, lra_live_range_t next)
     117                 :            : {
     118                 :          0 :   lra_live_range_t p = lra_live_range_pool.allocate ();
     119                 :   66190800 :   p->regno = regno;
     120                 :   66190800 :   p->start = start;
     121                 :   66190800 :   p->finish = finish;
     122                 :   66190800 :   p->next = next;
     123                 :   66190800 :   return p;
     124                 :            : }
     125                 :            : 
     126                 :            : /* Copy live range R and return the result.  */
     127                 :            : static lra_live_range_t
     128                 :    1196650 : copy_live_range (lra_live_range_t r)
     129                 :            : {
     130                 :          0 :   return new (lra_live_range_pool) lra_live_range (*r);
     131                 :            : }
     132                 :            : 
     133                 :            : /* Copy live range list given by its head R and return the result.  */
     134                 :            : lra_live_range_t
     135                 :     789538 : lra_copy_live_range_list (lra_live_range_t r)
     136                 :            : {
     137                 :     789538 :   lra_live_range_t p, first, *chain;
     138                 :            : 
     139                 :     789538 :   first = NULL;
     140                 :    1986190 :   for (chain = &first; r != NULL; r = r->next)
     141                 :            :     {
     142                 :    1196650 :       p = copy_live_range (r);
     143                 :    1196650 :       *chain = p;
     144                 :    1196650 :       chain = &p->next;
     145                 :            :     }
     146                 :     789538 :   return first;
     147                 :            : }
     148                 :            : 
     149                 :            : /* Merge *non-intersected* ranges R1 and R2 and returns the result.
     150                 :            :    The function maintains the order of ranges and tries to minimize
     151                 :            :    size of the result range list.  Ranges R1 and R2 may not be used
     152                 :            :    after the call.  */
     153                 :            : lra_live_range_t
     154                 :     789538 : lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
     155                 :            : {
     156                 :     789538 :   lra_live_range_t first, last;
     157                 :            : 
     158                 :     789538 :   if (r1 == NULL)
     159                 :            :     return r2;
     160                 :     319588 :   if (r2 == NULL)
     161                 :            :     return r1;
     162                 :    4461420 :   for (first = last = NULL; r1 != NULL && r2 != NULL;)
     163                 :            :     {
     164                 :    4448040 :       if (r1->start < r2->start)
     165                 :     190590 :         std::swap (r1, r2);
     166                 :            : 
     167                 :    4448040 :       if (r1->start == r2->finish + 1)
     168                 :            :         {
     169                 :            :           /* Joint ranges: merge r1 and r2 into r1.  */
     170                 :      33790 :           r1->start = r2->start;
     171                 :      33790 :           lra_live_range_t temp = r2;
     172                 :      33790 :           r2 = r2->next;
     173                 :    4801420 :           lra_live_range_pool.remove (temp);
     174                 :            :         }
     175                 :            :       else
     176                 :            :         {
     177                 :    4414250 :           gcc_assert (r2->finish + 1 < r1->start);
     178                 :            :           /* Add r1 to the result.  */
     179                 :    4414250 :           if (first == NULL)
     180                 :            :             first = last = r1;
     181                 :            :           else
     182                 :            :             {
     183                 :    4098860 :               last->next = r1;
     184                 :    4098860 :               last = r1;
     185                 :            :             }
     186                 :    4414250 :           r1 = r1->next;
     187                 :            :         }
     188                 :            :     }
     189                 :     319588 :   if (r1 != NULL)
     190                 :            :     {
     191                 :      13380 :       if (first == NULL)
     192                 :            :         first = r1;
     193                 :            :       else
     194                 :       9184 :         last->next = r1;
     195                 :            :     }
     196                 :            :   else
     197                 :            :     {
     198                 :     306208 :       lra_assert (r2 != NULL);
     199                 :     306208 :       if (first == NULL)
     200                 :            :         first = r2;
     201                 :            :       else
     202                 :     306208 :         last->next = r2;
     203                 :            :     }
     204                 :            :   return first;
     205                 :            : }
     206                 :            : 
     207                 :            : /* Return TRUE if live ranges R1 and R2 intersect.  */
     208                 :            : bool
     209                 :   30178500 : lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
     210                 :            : {
     211                 :            :   /* Remember the live ranges are always kept ordered.  */
     212                 :   41292800 :   while (r1 != NULL && r2 != NULL)
     213                 :            :     {
     214                 :   40972400 :       if (r1->start > r2->finish)
     215                 :   10298400 :         r1 = r1->next;
     216                 :   30674000 :       else if (r2->start > r1->finish)
     217                 :     815990 :         r2 = r2->next;
     218                 :            :       else
     219                 :            :         return true;
     220                 :            :     }
     221                 :            :   return false;
     222                 :            : }
     223                 :            : 
     224                 :            : enum point_type {
     225                 :            :   DEF_POINT,
     226                 :            :   USE_POINT
     227                 :            : };
     228                 :            : 
     229                 :            : /* Return TRUE if set A contains a pseudo register, otherwise, return FALSE.  */
     230                 :            : static bool
     231                 :  503174000 : sparseset_contains_pseudos_p (sparseset a)
     232                 :            : {
     233                 :  503174000 :   int regno;
     234                 :  592023000 :   EXECUTE_IF_SET_IN_SPARSESET (a, regno)
     235                 :  210016000 :     if (!HARD_REGISTER_NUM_P (regno))
     236                 :            :       return true;
     237                 :            :   return false;
     238                 :            : }
     239                 :            : 
     240                 :            : /* Mark pseudo REGNO as living or dying at program point POINT, depending on
     241                 :            :    whether TYPE is a definition or a use.  If this is the first reference to
     242                 :            :    REGNO that we've encountered, then create a new live range for it.  */
     243                 :            : 
     244                 :            : static void
     245                 :  697830000 : update_pseudo_point (int regno, int point, enum point_type type)
     246                 :            : {
     247                 :  697830000 :   lra_live_range_t p;
     248                 :            : 
     249                 :            :   /* Don't compute points for hard registers.  */
     250                 :  697830000 :   if (HARD_REGISTER_NUM_P (regno))
     251                 :            :     return;
     252                 :            : 
     253                 :  639576000 :   if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
     254                 :            :     {
     255                 :  611700000 :       if (type == DEF_POINT)
     256                 :            :         {
     257                 :  257191000 :           if (sparseset_bit_p (pseudos_live, regno))
     258                 :            :             {
     259                 :  257191000 :               p = lra_reg_info[regno].live_ranges;
     260                 :  257191000 :               lra_assert (p != NULL);
     261                 :  257191000 :               p->finish = point;
     262                 :            :             }
     263                 :            :         }
     264                 :            :       else /* USE_POINT */
     265                 :            :         {
     266                 :  354509000 :           if (!sparseset_bit_p (pseudos_live, regno)
     267                 :  354509000 :               && ((p = lra_reg_info[regno].live_ranges) == NULL
     268                 :  202507000 :                   || (p->finish != point && p->finish + 1 != point)))
     269                 :   66190800 :             lra_reg_info[regno].live_ranges
     270                 :   66190800 :               = create_live_range (regno, point, -1, p);
     271                 :            :         }
     272                 :            :     }
     273                 :            : }
     274                 :            : 
     275                 :            : /* The corresponding bitmaps of BB currently being processed.  */
     276                 :            : static bitmap bb_killed_pseudos, bb_gen_pseudos;
     277                 :            : 
     278                 :            : /* Record hard register REGNO as now being live.  It updates
     279                 :            :    living hard regs and START_LIVING.  */
     280                 :            : static void
     281                 :  145716000 : make_hard_regno_live (int regno)
     282                 :            : {
     283                 :  145716000 :   lra_assert (HARD_REGISTER_NUM_P (regno));
     284                 :  145716000 :   if (TEST_HARD_REG_BIT (hard_regs_live, regno)
     285                 :  145716000 :       || TEST_HARD_REG_BIT (eliminable_regset, regno))
     286                 :            :     return;
     287                 :   77908400 :   SET_HARD_REG_BIT (hard_regs_live, regno);
     288                 :   77908400 :   sparseset_set_bit (start_living, regno);
     289                 :   77908400 :   if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
     290                 :   45279000 :     bitmap_set_bit (bb_gen_pseudos, regno);
     291                 :            : }
     292                 :            : 
     293                 :            : /* Process the definition of hard register REGNO.  This updates
     294                 :            :    hard_regs_live, START_DYING and conflict hard regs for living
     295                 :            :    pseudos.  */
     296                 :            : static void
     297                 :   76273300 : make_hard_regno_dead (int regno)
     298                 :            : {
     299                 :   76273300 :   if (TEST_HARD_REG_BIT (eliminable_regset, regno))
     300                 :            :     return;
     301                 :            : 
     302                 :   76272400 :   lra_assert (HARD_REGISTER_NUM_P (regno));
     303                 :   76272400 :   unsigned int i;
     304                 :  847359000 :   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
     305                 :  771087000 :     SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
     306                 :            : 
     307                 :   76272400 :   if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
     308                 :            :     return;
     309                 :   76272300 :   CLEAR_HARD_REG_BIT (hard_regs_live, regno);
     310                 :   76272300 :   sparseset_set_bit (start_dying, regno);
     311                 :   76272300 :   if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
     312                 :            :     {
     313                 :   45279000 :       bitmap_clear_bit (bb_gen_pseudos, regno);
     314                 :   45279000 :       bitmap_set_bit (bb_killed_pseudos, regno);
     315                 :            :     }
     316                 :            : }
     317                 :            : 
     318                 :            : /* Mark pseudo REGNO as now being live and update START_LIVING.  */
     319                 :            : static void
     320                 :  365080000 : mark_pseudo_live (int regno)
     321                 :            : {
     322                 :  365080000 :   lra_assert (!HARD_REGISTER_NUM_P (regno));
     323                 :  365080000 :   if (sparseset_bit_p (pseudos_live, regno))
     324                 :            :     return;
     325                 :            : 
     326                 :  265398000 :   sparseset_set_bit (pseudos_live, regno);
     327                 :  265398000 :   sparseset_set_bit (start_living, regno);
     328                 :            : }
     329                 :            : 
     330                 :            : /* Mark pseudo REGNO as now being dead and update START_DYING.  */
     331                 :            : static void
     332                 :  265398000 : mark_pseudo_dead (int regno)
     333                 :            : {
     334                 :  265398000 :   lra_assert (!HARD_REGISTER_NUM_P (regno));
     335                 :  265398000 :   lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
     336                 :  265398000 :   if (!sparseset_bit_p (pseudos_live, regno))
     337                 :            :     return;
     338                 :            : 
     339                 :  265398000 :   sparseset_clear_bit (pseudos_live, regno);
     340                 :  265398000 :   sparseset_set_bit (start_dying, regno);
     341                 :            : }
     342                 :            : 
     343                 :            : /* Mark register REGNO (pseudo or hard register) in MODE as being live
     344                 :            :    and update BB_GEN_PSEUDOS.  */
     345                 :            : static void
     346                 :  234805000 : mark_regno_live (int regno, machine_mode mode)
     347                 :            : {
     348                 :  234805000 :   int last;
     349                 :            : 
     350                 :  234805000 :   if (HARD_REGISTER_NUM_P (regno))
     351                 :            :     {
     352                 :  143238000 :       for (last = end_hard_regno (mode, regno); regno < last; regno++)
     353                 :   71826300 :         make_hard_regno_live (regno);
     354                 :            :     }
     355                 :            :   else
     356                 :            :     {
     357                 :  163393000 :       mark_pseudo_live (regno);
     358                 :  163393000 :       bitmap_set_bit (bb_gen_pseudos, regno);
     359                 :            :     }
     360                 :  234805000 : }
     361                 :            : 
     362                 :            : 
     363                 :            : /* Mark register REGNO (pseudo or hard register) in MODE as being dead
     364                 :            :    and update BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS.  */
     365                 :            : static void
     366                 :   94534900 : mark_regno_dead (int regno, machine_mode mode)
     367                 :            : {
     368                 :   94534900 :   int last;
     369                 :            : 
     370                 :   94534900 :   if (HARD_REGISTER_NUM_P (regno))
     371                 :            :     {
     372                 :   52568800 :       for (last = end_hard_regno (mode, regno); regno < last; regno++)
     373                 :   26425100 :         make_hard_regno_dead (regno);
     374                 :            :     }
     375                 :            :   else
     376                 :            :     {
     377                 :   68391300 :       mark_pseudo_dead (regno);
     378                 :   68391300 :       bitmap_clear_bit (bb_gen_pseudos, regno);
     379                 :   68391300 :       bitmap_set_bit (bb_killed_pseudos, regno);
     380                 :            :     }
     381                 :   94534900 : }
     382                 :            : 
     383                 :            : 
     384                 :            : 
     385                 :            : /* This page contains code for making global live analysis of pseudos.
     386                 :            :    The code works only when pseudo live info is changed on a BB
     387                 :            :    border.  That might be a consequence of some global transformations
     388                 :            :    in LRA, e.g. PIC pseudo reuse or rematerialization.  */
     389                 :            : 
     390                 :            : /* Structure describing local BB data used for pseudo
     391                 :            :    live-analysis.  */
     392                 :            : class bb_data_pseudos
     393                 :            : {
     394                 :            : public:
     395                 :            :   /* Basic block about which the below data are.  */
     396                 :            :   basic_block bb;
     397                 :            :   bitmap_head killed_pseudos; /* pseudos killed in the BB.  */
     398                 :            :   bitmap_head gen_pseudos; /* pseudos generated in the BB.  */
     399                 :            : };
     400                 :            : 
     401                 :            : /* Array for all BB data.  Indexed by the corresponding BB index.  */
     402                 :            : typedef class bb_data_pseudos *bb_data_t;
     403                 :            : 
     404                 :            : /* All basic block data are referred through the following array.  */
     405                 :            : static bb_data_t bb_data;
     406                 :            : 
     407                 :            : /* Two small functions for access to the bb data.  */
     408                 :            : static inline bb_data_t
     409                 :   47682400 : get_bb_data (basic_block bb)
     410                 :            : {
     411                 :   47682400 :   return &bb_data[(bb)->index];
     412                 :            : }
     413                 :            : 
     414                 :            : static inline bb_data_t
     415                 :    5260460 : get_bb_data_by_index (int index)
     416                 :            : {
     417                 :    5260460 :   return &bb_data[index];
     418                 :            : }
     419                 :            : 
     420                 :            : /* Bitmap with all hard regs.  */
     421                 :            : static bitmap_head all_hard_regs_bitmap;
     422                 :            : 
     423                 :            : /* The transfer function used by the DF equation solver to propagate
     424                 :            :    live info through block with BB_INDEX according to the following
     425                 :            :    equation:
     426                 :            : 
     427                 :            :      bb.livein = (bb.liveout - bb.kill) OR bb.gen
     428                 :            : */
     429                 :            : static bool
     430                 :    5260460 : live_trans_fun (int bb_index)
     431                 :            : {
     432                 :    5260460 :   basic_block bb = get_bb_data_by_index (bb_index)->bb;
     433                 :    5260460 :   bitmap bb_liveout = df_get_live_out (bb);
     434                 :    5260460 :   bitmap bb_livein = df_get_live_in (bb);
     435                 :    5260460 :   bb_data_t bb_info = get_bb_data (bb);
     436                 :            : 
     437                 :    5260460 :   bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
     438                 :    5260460 :   return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
     439                 :    5260460 :                                &temp_bitmap, &bb_info->killed_pseudos);
     440                 :            : }
     441                 :            : 
     442                 :            : /* The confluence function used by the DF equation solver to set up
     443                 :            :    live info for a block BB without predecessor.  */
     444                 :            : static void
     445                 :     239592 : live_con_fun_0 (basic_block bb)
     446                 :            : {
     447                 :     239592 :   bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
     448                 :     239592 : }
     449                 :            : 
     450                 :            : /* The confluence function used by the DF equation solver to propagate
     451                 :            :    live info from successor to predecessor on edge E according to the
     452                 :            :    following equation:
     453                 :            : 
     454                 :            :       bb.liveout = 0 for entry block | OR (livein of successors)
     455                 :            :  */
     456                 :            : static bool
     457                 :    7668020 : live_con_fun_n (edge e)
     458                 :            : {
     459                 :    7668020 :   basic_block bb = e->src;
     460                 :    7668020 :   basic_block dest = e->dest;
     461                 :    7668020 :   bitmap bb_liveout = df_get_live_out (bb);
     462                 :    7668020 :   bitmap dest_livein = df_get_live_in (dest);
     463                 :            : 
     464                 :    7668020 :   return bitmap_ior_and_compl_into (bb_liveout,
     465                 :    7668020 :                                     dest_livein, &all_hard_regs_bitmap);
     466                 :            : }
     467                 :            : 
     468                 :            : /* Indexes of all function blocks.  */
     469                 :            : static bitmap_head all_blocks;
     470                 :            : 
     471                 :            : /* Allocate and initialize data needed for global pseudo live
     472                 :            :    analysis.  */
     473                 :            : static void
     474                 :     944096 : initiate_live_solver (void)
     475                 :            : {
     476                 :     944096 :   bitmap_initialize (&all_hard_regs_bitmap, &reg_obstack);
     477                 :     944096 :   bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
     478                 :     944096 :   bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
     479                 :     944096 :   bitmap_initialize (&all_blocks, &reg_obstack);
     480                 :            : 
     481                 :     944096 :   basic_block bb;
     482                 :   11954200 :   FOR_ALL_BB_FN (bb, cfun)
     483                 :            :     {
     484                 :   11010100 :       bb_data_t bb_info = get_bb_data (bb);
     485                 :   11010100 :       bb_info->bb = bb;
     486                 :   11010100 :       bitmap_initialize (&bb_info->killed_pseudos, &reg_obstack);
     487                 :   11010100 :       bitmap_initialize (&bb_info->gen_pseudos, &reg_obstack);
     488                 :   11010100 :       bitmap_set_bit (&all_blocks, bb->index);
     489                 :            :     }
     490                 :     944096 : }
     491                 :            : 
     492                 :            : /* Free all data needed for global pseudo live analysis.  */
     493                 :            : static void
     494                 :     944096 : finish_live_solver (void)
     495                 :            : {
     496                 :     944096 :   basic_block bb;
     497                 :            : 
     498                 :     944096 :   bitmap_clear (&all_blocks);
     499                 :   11954200 :   FOR_ALL_BB_FN (bb, cfun)
     500                 :            :     {
     501                 :   11010100 :       bb_data_t bb_info = get_bb_data (bb);
     502                 :   11010100 :       bitmap_clear (&bb_info->killed_pseudos);
     503                 :   11010100 :       bitmap_clear (&bb_info->gen_pseudos);
     504                 :            :     }
     505                 :     944096 :   free (bb_data);
     506                 :     944096 :   bitmap_clear (&all_hard_regs_bitmap);
     507                 :     944096 : }
     508                 :            : 
     509                 :            : 
     510                 :            : 
     511                 :            : /* Insn currently scanned.  */
     512                 :            : static rtx_insn *curr_insn;
     513                 :            : /* The insn data.  */
     514                 :            : static lra_insn_recog_data_t curr_id;
     515                 :            : /* The insn static data.  */
     516                 :            : static struct lra_static_insn_data *curr_static_id;
     517                 :            : 
     518                 :            : /* Vec containing execution frequencies of program points.  */
     519                 :            : static vec<int> point_freq_vec;
     520                 :            : 
     521                 :            : /* The start of the above vector elements.  */
     522                 :            : int *lra_point_freq;
     523                 :            : 
     524                 :            : /* Increment the current program point POINT to the next point which has
     525                 :            :    execution frequency FREQ.  */
     526                 :            : static void
     527                 :  137302000 : next_program_point (int &point, int freq)
     528                 :            : {
     529                 :          0 :   point_freq_vec.safe_push (freq);
     530                 :  137302000 :   lra_point_freq = point_freq_vec.address ();
     531                 :  137302000 :   point++;
     532                 :          0 : }
     533                 :            : 
     534                 :            : /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT.  */
     535                 :            : void
     536                 :    9814140 : lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
     537                 :            :                                               int hard_regno, int profit)
     538                 :            : {
     539                 :    9814140 :   lra_assert (regno >= lra_constraint_new_regno_start);
     540                 :    9814140 :   if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
     541                 :    1771720 :     lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
     542                 :    8042410 :   else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
     543                 :      85920 :     lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
     544                 :    7956490 :   else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
     545                 :            :     {
     546                 :    6356550 :       lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
     547                 :    6356550 :       lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
     548                 :            :     }
     549                 :    1599940 :   else if (lra_reg_info[regno].preferred_hard_regno2 < 0
     550                 :      50842 :            || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
     551                 :            :     {
     552                 :    1560810 :       lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
     553                 :    1560810 :       lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
     554                 :            :     }
     555                 :            :   else
     556                 :            :     return;
     557                 :            :   /* Keep the 1st hard regno as more profitable.  */
     558                 :    9775000 :   if (lra_reg_info[regno].preferred_hard_regno1 >= 0
     559                 :    9775000 :       && lra_reg_info[regno].preferred_hard_regno2 >= 0
     560                 :    1739840 :       && (lra_reg_info[regno].preferred_hard_regno_profit2
     561                 :    1739840 :           > lra_reg_info[regno].preferred_hard_regno_profit1))
     562                 :            :     {
     563                 :      82119 :       std::swap (lra_reg_info[regno].preferred_hard_regno1,
     564                 :      82119 :                  lra_reg_info[regno].preferred_hard_regno2);
     565                 :    9857120 :       std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
     566                 :      82119 :                  lra_reg_info[regno].preferred_hard_regno_profit2);
     567                 :            :     }
     568                 :    9775000 :   if (lra_dump_file != NULL)
     569                 :            :     {
     570                 :        674 :       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
     571                 :        674 :         fprintf (lra_dump_file,
     572                 :            :                  " Hard reg %d is preferable by r%d with profit %d\n",
     573                 :            :                  hard_regno, regno,
     574                 :            :                  lra_reg_info[regno].preferred_hard_regno_profit1);
     575                 :        674 :       if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
     576                 :        226 :         fprintf (lra_dump_file,
     577                 :            :                  " Hard reg %d is preferable by r%d with profit %d\n",
     578                 :            :                  hard_regno, regno,
     579                 :            :                  lra_reg_info[regno].preferred_hard_regno_profit2);
     580                 :            :     }
     581                 :            : }
     582                 :            : 
     583                 :            : /* Check whether REGNO lives through calls and setjmps and clear
     584                 :            :    the corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
     585                 :            :    PSEUDOS_LIVE_THROUGH_SETJUMPS.  All calls in the region described
     586                 :            :    by PSEUDOS_LIVE_THROUGH_CALLS have the given ABI.  */
     587                 :            : 
     588                 :            : static inline void
     589                 :  268243000 : check_pseudos_live_through_calls (int regno, const function_abi &abi)
     590                 :            : {
     591                 :  268243000 :   if (! sparseset_bit_p (pseudos_live_through_calls, regno))
     592                 :            :     return;
     593                 :            : 
     594                 :   37107900 :   machine_mode mode = PSEUDO_REGNO_MODE (regno);
     595                 :            : 
     596                 :   37107900 :   sparseset_clear_bit (pseudos_live_through_calls, regno);
     597                 :   74215900 :   lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
     598                 :   37107900 :   if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
     599                 :            :     return;
     600                 :       5879 :   sparseset_clear_bit (pseudos_live_through_setjumps, regno);
     601                 :            :   /* Don't allocate pseudos that cross setjmps or any call, if this
     602                 :            :      function receives a nonlocal goto.  */
     603                 :       5879 :   SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
     604                 :            : }
     605                 :            : 
     606                 :            : /* Return true if insn REG is an early clobber operand in alternative
     607                 :            :    NALT.  Negative NALT means that we don't know the current insn
     608                 :            :    alternative.  So assume the worst.  */
     609                 :            : static inline bool
     610                 :  242014000 : reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
     611                 :            : {
     612                 :  242014000 :   return (n_alt == LRA_UNKNOWN_ALT
     613                 :  251894000 :           ? reg->early_clobber_alts != 0
     614                 :            :           : (n_alt != LRA_NON_CLOBBERED_ALT
     615                 :  232135000 :              && TEST_BIT (reg->early_clobber_alts, n_alt)));
     616                 :            : }
     617                 :            : 
     618                 :            : /* Process insns of the basic block BB to update pseudo live ranges,
     619                 :            :    pseudo hard register conflicts, and insn notes.  We do it on
     620                 :            :    backward scan of BB insns.  CURR_POINT is the program point where
     621                 :            :    BB ends.  The function updates this counter and returns in
     622                 :            :    CURR_POINT the program point where BB starts.  The function also
     623                 :            :    does local live info updates and can delete the dead insns if
     624                 :            :    DEAD_INSN_P.  It returns true if pseudo live info was
     625                 :            :    changed at the BB start.  */
     626                 :            : static bool
     627                 :   20401700 : process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
     628                 :            : {
     629                 :   20401700 :   int i, regno, freq;
     630                 :   20401700 :   unsigned int j;
     631                 :   20401700 :   bitmap_iterator bi;
     632                 :   20401700 :   bitmap reg_live_out;
     633                 :   20401700 :   unsigned int px;
     634                 :   20401700 :   rtx_insn *next;
     635                 :   20401700 :   rtx link, *link_loc;
     636                 :   20401700 :   bool need_curr_point_incr;
     637                 :            :   /* Only has a meaningful value once we've seen a call.  */
     638                 :   20401700 :   function_abi last_call_abi = default_function_abi;
     639                 :            : 
     640                 :   20401700 :   reg_live_out = df_get_live_out (bb);
     641                 :   20401700 :   sparseset_clear (pseudos_live);
     642                 :   20401700 :   sparseset_clear (pseudos_live_through_calls);
     643                 :   20401700 :   sparseset_clear (pseudos_live_through_setjumps);
     644                 :   61205200 :   REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
     645                 :   40803500 :   hard_regs_live &= ~eliminable_regset;
     646                 :  222089000 :   EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
     647                 :            :     {
     648                 :  201687000 :       update_pseudo_point (j, curr_point, USE_POINT);
     649                 :  201687000 :       mark_pseudo_live (j);
     650                 :            :     }
     651                 :            : 
     652                 :   20401700 :   bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
     653                 :   20401700 :   bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
     654                 :   20401700 :   bitmap_clear (bb_gen_pseudos);
     655                 :   20401700 :   bitmap_clear (bb_killed_pseudos);
     656                 :   20401700 :   freq = REG_FREQ_FROM_BB (bb);
     657                 :            : 
     658                 :   20401700 :   if (lra_dump_file != NULL)
     659                 :       1568 :     fprintf (lra_dump_file, "  BB %d\n", bb->index);
     660                 :            : 
     661                 :            :   /* Scan the code of this basic block, noting which pseudos and hard
     662                 :            :      regs are born or die.
     663                 :            : 
     664                 :            :      Note that this loop treats uninitialized values as live until the
     665                 :            :      beginning of the block.  For example, if an instruction uses
     666                 :            :      (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
     667                 :            :      FOO will remain live until the beginning of the block.  Likewise
     668                 :            :      if FOO is not set at all.  This is unnecessarily pessimistic, but
     669                 :            :      it probably doesn't matter much in practice.  */
     670                 :  539449000 :   FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
     671                 :            :     {
     672                 :  249323000 :       bool call_p;
     673                 :  249323000 :       int n_alt, dst_regno, src_regno;
     674                 :  249323000 :       rtx set;
     675                 :  249323000 :       struct lra_insn_reg *reg;
     676                 :            : 
     677                 :  249323000 :       if (!NONDEBUG_INSN_P (curr_insn))
     678                 :  110067000 :         continue;
     679                 :            : 
     680                 :  139256000 :       curr_id = lra_get_insn_recog_data (curr_insn);
     681                 :  139256000 :       curr_static_id = curr_id->insn_static_data;
     682                 :  139256000 :       n_alt = curr_id->used_insn_alternative;
     683                 :  139256000 :       if (lra_dump_file != NULL)
     684                 :      13982 :         fprintf (lra_dump_file, "   Insn %u: point = %d, n_alt = %d\n",
     685                 :       6991 :                  INSN_UID (curr_insn), curr_point, n_alt);
     686                 :            : 
     687                 :  139256000 :       set = single_set (curr_insn);
     688                 :            : 
     689                 :  139256000 :       if (dead_insn_p && set != NULL_RTX
     690                 :  106625000 :           && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
     691                 :   53810000 :           && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
     692                 :   53643300 :           && ! may_trap_p (PATTERN (curr_insn))
     693                 :            :           /* Don't do premature remove of pic offset pseudo as we can
     694                 :            :              start to use it after some reload generation.  */
     695                 :  187672000 :           && (pic_offset_table_rtx == NULL_RTX
     696                 :    5834390 :               || pic_offset_table_rtx != SET_DEST (set)))
     697                 :            :         {
     698                 :   48366600 :           bool remove_p = true;
     699                 :            : 
     700                 :   48709400 :           for (reg = curr_id->regs; reg != NULL; reg = reg->next)
     701                 :   48684100 :             if (reg->type != OP_IN && sparseset_bit_p (pseudos_live, reg->regno))
     702                 :            :               {
     703                 :            :                 remove_p = false;
     704                 :            :                 break;
     705                 :            :               }
     706                 :   49113300 :           for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
     707                 :    9044490 :             if (reg->type != OP_IN)
     708                 :            :               {
     709                 :            :                 remove_p = false;
     710                 :            :                 break;
     711                 :            :               }
     712                 :            : 
     713                 :   48366600 :           if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
     714                 :            :             {
     715                 :      19991 :               dst_regno = REGNO (SET_DEST (set));
     716                 :      19991 :               if (lra_dump_file != NULL)
     717                 :          0 :                 fprintf (lra_dump_file, "   Deleting dead insn %u\n",
     718                 :          0 :                          INSN_UID (curr_insn));
     719                 :      19991 :               lra_set_insn_deleted (curr_insn);
     720                 :      19991 :               if (lra_reg_info[dst_regno].nrefs == 0)
     721                 :            :                 {
     722                 :            :                   /* There might be some debug insns with the pseudo.  */
     723                 :       1629 :                   unsigned int uid;
     724                 :       1629 :                   rtx_insn *insn;
     725                 :            : 
     726                 :       1629 :                   bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
     727                 :       1738 :                   EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
     728                 :            :                     {
     729                 :        109 :                       insn = lra_insn_recog_data[uid]->insn;
     730                 :        109 :                       lra_substitute_pseudo_within_insn (insn, dst_regno,
     731                 :            :                                                          SET_SRC (set), true);
     732                 :        109 :                       lra_update_insn_regno_info (insn);
     733                 :            :                     }
     734                 :            :                 }
     735                 :      19991 :               continue;
     736                 :            :             }
     737                 :            :         }
     738                 :            : 
     739                 :            :       /* Update max ref width and hard reg usage.  */
     740                 :  358882000 :       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
     741                 :            :         {
     742                 :  219646000 :           int i, regno = reg->regno;
     743                 :            : 
     744                 :  219646000 :           if (partial_subreg_p (lra_reg_info[regno].biggest_mode,
     745                 :  219646000 :                                 reg->biggest_mode))
     746                 :    5537990 :             lra_reg_info[regno].biggest_mode = reg->biggest_mode;
     747                 :  219646000 :           if (HARD_REGISTER_NUM_P (regno))
     748                 :            :             {
     749                 :   61818600 :               lra_hard_reg_usage[regno] += freq;
     750                 :            :               /* A hard register explicitly can be used in small mode,
     751                 :            :                  but implicitly it can be used in natural mode as a
     752                 :            :                  part of multi-register group.  Process this case
     753                 :            :                  here.  */
     754                 :   62233000 :               for (i = 1; i < hard_regno_nregs (regno, reg->biggest_mode); i++)
     755                 :     414413 :                 if (partial_subreg_p (lra_reg_info[regno + i].biggest_mode,
     756                 :     414413 :                                       GET_MODE (regno_reg_rtx[regno + i])))
     757                 :      55867 :                   lra_reg_info[regno + i].biggest_mode
     758                 :      55867 :                     = GET_MODE (regno_reg_rtx[regno + i]);
     759                 :            :             }
     760                 :            :         }
     761                 :            : 
     762                 :  139236000 :       call_p = CALL_P (curr_insn);
     763                 :            : 
     764                 :            :       /* If we have a simple register copy and the source reg is live after
     765                 :            :          this instruction, then remove the source reg from the live set so
     766                 :            :          that it will not conflict with the destination reg.  */
     767                 :  139236000 :       rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
     768                 :  139236000 :       if (ignore_reg != NULL_RTX)
     769                 :            :         {
     770                 :   37503900 :           int ignore_regno = REGNO (ignore_reg);
     771                 :   37503900 :           if (HARD_REGISTER_NUM_P (ignore_regno)
     772                 :   37503900 :               && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
     773                 :      47513 :             CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
     774                 :   37456300 :           else if (!HARD_REGISTER_NUM_P (ignore_regno)
     775                 :   37456300 :                    && sparseset_bit_p (pseudos_live, ignore_regno))
     776                 :    7876580 :             sparseset_clear_bit (pseudos_live, ignore_regno);
     777                 :            :           else
     778                 :            :             /* We don't need any special handling of the source reg if
     779                 :            :                it is dead after this instruction.  */
     780                 :            :             ignore_reg = NULL_RTX;
     781                 :            :         }
     782                 :            : 
     783                 :  132582000 :       src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
     784                 :  190067000 :                    ? REGNO (SET_SRC (set)) : -1);
     785                 :  132582000 :       dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
     786                 :  235779000 :                    ? REGNO (SET_DEST (set)) : -1);
     787                 :  139236000 :       if (complete_info_p
     788                 :  136747000 :           && src_regno >= 0 && dst_regno >= 0
     789                 :            :           /* Check that source regno does not conflict with
     790                 :            :              destination regno to exclude most impossible
     791                 :            :              preferences.  */
     792                 :  175907000 :           && (((!HARD_REGISTER_NUM_P (src_regno)
     793                 :   32413100 :                 && (! sparseset_bit_p (pseudos_live, src_regno)
     794                 :       3092 :                     || (!HARD_REGISTER_NUM_P (dst_regno)
     795                 :   40927500 :                         && lra_reg_val_equal_p (src_regno,
     796                 :            :                                                 lra_reg_info[dst_regno].val,
     797                 :          1 :                                                 lra_reg_info[dst_regno].offset))))
     798                 :    4260290 :                || (HARD_REGISTER_NUM_P (src_regno)
     799                 :    4257200 :                    && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
     800                 :            :               /* It might be 'inheritance pseudo <- reload pseudo'.  */
     801                 :       3106 :               || (src_regno >= lra_constraint_new_regno_start
     802                 :        131 :                   && dst_regno >= lra_constraint_new_regno_start
     803                 :            :                   /* Remember to skip special cases where src/dest regnos are
     804                 :            :                      the same, e.g. insn SET pattern has matching constraints
     805                 :            :                      like =r,0.  */
     806                 :          0 :                   && src_regno != dst_regno)))
     807                 :            :         {
     808                 :   36667200 :           int hard_regno = -1, regno = -1;
     809                 :            : 
     810                 :   36667200 :           if (dst_regno >= lra_constraint_new_regno_start
     811                 :   10259300 :               && src_regno >= lra_constraint_new_regno_start)
     812                 :            :             {
     813                 :            :               /* It might be still an original (non-reload) insn with
     814                 :            :                  one unused output and a constraint requiring to use
     815                 :            :                  the same reg for input/output operands. In this case
     816                 :            :                  dst_regno and src_regno have the same value, we don't
     817                 :            :                  need a misleading copy for this case.  */
     818                 :    4349560 :               if (dst_regno != src_regno)
     819                 :    4349560 :                 lra_create_copy (dst_regno, src_regno, freq);
     820                 :            :             }
     821                 :   32317600 :           else if (dst_regno >= lra_constraint_new_regno_start)
     822                 :            :             {
     823                 :    5909750 :               if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
     824                 :    5899460 :                 hard_regno = reg_renumber[src_regno];
     825                 :            :               regno = dst_regno;
     826                 :            :             }
     827                 :   26407900 :           else if (src_regno >= lra_constraint_new_regno_start)
     828                 :            :             {
     829                 :    7000830 :               if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
     830                 :    5515000 :                 hard_regno = reg_renumber[dst_regno];
     831                 :            :               regno = src_regno;
     832                 :            :             }
     833                 :   36667200 :           if (regno >= 0 && hard_regno >= 0)
     834                 :    7477480 :             lra_setup_reload_pseudo_preferenced_hard_reg
     835                 :    7477480 :               (regno, hard_regno, freq);
     836                 :            :         }
     837                 :            : 
     838                 :  139236000 :       sparseset_clear (start_living);
     839                 :            : 
     840                 :            :       /* Mark each defined value as live.  We need to do this for
     841                 :            :          unused values because they still conflict with quantities
     842                 :            :          that are live at the time of the definition.  */
     843                 :  358882000 :       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
     844                 :  219646000 :         if (reg->type != OP_IN)
     845                 :            :           {
     846                 :   95368700 :             update_pseudo_point (reg->regno, curr_point, USE_POINT);
     847                 :   95368700 :             mark_regno_live (reg->regno, reg->biggest_mode);
     848                 :            :             /* ??? Should be a no-op for unused registers.  */
     849                 :   95368700 :             check_pseudos_live_through_calls (reg->regno, last_call_abi);
     850                 :            :           }
     851                 :            : 
     852                 :  174904000 :       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
     853                 :   35667700 :         if (reg->type != OP_IN)
     854                 :   25638400 :           make_hard_regno_live (reg->regno);
     855                 :            : 
     856                 :  139236000 :       if (curr_id->arg_hard_regs != NULL)
     857                 :   18925100 :         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
     858                 :   13024500 :           if (!HARD_REGISTER_NUM_P (regno))
     859                 :            :             /* It is a clobber.  */
     860                 :     170361 :             make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
     861                 :            : 
     862                 :  139236000 :       sparseset_copy (unused_set, start_living);
     863                 :            : 
     864                 :  139236000 :       sparseset_clear (start_dying);
     865                 :            : 
     866                 :            :       /* See which defined values die here.  */
     867                 :  358882000 :       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
     868                 :  219646000 :         if (reg->type != OP_IN
     869                 :  405131000 :             && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
     870                 :            :           {
     871                 :   94329300 :             if (reg->type == OP_OUT)
     872                 :   79357300 :               update_pseudo_point (reg->regno, curr_point, DEF_POINT);
     873                 :   94329300 :             mark_regno_dead (reg->regno, reg->biggest_mode);
     874                 :            :           }
     875                 :            : 
     876                 :  174904000 :       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
     877                 :   35667700 :         if (reg->type != OP_IN
     878                 :   71273800 :             && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
     879                 :   10694200 :           make_hard_regno_dead (reg->regno);
     880                 :            : 
     881                 :  139236000 :       if (curr_id->arg_hard_regs != NULL)
     882                 :   18925100 :         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
     883                 :   13024500 :           if (!HARD_REGISTER_NUM_P (regno))
     884                 :            :             /* It is a clobber.  */
     885                 :     170361 :             make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
     886                 :            : 
     887                 :  139236000 :       if (call_p)
     888                 :            :         {
     889                 :    7998320 :           function_abi call_abi = insn_callee_abi (curr_insn);
     890                 :            : 
     891                 :   15996600 :           if (last_call_abi != call_abi)
     892                 :    4751140 :             EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
     893                 :    3287010 :               check_pseudos_live_through_calls (j, last_call_abi);
     894                 :            : 
     895                 :    7998320 :           last_call_abi = call_abi;
     896                 :            : 
     897                 :    7998320 :           sparseset_ior (pseudos_live_through_calls,
     898                 :            :                          pseudos_live_through_calls, pseudos_live);
     899                 :    7998320 :           if (cfun->has_nonlocal_label
     900                 :    7994040 :               || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
     901                 :    7994040 :                   && (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
     902                 :    7998320 :                       != NULL_RTX)))
     903                 :       5924 :             sparseset_ior (pseudos_live_through_setjumps,
     904                 :            :                            pseudos_live_through_setjumps, pseudos_live);
     905                 :            :         }
     906                 :            : 
     907                 :            :       /* Increment the current program point if we must.  */
     908                 :  139236000 :       if (sparseset_contains_pseudos_p (unused_set)
     909                 :  209928000 :           || sparseset_contains_pseudos_p (start_dying))
     910                 :  135835000 :         next_program_point (curr_point, freq);
     911                 :            : 
     912                 :            :       /* If we removed the source reg from a simple register copy from the
     913                 :            :          live set above, then add it back now so we don't accidentally add
     914                 :            :          it to the start_living set below.  */
     915                 :  139236000 :       if (ignore_reg != NULL_RTX)
     916                 :            :         {
     917                 :    7924090 :           int ignore_regno = REGNO (ignore_reg);
     918                 :    7924090 :           if (HARD_REGISTER_NUM_P (ignore_regno))
     919                 :      47513 :             SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
     920                 :            :           else
     921                 :    7876580 :             sparseset_set_bit (pseudos_live, ignore_regno);
     922                 :            :         }
     923                 :            : 
     924                 :  139236000 :       sparseset_clear (start_living);
     925                 :            : 
     926                 :            :       /* Mark each used value as live.  */
     927                 :  358882000 :       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
     928                 :  219646000 :         if (reg->type != OP_OUT)
     929                 :            :           {
     930                 :  139363000 :             if (reg->type == OP_IN)
     931                 :  124277000 :               update_pseudo_point (reg->regno, curr_point, USE_POINT);
     932                 :  139363000 :             mark_regno_live (reg->regno, reg->biggest_mode);
     933                 :  139363000 :             check_pseudos_live_through_calls (reg->regno, last_call_abi);
     934                 :            :           }
     935                 :            : 
     936                 :  174904000 :       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
     937                 :   35667700 :         if (reg->type != OP_OUT)
     938                 :   10426300 :           make_hard_regno_live (reg->regno);
     939                 :            : 
     940                 :  139236000 :       if (curr_id->arg_hard_regs != NULL)
     941                 :            :         /* Make argument hard registers live.  */
     942                 :   18925100 :         for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
     943                 :   13024500 :           if (HARD_REGISTER_NUM_P (regno))
     944                 :   12854200 :             make_hard_regno_live (regno);
     945                 :            : 
     946                 :  139236000 :       sparseset_and_compl (dead_set, start_living, start_dying);
     947                 :            : 
     948                 :  139236000 :       sparseset_clear (start_dying);
     949                 :            : 
     950                 :            :       /* Mark early clobber outputs dead.  */
     951                 :  358882000 :       for (reg = curr_id->regs; reg != NULL; reg = reg->next)
     952                 :  219646000 :         if (reg->type != OP_IN
     953                 :  311007000 :             && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
     954                 :            :           {
     955                 :     205611 :             if (reg->type == OP_OUT)
     956                 :     132877 :               update_pseudo_point (reg->regno, curr_point, DEF_POINT);
     957                 :     205611 :             mark_regno_dead (reg->regno, reg->biggest_mode);
     958                 :            : 
     959                 :            :             /* We're done processing inputs, so make sure early clobber
     960                 :            :                operands that are both inputs and outputs are still live.  */
     961                 :     205611 :             if (reg->type == OP_INOUT)
     962                 :      72734 :               mark_regno_live (reg->regno, reg->biggest_mode);
     963                 :            :           }
     964                 :            : 
     965                 :  174904000 :       for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
     966                 :   35667700 :         if (reg->type != OP_IN
     967                 :   75523700 :             && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
     968                 :            :           {
     969                 :   14944200 :             struct lra_insn_reg *reg2;
     970                 :            : 
     971                 :            :             /* We can have early clobbered non-operand hard reg and
     972                 :            :                the same hard reg as an insn input.  Don't make hard
     973                 :            :                reg dead before the insns.  */
     974                 :   40669800 :             for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
     975                 :   25751900 :               if (reg2->type != OP_OUT && reg2->regno == reg->regno)
     976                 :            :                 break;
     977                 :   14944200 :             if (reg2 == NULL)
     978                 :   14917800 :               make_hard_regno_dead (reg->regno);
     979                 :            :           }
     980                 :            : 
     981                 :            :       /* Increment the current program point if we must.  */
     982                 :  139236000 :       if (sparseset_contains_pseudos_p (dead_set)
     983                 :  172079000 :           || sparseset_contains_pseudos_p (start_dying))
     984                 :  106500000 :         next_program_point (curr_point, freq);
     985                 :            : 
     986                 :            :       /* Update notes.  */
     987                 :  278160000 :       for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
     988                 :            :         {
     989                 :  138924000 :           if (REG_NOTE_KIND (link) != REG_DEAD
     990                 :   58990400 :               && REG_NOTE_KIND (link) != REG_UNUSED)
     991                 :            :             ;
     992                 :   96845800 :           else if (REG_P (XEXP (link, 0)))
     993                 :            :             {
     994                 :   96845800 :               regno = REGNO (XEXP (link, 0));
     995                 :   98941000 :               if ((REG_NOTE_KIND (link) == REG_DEAD
     996                 :   79933800 :                    && ! sparseset_bit_p (dead_set, regno))
     997                 :  174831000 :                   || (REG_NOTE_KIND (link) == REG_UNUSED
     998                 :   16912000 :                       && ! sparseset_bit_p (unused_set, regno)))
     999                 :            :                 {
    1000                 :    2095210 :                   *link_loc = XEXP (link, 1);
    1001                 :    2095210 :                   continue;
    1002                 :            :                 }
    1003                 :   94750600 :               if (REG_NOTE_KIND (link) == REG_DEAD)
    1004                 :   77985200 :                 sparseset_clear_bit (dead_set, regno);
    1005                 :   16765400 :               else if (REG_NOTE_KIND (link) == REG_UNUSED)
    1006                 :   16765400 :                 sparseset_clear_bit (unused_set, regno);
    1007                 :            :             }
    1008                 :  136829000 :           link_loc = &XEXP (link, 1);
    1009                 :            :         }
    1010                 :  145311000 :       EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
    1011                 :    6074340 :         add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
    1012                 :  278797000 :       EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
    1013                 :     324662 :         add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
    1014                 :            :     }
    1015                 :            : 
    1016                 :   20401700 :   if (bb_has_eh_pred (bb))
    1017                 :     367433 :     for (j = 0; ; ++j)
    1018                 :            :       {
    1019                 :    1102300 :         unsigned int regno = EH_RETURN_DATA_REGNO (j);
    1020                 :            : 
    1021                 :     734866 :         if (regno == INVALID_REGNUM)
    1022                 :            :           break;
    1023                 :     734866 :         make_hard_regno_live (regno);
    1024                 :     734866 :       }
    1025                 :            : 
    1026                 :            :   /* Pseudos can't go in stack regs at the start of a basic block that
    1027                 :            :      is reached by an abnormal edge.  Likewise for registers that are at
    1028                 :            :      least partly call clobbered, because caller-save, fixup_abnormal_edges
    1029                 :            :      and possibly the table driven EH machinery are not quite ready to
    1030                 :            :      handle such pseudos live across such edges.  */
    1031                 :   20401700 :   if (bb_has_abnormal_pred (bb))
    1032                 :            :     {
    1033                 :            :       HARD_REG_SET clobbers;
    1034                 :            : 
    1035                 :    1111170 :       CLEAR_HARD_REG_SET (clobbers);
    1036                 :            : #ifdef STACK_REGS
    1037                 :    1369380 :       EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
    1038                 :     628594 :         lra_reg_info[px].no_stack_p = true;
    1039                 :    3333520 :       for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
    1040                 :    2963130 :         SET_HARD_REG_BIT (clobbers, px);
    1041                 :            : #endif
    1042                 :            :       /* No need to record conflicts for call clobbered regs if we
    1043                 :            :          have nonlocal labels around, as we don't ever try to
    1044                 :            :          allocate such regs in this case.  */
    1045                 :     370391 :       if (!cfun->has_nonlocal_label
    1046                 :     370391 :           && has_abnormal_call_or_eh_pred_edge_p (bb))
    1047                 :   28292000 :         for (px = 0; HARD_REGISTER_NUM_P (px); px++)
    1048                 :   27924600 :           if (eh_edge_abi.clobbers_at_least_part_of_reg_p (px)
    1049                 :            : #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
    1050                 :            :               /* We should create a conflict of PIC pseudo with PIC
    1051                 :            :                  hard reg as PIC hard reg can have a wrong value after
    1052                 :            :                  jump described by the abnormal edge.  In this case we
    1053                 :            :                  cannot allocate PIC hard reg to PIC pseudo as PIC
    1054                 :            :                  pseudo will also have a wrong value.  */
    1055                 :   28404600 :               || (px == REAL_PIC_OFFSET_TABLE_REGNUM
    1056                 :     367429 :                   && pic_offset_table_rtx != NULL_RTX
    1057                 :      21957 :                   && !HARD_REGISTER_P (pic_offset_table_rtx))
    1058                 :            : #endif
    1059                 :            :               )
    1060                 :   27924600 :             SET_HARD_REG_BIT (clobbers, px);
    1061                 :            : 
    1062                 :    1111170 :       clobbers &= ~hard_regs_live;
    1063                 :   28520100 :       for (px = 0; HARD_REGISTER_NUM_P (px); px++)
    1064                 :   28149700 :         if (TEST_HARD_REG_BIT (clobbers, px))
    1065                 :            :           {
    1066                 :   24065700 :             make_hard_regno_live (px);
    1067                 :   24065700 :             make_hard_regno_dead (px);
    1068                 :            :           }
    1069                 :            :     }
    1070                 :            : 
    1071                 :   20401700 :   bool live_change_p = false;
    1072                 :            :   /* Check if bb border live info was changed.  */
    1073                 :   20401700 :   unsigned int live_pseudos_num = 0;
    1074                 :  216999000 :   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
    1075                 :            :                             FIRST_PSEUDO_REGISTER, j, bi)
    1076                 :            :     {
    1077                 :  196736000 :       live_pseudos_num++;
    1078                 :  196736000 :       if (! sparseset_bit_p (pseudos_live, j))
    1079                 :            :         {
    1080                 :     139359 :           live_change_p = true;
    1081                 :     139359 :           if (lra_dump_file != NULL)
    1082                 :          0 :             fprintf (lra_dump_file,
    1083                 :            :                      "  r%d is removed as live at bb%d start\n", j, bb->index);
    1084                 :            :           break;
    1085                 :            :         }
    1086                 :            :     }
    1087                 :   20401700 :   if (! live_change_p
    1088                 :   20401700 :       && sparseset_cardinality (pseudos_live) != live_pseudos_num)
    1089                 :            :     {
    1090                 :     129825 :       live_change_p = true;
    1091                 :     129825 :       if (lra_dump_file != NULL)
    1092                 :          0 :         EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
    1093                 :          0 :           if (! bitmap_bit_p (df_get_live_in (bb), j))
    1094                 :          0 :             fprintf (lra_dump_file,
    1095                 :            :                      "  r%d is added to live at bb%d start\n", j, bb->index);
    1096                 :            :     }
    1097                 :            :   /* See if we'll need an increment at the end of this basic block.
    1098                 :            :      An increment is needed if the PSEUDOS_LIVE set is not empty,
    1099                 :            :      to make sure the finish points are set up correctly.  */
    1100                 :   20401700 :   need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
    1101                 :            : 
    1102                 :  414415000 :   EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
    1103                 :            :     {
    1104                 :  197007000 :       update_pseudo_point (i, curr_point, DEF_POINT);
    1105                 :  197007000 :       mark_pseudo_dead (i);
    1106                 :            :     }
    1107                 :            : 
    1108                 :   54640600 :   EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
    1109                 :            :     {
    1110                 :   47485900 :       if (sparseset_cardinality (pseudos_live_through_calls) == 0)
    1111                 :            :         break;
    1112                 :   34238800 :       if (sparseset_bit_p (pseudos_live_through_calls, j))
    1113                 :   30224100 :         check_pseudos_live_through_calls (j, last_call_abi);
    1114                 :            :     }
    1115                 :            : 
    1116                 : 1570930000 :   for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
    1117                 :            :     {
    1118                 : 1550530000 :       if (!TEST_HARD_REG_BIT (hard_regs_live, i))
    1119                 : 1522040000 :         continue;
    1120                 :            : 
    1121                 :   28492200 :       if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
    1122                 :   28492200 :         continue;
    1123                 :            : 
    1124                 :          0 :       if (bitmap_bit_p (df_get_live_in (bb), i))
    1125                 :          0 :         continue;
    1126                 :            : 
    1127                 :          0 :       live_change_p = true;
    1128                 :          0 :       if (lra_dump_file)
    1129                 :          0 :         fprintf (lra_dump_file,
    1130                 :            :                  "  hard reg r%d is added to live at bb%d start\n", i,
    1131                 :            :                  bb->index);
    1132                 :          0 :       bitmap_set_bit (df_get_live_in (bb), i);
    1133                 :            :     }
    1134                 :            : 
    1135                 :   20401700 :   if (need_curr_point_incr)
    1136                 :   32268100 :     next_program_point (curr_point, freq);
    1137                 :            : 
    1138                 :   20401700 :   return live_change_p;
    1139                 :            : }
    1140                 :            : 
    1141                 :            : /* Compress pseudo live ranges by removing program points where
    1142                 :            :    nothing happens.  Complexity of many algorithms in LRA is linear
    1143                 :            :    function of program points number.  To speed up the code we try to
    1144                 :            :    minimize the number of the program points here.  */
    1145                 :            : static void
    1146                 :    1005680 : remove_some_program_points_and_update_live_ranges (void)
    1147                 :            : {
    1148                 :    1005680 :   unsigned i;
    1149                 :    1005680 :   int n, max_regno;
    1150                 :    1005680 :   int *map;
    1151                 :    1005680 :   lra_live_range_t r, prev_r, next_r;
    1152                 :    1005680 :   sbitmap_iterator sbi;
    1153                 :    1005680 :   bool born_p, dead_p, prev_born_p, prev_dead_p;
    1154                 :            : 
    1155                 :    1005680 :   auto_sbitmap born (lra_live_max_point);
    1156                 :    1005680 :   auto_sbitmap dead (lra_live_max_point);
    1157                 :    1005680 :   bitmap_clear (born);
    1158                 :    1005680 :   bitmap_clear (dead);
    1159                 :    1005680 :   max_regno = max_reg_num ();
    1160                 :  107784000 :   for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
    1161                 :            :     {
    1162                 :  172969000 :       for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
    1163                 :            :         {
    1164                 :   66190800 :           lra_assert (r->start <= r->finish);
    1165                 :   66190800 :           bitmap_set_bit (born, r->start);
    1166                 :   66190800 :           bitmap_set_bit (dead, r->finish);
    1167                 :            :         }
    1168                 :            :     }
    1169                 :    1005680 :   auto_sbitmap born_or_dead (lra_live_max_point);
    1170                 :    1005680 :   bitmap_ior (born_or_dead, born, dead);
    1171                 :    1005680 :   map = XCNEWVEC (int, lra_live_max_point);
    1172                 :    1005680 :   n = -1;
    1173                 :    1005680 :   prev_born_p = prev_dead_p = false;
    1174                 :  118137000 :   EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
    1175                 :            :     {
    1176                 :  116126000 :       born_p = bitmap_bit_p (born, i);
    1177                 :  116126000 :       dead_p = bitmap_bit_p (dead, i);
    1178                 :  116126000 :       if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
    1179                 :  107408000 :           || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
    1180                 :            :         {
    1181                 :   25052300 :           map[i] = n;
    1182                 :   25052300 :           lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
    1183                 :            :         }
    1184                 :            :       else
    1185                 :            :         {
    1186                 :   91073400 :           map[i] = ++n;
    1187                 :   91073400 :           lra_point_freq[n] = lra_point_freq[i];
    1188                 :            :         }
    1189                 :  116126000 :       prev_born_p = born_p;
    1190                 :  116126000 :       prev_dead_p = dead_p;
    1191                 :            :     }
    1192                 :    1005680 :   n++;
    1193                 :    1005680 :   if (lra_dump_file != NULL)
    1194                 :        116 :     fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
    1195                 :            :              lra_live_max_point, n,
    1196                 :        116 :              lra_live_max_point ? 100 * n / lra_live_max_point : 100);
    1197                 :    1005680 :   if (n < lra_live_max_point)
    1198                 :            :     {
    1199                 :     839369 :       lra_live_max_point = n;
    1200                 :  105531000 :       for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
    1201                 :            :         {
    1202                 :  104692000 :           for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
    1203                 :  170311000 :                r != NULL;
    1204                 :            :                r = next_r)
    1205                 :            :             {
    1206                 :   65618700 :               next_r = r->next;
    1207                 :   65618700 :               r->start = map[r->start];
    1208                 :   65618700 :               r->finish = map[r->finish];
    1209                 :   65618700 :               if (prev_r == NULL || prev_r->start > r->finish + 1)
    1210                 :            :                 {
    1211                 :   64419200 :                   prev_r = r;
    1212                 :   64419200 :                   continue;
    1213                 :            :                 }
    1214                 :    1199530 :               prev_r->start = r->start;
    1215                 :    1199530 :               prev_r->next = next_r;
    1216                 :  171510000 :               lra_live_range_pool.remove (r);
    1217                 :            :             }
    1218                 :            :         }
    1219                 :            :     }
    1220                 :    1005680 :   free (map);
    1221                 :    1005680 : }
    1222                 :            : 
    1223                 :            : /* Print live ranges R to file F.  */
    1224                 :            : void
    1225                 :       6224 : lra_print_live_range_list (FILE *f, lra_live_range_t r)
    1226                 :            : {
    1227                 :      13526 :   for (; r != NULL; r = r->next)
    1228                 :       7302 :     fprintf (f, " [%d..%d]", r->start, r->finish);
    1229                 :       6224 :   fprintf (f, "\n");
    1230                 :       6224 : }
    1231                 :            : 
    1232                 :            : DEBUG_FUNCTION void
    1233                 :          0 : debug (lra_live_range &ref)
    1234                 :            : {
    1235                 :          0 :   lra_print_live_range_list (stderr, &ref);
    1236                 :          0 : }
    1237                 :            : 
    1238                 :            : DEBUG_FUNCTION void
    1239                 :          0 : debug (lra_live_range *ptr)
    1240                 :            : {
    1241                 :          0 :   if (ptr)
    1242                 :          0 :     debug (*ptr);
    1243                 :            :   else
    1244                 :          0 :     fprintf (stderr, "<nil>\n");
    1245                 :          0 : }
    1246                 :            : 
    1247                 :            : /* Print live ranges R to stderr.  */
    1248                 :            : void
    1249                 :          0 : lra_debug_live_range_list (lra_live_range_t r)
    1250                 :            : {
    1251                 :          0 :   lra_print_live_range_list (stderr, r);
    1252                 :          0 : }
    1253                 :            : 
    1254                 :            : /* Print live ranges of pseudo REGNO to file F.  */
    1255                 :            : static void
    1256                 :      14810 : print_pseudo_live_ranges (FILE *f, int regno)
    1257                 :            : {
    1258                 :      14810 :   if (lra_reg_info[regno].live_ranges == NULL)
    1259                 :            :     return;
    1260                 :       6224 :   fprintf (f, " r%d:", regno);
    1261                 :       6224 :   lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
    1262                 :            : }
    1263                 :            : 
    1264                 :            : /* Print live ranges of pseudo REGNO to stderr.  */
    1265                 :            : void
    1266                 :          0 : lra_debug_pseudo_live_ranges (int regno)
    1267                 :            : {
    1268                 :          0 :   print_pseudo_live_ranges (stderr, regno);
    1269                 :          0 : }
    1270                 :            : 
    1271                 :            : /* Print live ranges of all pseudos to file F.  */
    1272                 :            : static void
    1273                 :        232 : print_live_ranges (FILE *f)
    1274                 :            : {
    1275                 :        232 :   int i, max_regno;
    1276                 :            : 
    1277                 :        232 :   max_regno = max_reg_num ();
    1278                 :      15042 :   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
    1279                 :      14810 :     print_pseudo_live_ranges (f, i);
    1280                 :        232 : }
    1281                 :            : 
    1282                 :            : /* Print live ranges of all pseudos to stderr.  */
    1283                 :            : void
    1284                 :          0 : lra_debug_live_ranges (void)
    1285                 :            : {
    1286                 :          0 :   print_live_ranges (stderr);
    1287                 :          0 : }
    1288                 :            : 
    1289                 :            : /* Compress pseudo live ranges.  */
    1290                 :            : static void
    1291                 :    1005680 : compress_live_ranges (void)
    1292                 :            : {
    1293                 :    1005680 :   remove_some_program_points_and_update_live_ranges ();
    1294                 :    1005680 :   if (lra_dump_file != NULL)
    1295                 :            :     {
    1296                 :        116 :       fprintf (lra_dump_file, "Ranges after the compression:\n");
    1297                 :        116 :       print_live_ranges (lra_dump_file);
    1298                 :            :     }
    1299                 :    1005680 : }
    1300                 :            : 
    1301                 :            : 
    1302                 :            : 
    1303                 :            : /* The number of the current live range pass.  */
    1304                 :            : int lra_live_range_iter;
    1305                 :            : 
    1306                 :            : /* The function creates live ranges only for memory pseudos (or for
    1307                 :            :    all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos.  It
    1308                 :            :    also does dead insn elimination if DEAD_INSN_P and global live
    1309                 :            :    analysis only for pseudos and only if the pseudo live info was
    1310                 :            :    changed on a BB border.  Return TRUE if the live info was
    1311                 :            :    changed.  */
    1312                 :            : static bool
    1313                 :    1134610 : lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
    1314                 :            : {
    1315                 :    1134610 :   basic_block bb;
    1316                 :    1134610 :   int i, hard_regno, max_regno = max_reg_num ();
    1317                 :    1134610 :   int curr_point;
    1318                 :    1134610 :   bool bb_live_change_p, have_referenced_pseudos = false;
    1319                 :            : 
    1320                 :    1134610 :   timevar_push (TV_LRA_CREATE_LIVE_RANGES);
    1321                 :            : 
    1322                 :    1134610 :   complete_info_p = all_p;
    1323                 :    1134610 :   if (lra_dump_file != NULL)
    1324                 :        130 :     fprintf (lra_dump_file,
    1325                 :            :              "\n********** Pseudo live ranges #%d: **********\n\n",
    1326                 :            :              ++lra_live_range_iter);
    1327                 :    1134610 :   memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
    1328                 :  195628000 :   for (i = 0; i < max_regno; i++)
    1329                 :            :     {
    1330                 :  194493000 :       lra_reg_info[i].live_ranges = NULL;
    1331                 :  194493000 :       CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
    1332                 :  194493000 :       lra_reg_info[i].preferred_hard_regno1 = -1;
    1333                 :  194493000 :       lra_reg_info[i].preferred_hard_regno2 = -1;
    1334                 :  194493000 :       lra_reg_info[i].preferred_hard_regno_profit1 = 0;
    1335                 :  194493000 :       lra_reg_info[i].preferred_hard_regno_profit2 = 0;
    1336                 :            : #ifdef STACK_REGS
    1337                 :  194493000 :       lra_reg_info[i].no_stack_p = false;
    1338                 :            : #endif
    1339                 :            :       /* The biggest mode is already set but its value might be to
    1340                 :            :          conservative because of recent transformation.  Here in this
    1341                 :            :          file we recalculate it again as it costs practically
    1342                 :            :          nothing.  */
    1343                 :  194493000 :       if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
    1344                 :  106834000 :         lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
    1345                 :            :       else
    1346                 :   87658900 :         lra_reg_info[i].biggest_mode = VOIDmode;
    1347                 :  194493000 :       if (!HARD_REGISTER_NUM_P (i)
    1348                 :  108263000 :           && lra_reg_info[i].nrefs != 0)
    1349                 :            :         {
    1350                 :   55667900 :           if ((hard_regno = reg_renumber[i]) >= 0)
    1351                 :   44818000 :             lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
    1352                 :            :           have_referenced_pseudos = true;
    1353                 :            :         }
    1354                 :            :     }
    1355                 :    1134610 :   lra_free_copies ();
    1356                 :            : 
    1357                 :            :   /* Under some circumstances, we can have functions without pseudo
    1358                 :            :      registers.  For such functions, lra_live_max_point will be 0,
    1359                 :            :      see e.g. PR55604, and there's nothing more to do for us here.  */
    1360                 :    1134610 :   if (! have_referenced_pseudos)
    1361                 :            :     {
    1362                 :     128934 :       timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
    1363                 :     128934 :       return false;
    1364                 :            :     }
    1365                 :            : 
    1366                 :    1005680 :   pseudos_live = sparseset_alloc (max_regno);
    1367                 :    1005680 :   pseudos_live_through_calls = sparseset_alloc (max_regno);
    1368                 :    1005680 :   pseudos_live_through_setjumps = sparseset_alloc (max_regno);
    1369                 :    1005680 :   start_living = sparseset_alloc (max_regno);
    1370                 :    1005680 :   start_dying = sparseset_alloc (max_regno);
    1371                 :    1005680 :   dead_set = sparseset_alloc (max_regno);
    1372                 :    1005680 :   unused_set = sparseset_alloc (max_regno);
    1373                 :    1005680 :   curr_point = 0;
    1374                 :    1005680 :   unsigned new_length = get_max_uid () * 2;
    1375                 :    1005680 :   point_freq_vec.truncate (0);
    1376                 :    1005680 :   point_freq_vec.reserve_exact (new_length);
    1377                 :    1005680 :   lra_point_freq = point_freq_vec.address ();
    1378                 :    1005680 :   auto_vec<int, 20> post_order_rev_cfg;
    1379                 :    1005680 :   inverted_post_order_compute (&post_order_rev_cfg);
    1380                 :    2011360 :   lra_assert (post_order_rev_cfg.length () == (unsigned) n_basic_blocks_for_fn (cfun));
    1381                 :    1005680 :   bb_live_change_p = false;
    1382                 :   23418800 :   for (i = post_order_rev_cfg.length () - 1; i >= 0; --i)
    1383                 :            :     {
    1384                 :   22413100 :       bb = BASIC_BLOCK_FOR_FN (cfun, post_order_rev_cfg[i]);
    1385                 :   22413100 :       if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
    1386                 :   21407400 :           == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1387                 :    2011360 :         continue;
    1388                 :   20401700 :       if (process_bb_lives (bb, curr_point, dead_insn_p))
    1389                 :     269184 :         bb_live_change_p = true;
    1390                 :            :     }
    1391                 :    1005680 :   if (bb_live_change_p)
    1392                 :            :     {
    1393                 :            :       /* We need to clear pseudo live info as some pseudos can
    1394                 :            :          disappear, e.g. pseudos with used equivalences.  */
    1395                 :    3951000 :       FOR_EACH_BB_FN (bb, cfun)
    1396                 :            :         {
    1397                 :    3874620 :           bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
    1398                 :    3874620 :                               max_regno - FIRST_PSEUDO_REGISTER);
    1399                 :    3874620 :           bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
    1400                 :            :                               max_regno - FIRST_PSEUDO_REGISTER);
    1401                 :            :         }
    1402                 :            :       /* As we did not change CFG since LRA start we can use
    1403                 :            :          DF-infrastructure solver to solve live data flow problem.  */
    1404                 :    5880800 :       for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
    1405                 :            :         {
    1406                 :    5804420 :           if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
    1407                 :          0 :             bitmap_clear_bit (&all_hard_regs_bitmap, i);
    1408                 :            :         }
    1409                 :      76374 :       df_simple_dataflow
    1410                 :      76374 :         (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
    1411                 :            :          live_trans_fun, &all_blocks,
    1412                 :            :          df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
    1413                 :      76374 :       if (lra_dump_file != NULL)
    1414                 :            :         {
    1415                 :          0 :           fprintf (lra_dump_file,
    1416                 :            :                    "Global pseudo live data have been updated:\n");
    1417                 :          0 :           basic_block bb;
    1418                 :          0 :           FOR_EACH_BB_FN (bb, cfun)
    1419                 :            :             {
    1420                 :          0 :               bb_data_t bb_info = get_bb_data (bb);
    1421                 :          0 :               bitmap bb_livein = df_get_live_in (bb);
    1422                 :          0 :               bitmap bb_liveout = df_get_live_out (bb);
    1423                 :            : 
    1424                 :          0 :               fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
    1425                 :          0 :               lra_dump_bitmap_with_title ("  gen:",
    1426                 :            :                                           &bb_info->gen_pseudos, bb->index);
    1427                 :          0 :               lra_dump_bitmap_with_title ("  killed:",
    1428                 :            :                                           &bb_info->killed_pseudos, bb->index);
    1429                 :          0 :               lra_dump_bitmap_with_title ("  livein:", bb_livein, bb->index);
    1430                 :          0 :               lra_dump_bitmap_with_title ("  liveout:", bb_liveout, bb->index);
    1431                 :            :             }
    1432                 :            :         }
    1433                 :            :     }
    1434                 :    1005680 :   lra_live_max_point = curr_point;
    1435                 :    1005680 :   if (lra_dump_file != NULL)
    1436                 :        116 :     print_live_ranges (lra_dump_file);
    1437                 :            :   /* Clean up.  */
    1438                 :    1005680 :   sparseset_free (unused_set);
    1439                 :    1005680 :   sparseset_free (dead_set);
    1440                 :    1005680 :   sparseset_free (start_dying);
    1441                 :    1005680 :   sparseset_free (start_living);
    1442                 :    1005680 :   sparseset_free (pseudos_live_through_calls);
    1443                 :    1005680 :   sparseset_free (pseudos_live_through_setjumps);
    1444                 :    1005680 :   sparseset_free (pseudos_live);
    1445                 :    1005680 :   compress_live_ranges ();
    1446                 :    1005680 :   timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
    1447                 :    1005680 :   return bb_live_change_p;
    1448                 :            : }
    1449                 :            : 
    1450                 :            : /* The main entry function creates live-ranges and other live info
    1451                 :            :    necessary for the assignment sub-pass.  It uses
    1452                 :            :    lra_creates_live_ranges_1 -- so read comments for the
    1453                 :            :    function.  */
    1454                 :            : void
    1455                 :    1058240 : lra_create_live_ranges (bool all_p, bool dead_insn_p)
    1456                 :            : {
    1457                 :    1058240 :   if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
    1458                 :            :     return;
    1459                 :      76374 :   if (lra_dump_file != NULL)
    1460                 :          0 :     fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
    1461                 :            :   /* Live info was changed on a bb border.  It means that some info,
    1462                 :            :      e.g. about conflict regs, calls crossed, and live ranges may be
    1463                 :            :      wrong.  We need this info for allocation.  So recalculate it
    1464                 :            :      again but without removing dead insns which can change live info
    1465                 :            :      again.  Repetitive live range calculations are expensive therefore
    1466                 :            :      we stop here as we already have correct info although some
    1467                 :            :      improvement in rare cases could be possible on this sub-pass if
    1468                 :            :      we do dead insn elimination again (still the improvement may
    1469                 :            :      happen later).  */
    1470                 :      76374 :   lra_clear_live_ranges ();
    1471                 :      76374 :   bool res = lra_create_live_ranges_1 (all_p, false);
    1472                 :      76374 :   lra_assert (! res);
    1473                 :            : }
    1474                 :            : 
    1475                 :            : /* Finish all live ranges.  */
    1476                 :            : void
    1477                 :    1125530 : lra_clear_live_ranges (void)
    1478                 :            : {
    1479                 :    1125530 :   int i;
    1480                 :            : 
    1481                 :  188599000 :   for (i = 0; i < max_reg_num (); i++)
    1482                 :  374947000 :     free_live_range_list (lra_reg_info[i].live_ranges);
    1483                 :    1125530 :   point_freq_vec.release ();
    1484                 :    1125530 : }
    1485                 :            : 
    1486                 :            : /* Initialize live ranges data once per function.  */
    1487                 :            : void
    1488                 :     944096 : lra_live_ranges_init (void)
    1489                 :            : {
    1490                 :     944096 :   bitmap_initialize (&temp_bitmap, &reg_obstack);
    1491                 :     944096 :   initiate_live_solver ();
    1492                 :     944096 : }
    1493                 :            : 
    1494                 :            : /* Finish live ranges data once per function.  */
    1495                 :            : void
    1496                 :     944096 : lra_live_ranges_finish (void)
    1497                 :            : {
    1498                 :     944096 :   finish_live_solver ();
    1499                 :     944096 :   bitmap_clear (&temp_bitmap);
    1500                 :     944096 :   lra_live_range_pool.release ();
    1501                 :     944096 : }

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.