LCOV - code coverage report
Current view: top level - gcc - lra-coalesce.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 90.4 % 167 151
Test Date: 2024-11-30 13:30:02 Functions: 87.5 % 8 7
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Coalesce spilled pseudos.
       2                 :             :    Copyright (C) 2010-2024 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 a pass making some simple RTL code
      23                 :             :    transformations by coalescing pseudos to remove some move insns.
      24                 :             : 
      25                 :             :    Spilling pseudos in LRA can create memory-memory moves.  We should
      26                 :             :    remove potential memory-memory moves before the next constraint
      27                 :             :    pass because the constraint pass will generate additional insns for
      28                 :             :    such moves and all these insns will be hard to remove afterwards.
      29                 :             : 
      30                 :             :    Here we coalesce only spilled pseudos.  Coalescing non-spilled
      31                 :             :    pseudos (with different hard regs) might result in spilling
      32                 :             :    additional pseudos because of possible conflicts with other
      33                 :             :    non-spilled pseudos and, as a consequence, in more constraint
      34                 :             :    passes and even LRA infinite cycling.  Trivial the same hard
      35                 :             :    register moves will be removed by subsequent compiler passes.
      36                 :             : 
      37                 :             :    We don't coalesce special reload pseudos.  It complicates LRA code
      38                 :             :    a lot without visible generated code improvement.
      39                 :             : 
      40                 :             :    The pseudo live-ranges are used to find conflicting pseudos during
      41                 :             :    coalescing.
      42                 :             : 
      43                 :             :    Most frequently executed moves is tried to be coalesced first.  */
      44                 :             : 
      45                 :             : #include "config.h"
      46                 :             : #include "system.h"
      47                 :             : #include "coretypes.h"
      48                 :             : #include "backend.h"
      49                 :             : #include "rtl.h"
      50                 :             : #include "predict.h"
      51                 :             : #include "df.h"
      52                 :             : #include "insn-config.h"
      53                 :             : #include "regs.h"
      54                 :             : #include "memmodel.h"
      55                 :             : #include "ira.h"
      56                 :             : #include "recog.h"
      57                 :             : #include "lra-int.h"
      58                 :             : 
      59                 :             : /* Arrays whose elements represent the first and the next pseudo
      60                 :             :    (regno) in the coalesced pseudos group to which given pseudo (its
      61                 :             :    regno is the index) belongs.  The next of the last pseudo in the
      62                 :             :    group refers to the first pseudo in the group, in other words the
      63                 :             :    group is represented by a cyclic list.  */
      64                 :             : static int *first_coalesced_pseudo, *next_coalesced_pseudo;
      65                 :             : 
      66                 :             : /* The function is used to sort moves according to their execution
      67                 :             :    frequencies.  */
      68                 :             : static int
      69                 :       18205 : move_freq_compare_func (const void *v1p, const void *v2p)
      70                 :             : {
      71                 :       18205 :   rtx_insn *mv1 = *(rtx_insn * const *) v1p;
      72                 :       18205 :   rtx_insn *mv2 = *(rtx_insn * const *) v2p;
      73                 :       18205 :   int pri1, pri2;
      74                 :             : 
      75                 :       18205 :   pri1 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv1));
      76                 :       18205 :   pri2 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv2));
      77                 :       18205 :   if (pri2 - pri1)
      78                 :        7277 :     return pri2 - pri1;
      79                 :             : 
      80                 :             :   /* If frequencies are equal, sort by moves, so that the results of
      81                 :             :      qsort leave nothing to chance.  */
      82                 :       10928 :   return (int) INSN_UID (mv1) - (int) INSN_UID (mv2);
      83                 :             : }
      84                 :             : 
      85                 :             : /* Pseudos which go away after coalescing.  */
      86                 :             : static bitmap_head coalesced_pseudos_bitmap;
      87                 :             : 
      88                 :             : /* Merge two sets of coalesced pseudos given correspondingly by
      89                 :             :    pseudos REGNO1 and REGNO2 (more accurately merging REGNO2 group
      90                 :             :    into REGNO1 group).  Set up COALESCED_PSEUDOS_BITMAP.  */
      91                 :             : static void
      92                 :        1172 : merge_pseudos (int regno1, int regno2)
      93                 :             : {
      94                 :        1172 :   int regno, first, first2, last, next;
      95                 :             : 
      96                 :        1172 :   first = first_coalesced_pseudo[regno1];
      97                 :        1172 :   if ((first2 = first_coalesced_pseudo[regno2]) == first)
      98                 :             :     return;
      99                 :        1172 :   for (last = regno2, regno = next_coalesced_pseudo[regno2];;
     100                 :          48 :        regno = next_coalesced_pseudo[regno])
     101                 :             :     {
     102                 :        1220 :       first_coalesced_pseudo[regno] = first;
     103                 :        1220 :       bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
     104                 :        1220 :       if (regno == regno2)
     105                 :             :         break;
     106                 :          48 :       last = regno;
     107                 :             :     }
     108                 :        1172 :   next = next_coalesced_pseudo[first];
     109                 :        1172 :   next_coalesced_pseudo[first] = regno2;
     110                 :        1172 :   next_coalesced_pseudo[last] = next;
     111                 :        1172 :   lra_reg_info[first].live_ranges
     112                 :        1172 :     = (lra_merge_live_ranges
     113                 :        1172 :        (lra_reg_info[first].live_ranges,
     114                 :        1172 :         lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
     115                 :        1172 :   lra_update_biggest_mode (first, lra_reg_info[first2].biggest_mode);
     116                 :             : }
     117                 :             : 
     118                 :             : /* Change pseudos in *LOC on their coalescing group
     119                 :             :    representatives.  */
     120                 :             : static bool
     121                 :       82909 : substitute (rtx *loc)
     122                 :             : {
     123                 :       82909 :   int i, regno;
     124                 :       82909 :   const char *fmt;
     125                 :       82909 :   enum rtx_code code;
     126                 :       82909 :   bool res;
     127                 :             : 
     128                 :       82909 :   if (*loc == NULL_RTX)
     129                 :             :     return false;
     130                 :       72628 :   code = GET_CODE (*loc);
     131                 :       72628 :   if (code == REG)
     132                 :             :     {
     133                 :       30726 :       regno = REGNO (*loc);
     134                 :       30726 :       if (regno < FIRST_PSEUDO_REGISTER
     135                 :       27273 :           || first_coalesced_pseudo[regno] == regno)
     136                 :             :         return false;
     137                 :        6688 :       *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
     138                 :        6688 :       return true;
     139                 :             :     }
     140                 :             : 
     141                 :       41902 :   res = false;
     142                 :       41902 :   fmt = GET_RTX_FORMAT (code);
     143                 :      171373 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     144                 :             :     {
     145                 :      129471 :       if (fmt[i] == 'e')
     146                 :             :         {
     147                 :       69853 :           if (substitute (&XEXP (*loc, i)))
     148                 :      129471 :             res = true;
     149                 :             :         }
     150                 :       59618 :       else if (fmt[i] == 'E')
     151                 :             :         {
     152                 :        1410 :           int j;
     153                 :             : 
     154                 :        4185 :           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
     155                 :        2775 :             if (substitute (&XVECEXP (*loc, i, j)))
     156                 :         408 :               res = true;
     157                 :             :         }
     158                 :             :     }
     159                 :             :   return res;
     160                 :             : }
     161                 :             : 
     162                 :             : /* Specialize "substitute" for use on an insn.  This can't change
     163                 :             :    the insn ptr, just the contents of the insn.  */
     164                 :             : 
     165                 :             : static bool
     166                 :       10281 : substitute_within_insn (rtx_insn *insn)
     167                 :             : {
     168                 :       10281 :   rtx loc = insn;
     169                 :           0 :   return substitute (&loc);
     170                 :             : }
     171                 :             : 
     172                 :             : /* The current iteration (1, 2, ...) of the coalescing pass.  */
     173                 :             : int lra_coalesce_iter;
     174                 :             : 
     175                 :             : /* Return true if the move involving REGNO1 and REGNO2 is a potential
     176                 :             :    memory-memory move.  */
     177                 :             : static bool
     178                 :     3592189 : mem_move_p (int regno1, int regno2)
     179                 :             : {
     180                 :     3592189 :   return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
     181                 :             : }
     182                 :             : 
     183                 :             : /* Pseudos used instead of the coalesced pseudos.  */
     184                 :             : static bitmap_head used_pseudos_bitmap;
     185                 :             : 
     186                 :             : /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
     187                 :             :    bitmap).  */
     188                 :             : static void
     189                 :     3174588 : update_live_info (bitmap lr_bitmap)
     190                 :             : {
     191                 :     3174588 :   unsigned int j;
     192                 :     3174588 :   bitmap_iterator bi;
     193                 :             : 
     194                 :     3174588 :   bitmap_clear (&used_pseudos_bitmap);
     195                 :     3231834 :   EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
     196                 :             :                             FIRST_PSEUDO_REGISTER, j, bi)
     197                 :       57246 :     bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
     198                 :     3174588 :   if (! bitmap_empty_p (&used_pseudos_bitmap))
     199                 :             :     {
     200                 :       43506 :       bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
     201                 :       43506 :       bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
     202                 :             :     }
     203                 :     3174588 : }
     204                 :             : 
     205                 :             : /* Return true if pseudo REGNO can be potentially coalesced.  */
     206                 :             : static bool
     207                 :        6369 : coalescable_pseudo_p (int regno)
     208                 :             : {
     209                 :        6369 :   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
     210                 :        6369 :   return (/* We don't want to coalesce regnos with equivalences, at
     211                 :             :              least without updating this info.  */
     212                 :        6369 :           ira_reg_equiv[regno].constant == NULL_RTX
     213                 :        6369 :           && ira_reg_equiv[regno].memory == NULL_RTX
     214                 :       12737 :           && ira_reg_equiv[regno].invariant == NULL_RTX);
     215                 :             : }
     216                 :             : 
     217                 :             : /* The major function for aggressive pseudo coalescing of moves only
     218                 :             :    if the both pseudos were spilled and not special reload pseudos.  */
     219                 :             : bool
     220                 :       25986 : lra_coalesce (void)
     221                 :             : {
     222                 :       25986 :   basic_block bb;
     223                 :       25986 :   rtx_insn *mv, *insn, *next, **sorted_moves;
     224                 :       25986 :   rtx set;
     225                 :       25986 :   int i, mv_num, sregno, dregno;
     226                 :       25986 :   int coalesced_moves;
     227                 :       25986 :   int max_regno = max_reg_num ();
     228                 :       25986 :   bitmap_head involved_insns_bitmap;
     229                 :             : 
     230                 :       25986 :   timevar_push (TV_LRA_COALESCE);
     231                 :             : 
     232                 :       25986 :   if (lra_dump_file != NULL)
     233                 :           0 :     fprintf (lra_dump_file,
     234                 :             :              "\n********** Pseudos coalescing #%d: **********\n\n",
     235                 :             :              ++lra_coalesce_iter);
     236                 :       25986 :   first_coalesced_pseudo = XNEWVEC (int, max_regno);
     237                 :       25986 :   next_coalesced_pseudo = XNEWVEC (int, max_regno);
     238                 :    13531437 :   for (i = 0; i < max_regno; i++)
     239                 :    13505451 :     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
     240                 :       25986 :   sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
     241                 :       25986 :   mv_num = 0;
     242                 :             :   /* Collect moves.  */
     243                 :       25986 :   coalesced_moves = 0;
     244                 :     1613280 :   FOR_EACH_BB_FN (bb, cfun)
     245                 :             :     {
     246                 :    49281952 :       FOR_BB_INSNS_SAFE (bb, insn, next)
     247                 :    23053682 :         if (INSN_P (insn)
     248                 :    19388285 :             && (set = single_set (insn)) != NULL_RTX
     249                 :    12585717 :             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
     250                 :     4186469 :             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
     251                 :     3978191 :             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
     252                 :     3592189 :             && mem_move_p (sregno, dregno)
     253                 :        3185 :             && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
     254                 :        3184 :             && ! side_effects_p (set)
     255                 :    23056866 :             && !(lra_intersected_live_ranges_p
     256                 :        3184 :                  (lra_reg_info[sregno].live_ranges,
     257                 :        3184 :                   lra_reg_info[dregno].live_ranges)))
     258                 :        2159 :           sorted_moves[mv_num++] = insn;
     259                 :             :     }
     260                 :       25986 :   qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
     261                 :             :   /* Coalesced copies, most frequently executed first.  */
     262                 :       25986 :   bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
     263                 :       25986 :   bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
     264                 :       28145 :   for (i = 0; i < mv_num; i++)
     265                 :             :     {
     266                 :        2159 :       mv = sorted_moves[i];
     267                 :        2159 :       set = single_set (mv);
     268                 :        2159 :       lra_assert (set != NULL && REG_P (SET_SRC (set))
     269                 :             :                   && REG_P (SET_DEST (set)));
     270                 :        2159 :       sregno = REGNO (SET_SRC (set));
     271                 :        2159 :       dregno = REGNO (SET_DEST (set));
     272                 :        2159 :       if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
     273                 :             :         {
     274                 :         987 :           coalesced_moves++;
     275                 :         987 :           if (lra_dump_file != NULL)
     276                 :           0 :             fprintf
     277                 :           0 :               (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
     278                 :           0 :                INSN_UID (mv), sregno, dregno,
     279                 :           0 :                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
     280                 :             :           /* We updated involved_insns_bitmap when doing the merge.  */
     281                 :             :         }
     282                 :        1172 :       else if (!(lra_intersected_live_ranges_p
     283                 :        1172 :                  (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
     284                 :        1172 :                   lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
     285                 :             :         {
     286                 :        1172 :           coalesced_moves++;
     287                 :        1172 :           if (lra_dump_file != NULL)
     288                 :           0 :             fprintf
     289                 :           0 :               (lra_dump_file,
     290                 :             :                "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
     291                 :           0 :                INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
     292                 :           0 :                dregno, ORIGINAL_REGNO (SET_DEST (set)),
     293                 :           0 :                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
     294                 :        1172 :           bitmap_ior_into (&involved_insns_bitmap,
     295                 :        1172 :                            &lra_reg_info[sregno].insn_bitmap);
     296                 :        1172 :           bitmap_ior_into (&involved_insns_bitmap,
     297                 :        1172 :                            &lra_reg_info[dregno].insn_bitmap);
     298                 :        1172 :           merge_pseudos (sregno, dregno);
     299                 :             :         }
     300                 :             :     }
     301                 :       25986 :   bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
     302                 :     1613280 :   FOR_EACH_BB_FN (bb, cfun)
     303                 :             :     {
     304                 :     1587294 :       update_live_info (df_get_live_in (bb));
     305                 :     1587294 :       update_live_info (df_get_live_out (bb));
     306                 :    49281952 :       FOR_BB_INSNS_SAFE (bb, insn, next)
     307                 :    23053682 :         if (INSN_P (insn)
     308                 :    23053682 :             && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
     309                 :             :           {
     310                 :       10281 :             if (! substitute_within_insn (insn))
     311                 :        5504 :               continue;
     312                 :        4777 :             lra_update_insn_regno_info (insn);
     313                 :        4777 :             if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
     314                 :             :               {
     315                 :             :                 /* Coalesced move.  */
     316                 :        2159 :                 if (lra_dump_file != NULL)
     317                 :           0 :                   fprintf (lra_dump_file, "         Removing move %i (freq=%d)\n",
     318                 :           0 :                            INSN_UID (insn),
     319                 :           0 :                            REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
     320                 :        2159 :                 lra_set_insn_deleted (insn);
     321                 :             :               }
     322                 :             :           }
     323                 :             :     }
     324                 :             :   /* If we have situation after inheritance pass:
     325                 :             : 
     326                 :             :      r1 <- p1   insn originally setting p1
     327                 :             :      i1 <- r1   setting inheritance i1 from reload r1
     328                 :             :        ...
     329                 :             :      ... <- ... p2 ... dead p2
     330                 :             :      ..
     331                 :             :      p1 <- i1
     332                 :             :      r2 <- i1
     333                 :             :      ...<- ... r2 ...
     334                 :             : 
     335                 :             :      And we are coalescing p1 and p2 using p1.  In this case i1 and p1
     336                 :             :      should have different values, otherwise they can get the same
     337                 :             :      hard reg and this is wrong for insn using p2 before coalescing.
     338                 :             :      The situation even can be more complicated when new reload
     339                 :             :      pseudos occur after the inheriatnce.  So invalidate the result
     340                 :             :      pseudos.  */
     341                 :    13531437 :   for (i = 0; i < max_regno; i++)
     342                 :    13505451 :     if (first_coalesced_pseudo[i] == i
     343                 :    13504279 :         && first_coalesced_pseudo[i] != next_coalesced_pseudo[i])
     344                 :             :       {
     345                 :         941 :         lra_set_regno_unique_value (i);
     346                 :         941 :         if (lra_dump_file != NULL)
     347                 :           0 :           fprintf (lra_dump_file,
     348                 :             :                    "        Make unique value for coalescing result r%d\n", i);
     349                 :             :       }
     350                 :       25986 :   bitmap_clear (&used_pseudos_bitmap);
     351                 :       25986 :   bitmap_clear (&involved_insns_bitmap);
     352                 :       25986 :   bitmap_clear (&coalesced_pseudos_bitmap);
     353                 :       25986 :   if (lra_dump_file != NULL && coalesced_moves != 0)
     354                 :           0 :     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
     355                 :       25986 :   free (sorted_moves);
     356                 :       25986 :   free (next_coalesced_pseudo);
     357                 :       25986 :   free (first_coalesced_pseudo);
     358                 :       25986 :   timevar_pop (TV_LRA_COALESCE);
     359                 :       25986 :   return coalesced_moves != 0;
     360                 :             : }
        

Generated by: LCOV version 2.1-beta

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