LCOV - code coverage report
Current view: top level - gcc - lra-coalesce.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 153 169 90.5 %
Date: 2020-03-28 11:57:23 Functions: 6 8 75.0 %
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-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 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                 :       3339 : move_freq_compare_func (const void *v1p, const void *v2p)
      70                 :            : {
      71                 :       3339 :   rtx_insn *mv1 = *(rtx_insn * const *) v1p;
      72                 :       3339 :   rtx_insn *mv2 = *(rtx_insn * const *) v2p;
      73                 :       3339 :   int pri1, pri2;
      74                 :            : 
      75                 :       3339 :   pri1 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv1));
      76                 :       3339 :   pri2 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv2));
      77                 :       3339 :   if (pri2 - pri1)
      78                 :       1699 :     return pri2 - pri1;
      79                 :            : 
      80                 :            :   /* If frequencies are equal, sort by moves, so that the results of
      81                 :            :      qsort leave nothing to chance.  */
      82                 :       1640 :   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                 :        597 : merge_pseudos (int regno1, int regno2)
      93                 :            : {
      94                 :        597 :   int regno, first, first2, last, next;
      95                 :            : 
      96                 :        597 :   first = first_coalesced_pseudo[regno1];
      97                 :        597 :   if ((first2 = first_coalesced_pseudo[regno2]) == first)
      98                 :            :     return;
      99                 :        597 :   for (last = regno2, regno = next_coalesced_pseudo[regno2];;
     100                 :          5 :        regno = next_coalesced_pseudo[regno])
     101                 :            :     {
     102                 :        602 :       first_coalesced_pseudo[regno] = first;
     103                 :        602 :       bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
     104                 :        602 :       if (regno == regno2)
     105                 :            :         break;
     106                 :          5 :       last = regno;
     107                 :            :     }
     108                 :        597 :   next = next_coalesced_pseudo[first];
     109                 :        597 :   next_coalesced_pseudo[first] = regno2;
     110                 :        597 :   next_coalesced_pseudo[last] = next;
     111                 :        597 :   lra_reg_info[first].live_ranges
     112                 :        597 :     = (lra_merge_live_ranges
     113                 :        597 :        (lra_reg_info[first].live_ranges,
     114                 :        597 :         lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
     115                 :        597 :   if (partial_subreg_p (lra_reg_info[first].biggest_mode,
     116                 :        597 :                         lra_reg_info[first2].biggest_mode))
     117                 :          0 :     lra_reg_info[first].biggest_mode = lra_reg_info[first2].biggest_mode;
     118                 :            : }
     119                 :            : 
     120                 :            : /* Change pseudos in *LOC on their coalescing group
     121                 :            :    representatives.  */
     122                 :            : static bool
     123                 :      55694 : substitute (rtx *loc)
     124                 :            : {
     125                 :      55694 :   int i, regno;
     126                 :      55694 :   const char *fmt;
     127                 :      55694 :   enum rtx_code code;
     128                 :      55694 :   bool res;
     129                 :            : 
     130                 :      55694 :   if (*loc == NULL_RTX)
     131                 :            :     return false;
     132                 :      48459 :   code = GET_CODE (*loc);
     133                 :      48459 :   if (code == REG)
     134                 :            :     {
     135                 :      20651 :       regno = REGNO (*loc);
     136                 :      20651 :       if (regno < FIRST_PSEUDO_REGISTER
     137                 :      17892 :           || first_coalesced_pseudo[regno] == regno)
     138                 :            :         return false;
     139                 :       5062 :       *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
     140                 :       5062 :       return true;
     141                 :            :     }
     142                 :            : 
     143                 :      27808 :   res = false;
     144                 :      27808 :   fmt = GET_RTX_FORMAT (code);
     145                 :     115763 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     146                 :            :     {
     147                 :      87955 :       if (fmt[i] == 'e')
     148                 :            :         {
     149                 :      45838 :           if (substitute (&XEXP (*loc, i)))
     150                 :      11144 :             res = true;
     151                 :            :         }
     152                 :      42117 :       else if (fmt[i] == 'E')
     153                 :            :         {
     154                 :       1321 :           int j;
     155                 :            : 
     156                 :       3942 :           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
     157                 :       2621 :             if (substitute (&XVECEXP (*loc, i, j)))
     158                 :        507 :               res = true;
     159                 :            :         }
     160                 :            :     }
     161                 :            :   return res;
     162                 :            : }
     163                 :            : 
     164                 :            : /* Specialize "substitute" for use on an insn.  This can't change
     165                 :            :    the insn ptr, just the contents of the insn.  */
     166                 :            : 
     167                 :            : static bool
     168                 :       7235 : substitute_within_insn (rtx_insn *insn)
     169                 :            : {
     170                 :       7235 :   rtx loc = insn;
     171                 :          0 :   return substitute (&loc);
     172                 :            : }
     173                 :            : 
     174                 :            : /* The current iteration (1, 2, ...) of the coalescing pass.  */
     175                 :            : int lra_coalesce_iter;
     176                 :            : 
     177                 :            : /* Return true if the move involving REGNO1 and REGNO2 is a potential
     178                 :            :    memory-memory move.  */
     179                 :            : static bool
     180                 :    2103410 : mem_move_p (int regno1, int regno2)
     181                 :            : {
     182                 :    2103410 :   return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
     183                 :            : }
     184                 :            : 
     185                 :            : /* Pseudos used instead of the coalesced pseudos.  */
     186                 :            : static bitmap_head used_pseudos_bitmap;
     187                 :            : 
     188                 :            : /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
     189                 :            :    bitmap).  */
     190                 :            : static void
     191                 :    2159040 : update_live_info (bitmap lr_bitmap)
     192                 :            : {
     193                 :    2159040 :   unsigned int j;
     194                 :    2159040 :   bitmap_iterator bi;
     195                 :            : 
     196                 :    2159040 :   bitmap_clear (&used_pseudos_bitmap);
     197                 :    2181570 :   EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
     198                 :            :                             FIRST_PSEUDO_REGISTER, j, bi)
     199                 :      22535 :     bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
     200                 :    2159040 :   if (! bitmap_empty_p (&used_pseudos_bitmap))
     201                 :            :     {
     202                 :      22448 :       bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
     203                 :      22448 :       bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
     204                 :            :     }
     205                 :    2159040 : }
     206                 :            : 
     207                 :            : /* Return true if pseudo REGNO can be potentially coalesced.  */
     208                 :            : static bool
     209                 :       3622 : coalescable_pseudo_p (int regno)
     210                 :            : {
     211                 :       3622 :   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
     212                 :       3622 :   return (/* We don't want to coalesce regnos with equivalences, at
     213                 :            :              least without updating this info.  */
     214                 :       3622 :           ira_reg_equiv[regno].constant == NULL_RTX
     215                 :       3618 :           && ira_reg_equiv[regno].memory == NULL_RTX
     216                 :       7194 :           && ira_reg_equiv[regno].invariant == NULL_RTX);
     217                 :            : }
     218                 :            : 
     219                 :            : /* The major function for aggressive pseudo coalescing of moves only
     220                 :            :    if the both pseudos were spilled and not special reload pseudos.  */
     221                 :            : bool
     222                 :      17467 : lra_coalesce (void)
     223                 :            : {
     224                 :      17467 :   basic_block bb;
     225                 :      17467 :   rtx_insn *mv, *insn, *next, **sorted_moves;
     226                 :      17467 :   rtx set;
     227                 :      17467 :   int i, mv_num, sregno, dregno;
     228                 :      17467 :   int coalesced_moves;
     229                 :      17467 :   int max_regno = max_reg_num ();
     230                 :      17467 :   bitmap_head involved_insns_bitmap;
     231                 :            :   
     232                 :      17467 :   timevar_push (TV_LRA_COALESCE);
     233                 :            : 
     234                 :      17467 :   if (lra_dump_file != NULL)
     235                 :          7 :     fprintf (lra_dump_file,
     236                 :            :              "\n********** Pseudos coalescing #%d: **********\n\n",
     237                 :            :              ++lra_coalesce_iter);
     238                 :      17467 :   first_coalesced_pseudo = XNEWVEC (int, max_regno);
     239                 :      17467 :   next_coalesced_pseudo = XNEWVEC (int, max_regno);
     240                 :    8224220 :   for (i = 0; i < max_regno; i++)
     241                 :    8206750 :     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
     242                 :      17467 :   sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
     243                 :      17467 :   mv_num = 0;
     244                 :            :   /* Collect moves.  */
     245                 :      17467 :   coalesced_moves = 0;
     246                 :    1096980 :   FOR_EACH_BB_FN (bb, cfun)
     247                 :            :     {
     248                 :   28492300 :       FOR_BB_INSNS_SAFE (bb, insn, next)
     249                 :   13166600 :         if (INSN_P (insn)
     250                 :   10775700 :             && (set = single_set (insn)) != NULL_RTX
     251                 :    8092330 :             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
     252                 :    2412690 :             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
     253                 :    2292350 :             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
     254                 :   13166600 :             && mem_move_p (sregno, dregno)
     255                 :       1836 :             && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
     256                 :       1786 :             && ! side_effects_p (set)
     257                 :   13168400 :             && !(lra_intersected_live_ranges_p
     258                 :       1786 :                  (lra_reg_info[sregno].live_ranges,
     259                 :       1786 :                   lra_reg_info[dregno].live_ranges)))
     260                 :        862 :           sorted_moves[mv_num++] = insn;
     261                 :            :     }
     262                 :      17467 :   qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
     263                 :            :   /* Coalesced copies, most frequently executed first.  */
     264                 :      17467 :   bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
     265                 :      17467 :   bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
     266                 :      18329 :   for (i = 0; i < mv_num; i++)
     267                 :            :     {
     268                 :        862 :       mv = sorted_moves[i];
     269                 :        862 :       set = single_set (mv);
     270                 :        862 :       lra_assert (set != NULL && REG_P (SET_SRC (set))
     271                 :            :                   && REG_P (SET_DEST (set)));
     272                 :        862 :       sregno = REGNO (SET_SRC (set));
     273                 :        862 :       dregno = REGNO (SET_DEST (set));
     274                 :        862 :       if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
     275                 :            :         {
     276                 :        265 :           coalesced_moves++;
     277                 :        265 :           if (lra_dump_file != NULL)
     278                 :          0 :             fprintf
     279                 :          0 :               (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
     280                 :          0 :                INSN_UID (mv), sregno, dregno,
     281                 :          0 :                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
     282                 :            :           /* We updated involved_insns_bitmap when doing the merge.  */
     283                 :            :         }
     284                 :        597 :       else if (!(lra_intersected_live_ranges_p
     285                 :        597 :                  (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
     286                 :        597 :                   lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
     287                 :            :         {
     288                 :        597 :           coalesced_moves++;
     289                 :        597 :           if (lra_dump_file != NULL)
     290                 :          0 :             fprintf
     291                 :          0 :               (lra_dump_file,
     292                 :            :                "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
     293                 :          0 :                INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
     294                 :          0 :                dregno, ORIGINAL_REGNO (SET_DEST (set)),
     295                 :          0 :                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
     296                 :        597 :           bitmap_ior_into (&involved_insns_bitmap,
     297                 :        597 :                            &lra_reg_info[sregno].insn_bitmap);
     298                 :        597 :           bitmap_ior_into (&involved_insns_bitmap,
     299                 :        597 :                            &lra_reg_info[dregno].insn_bitmap);
     300                 :        597 :           merge_pseudos (sregno, dregno);
     301                 :            :         }
     302                 :            :     }
     303                 :      17467 :   bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
     304                 :    1096980 :   FOR_EACH_BB_FN (bb, cfun)
     305                 :            :     {
     306                 :    1079520 :       update_live_info (df_get_live_in (bb));
     307                 :    1079520 :       update_live_info (df_get_live_out (bb));
     308                 :   28492300 :       FOR_BB_INSNS_SAFE (bb, insn, next)
     309                 :   13166600 :         if (INSN_P (insn)
     310                 :   13166600 :             && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
     311                 :            :           {
     312                 :       7235 :             if (! substitute_within_insn (insn))
     313                 :       3141 :               continue;
     314                 :       4094 :             lra_update_insn_regno_info (insn);
     315                 :       4094 :             if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
     316                 :            :               {
     317                 :            :                 /* Coalesced move.  */
     318                 :        862 :                 if (lra_dump_file != NULL)
     319                 :          0 :                   fprintf (lra_dump_file, "         Removing move %i (freq=%d)\n",
     320                 :          0 :                            INSN_UID (insn),
     321                 :          0 :                            REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
     322                 :        862 :                 lra_set_insn_deleted (insn);
     323                 :            :               }
     324                 :            :           }
     325                 :            :     }
     326                 :            :   /* If we have situation after inheritance pass:
     327                 :            : 
     328                 :            :      r1 <- p1   insn originally setting p1
     329                 :            :      i1 <- r1   setting inheritance i1 from reload r1
     330                 :            :        ...
     331                 :            :      ... <- ... p2 ... dead p2
     332                 :            :      ..
     333                 :            :      p1 <- i1
     334                 :            :      r2 <- i1
     335                 :            :      ...<- ... r2 ...
     336                 :            : 
     337                 :            :      And we are coalescing p1 and p2 using p1.  In this case i1 and p1
     338                 :            :      should have different values, otherwise they can get the same
     339                 :            :      hard reg and this is wrong for insn using p2 before coalescing.
     340                 :            :      The situation even can be more complicated when new reload
     341                 :            :      pseudos occur after the inheriatnce.  So invalidate the result
     342                 :            :      pseudos.  */
     343                 :    8224220 :   for (i = 0; i < max_regno; i++)
     344                 :    8206750 :     if (first_coalesced_pseudo[i] == i
     345                 :    8206150 :         && first_coalesced_pseudo[i] != next_coalesced_pseudo[i])
     346                 :            :       {
     347                 :        560 :         lra_set_regno_unique_value (i);
     348                 :        560 :         if (lra_dump_file != NULL)
     349                 :          0 :           fprintf (lra_dump_file,
     350                 :            :                    "        Make unique value for coalescing result r%d\n", i);
     351                 :            :       }
     352                 :      17467 :   bitmap_clear (&used_pseudos_bitmap);
     353                 :      17467 :   bitmap_clear (&involved_insns_bitmap);
     354                 :      17467 :   bitmap_clear (&coalesced_pseudos_bitmap);
     355                 :      17467 :   if (lra_dump_file != NULL && coalesced_moves != 0)
     356                 :          0 :     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
     357                 :      17467 :   free (sorted_moves);
     358                 :      17467 :   free (next_coalesced_pseudo);
     359                 :      17467 :   free (first_coalesced_pseudo);
     360                 :      17467 :   timevar_pop (TV_LRA_COALESCE);
     361                 :      17467 :   return coalesced_moves != 0;
     362                 :            : }

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.