gcc/lra-coalesce.c

   1 /* Coalesce spilled pseudos.
   2    Copyright (C) 2010-2017 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 move_freq_compare_func (const void *v1p, const void *v2p)
  70 {
  71   rtx_insn *mv1 = *(rtx_insn * const *) v1p;
  72   rtx_insn *mv2 = *(rtx_insn * const *) v2p;
  73   int pri1, pri2;
  74
  75   pri1 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv1));
  76   pri2 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv2));
  77   if (pri2 - pri1)
  78     return pri2 - pri1;
  79
  80   /* If frequencies are equal, sort by moves, so that the results of
  81      qsort leave nothing to chance.  */
  82   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 merge_pseudos (int regno1, int regno2)
  93 {
  94   int regno, first, first2, last, next;
  95
  96   first = first_coalesced_pseudo[regno1];
  97   if ((first2 = first_coalesced_pseudo[regno2]) == first)
  98     return;
  99   for (last = regno2, regno = next_coalesced_pseudo[regno2];;
 100        regno = next_coalesced_pseudo[regno])
 101     {
 102       first_coalesced_pseudo[regno] = first;
 103       bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
 104       if (regno == regno2)
 105         break;
 106       last = regno;
 107     }
 108   next = next_coalesced_pseudo[first];
 109   next_coalesced_pseudo[first] = regno2;
 110   next_coalesced_pseudo[last] = next;
 111   lra_reg_info[first].live_ranges
 112     = (lra_merge_live_ranges
 113        (lra_reg_info[first].live_ranges,
 114         lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
 115   if (GET_MODE_SIZE (lra_reg_info[first].biggest_mode)
 116       < GET_MODE_SIZE (lra_reg_info[first2].biggest_mode))
 117     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 substitute (rtx *loc)
 124 {
 125   int i, regno;
 126   const char *fmt;
 127   enum rtx_code code;
 128   bool res;
 129
 130   if (*loc == NULL_RTX)
 131     return false;
 132   code = GET_CODE (*loc);
 133   if (code == REG)
 134     {
 135       regno = REGNO (*loc);
 136       if (regno < FIRST_PSEUDO_REGISTER
 137           || first_coalesced_pseudo[regno] == regno)
 138         return false;
 139       *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
 140       return true;
 141     }
 142
 143   res = false;
 144   fmt = GET_RTX_FORMAT (code);
 145   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 146     {
 147       if (fmt[i] == 'e')
 148         {
 149           if (substitute (&XEXP (*loc, i)))
 150             res = true;
 151         }
 152       else if (fmt[i] == 'E')
 153         {
 154           int j;
 155
 156           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 157             if (substitute (&XVECEXP (*loc, i, j)))
 158               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 substitute_within_insn (rtx_insn *insn)
 169 {
 170   rtx loc = insn;
 171   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 mem_move_p (int regno1, int regno2)
 181 {
 182   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 update_live_info (bitmap lr_bitmap)
 192 {
 193   unsigned int j;
 194   bitmap_iterator bi;
 195
 196   bitmap_clear (&used_pseudos_bitmap);
 197   EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
 198                             FIRST_PSEUDO_REGISTER, j, bi)
 199     bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
 200   if (! bitmap_empty_p (&used_pseudos_bitmap))
 201     {
 202       bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
 203       bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
 204     }
 205 }
 206
 207 /* Return true if pseudo REGNO can be potentially coalesced.  */
 208 static bool
 209 coalescable_pseudo_p (int regno)
 210 {
 211   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 212   return (/* We don't want to coalesce regnos with equivalences, at
 213              least without updating this info.  */
 214           ira_reg_equiv[regno].constant == NULL_RTX
 215           && ira_reg_equiv[regno].memory == NULL_RTX
 216           && 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 lra_coalesce (void)
 223 {
 224   basic_block bb;
 225   rtx_insn *mv, *insn, *next, **sorted_moves;
 226   rtx set;
 227   int i, mv_num, sregno, dregno;
 228   int coalesced_moves;
 229   int max_regno = max_reg_num ();
 230   bitmap_head involved_insns_bitmap;
 231
 232   timevar_push (TV_LRA_COALESCE);
 233
 234   if (lra_dump_file != NULL)
 235     fprintf (lra_dump_file,
 236              "\n********** Pseudos coalescing #%d: **********\n\n",
 237              ++lra_coalesce_iter);
 238   first_coalesced_pseudo = XNEWVEC (int, max_regno);
 239   next_coalesced_pseudo = XNEWVEC (int, max_regno);
 240   for (i = 0; i < max_regno; i++)
 241     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
 242   sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
 243   mv_num = 0;
 244   /* Collect moves.  */
 245   coalesced_moves = 0;
 246   FOR_EACH_BB_FN (bb, cfun)
 247     {
 248       FOR_BB_INSNS_SAFE (bb, insn, next)
 249         if (INSN_P (insn)
 250             && (set = single_set (insn)) != NULL_RTX
 251             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 252             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 253             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 254             && mem_move_p (sregno, dregno)
 255             && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
 256             && ! side_effects_p (set)
 257             && !(lra_intersected_live_ranges_p
 258                  (lra_reg_info[sregno].live_ranges,
 259                   lra_reg_info[dregno].live_ranges)))
 260           sorted_moves[mv_num++] = insn;
 261     }
 262   qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
 263   /* Coalesced copies, most frequently executed first.  */
 264   bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
 265   bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
 266   for (i = 0; i < mv_num; i++)
 267     {
 268       mv = sorted_moves[i];
 269       set = single_set (mv);
 270       lra_assert (set != NULL && REG_P (SET_SRC (set))
 271                   && REG_P (SET_DEST (set)));
 272       sregno = REGNO (SET_SRC (set));
 273       dregno = REGNO (SET_DEST (set));
 274       if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
 275         {
 276           coalesced_moves++;
 277           if (lra_dump_file != NULL)
 278             fprintf
 279               (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
 280                INSN_UID (mv), sregno, dregno,
 281                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
 282           /* We updated involved_insns_bitmap when doing the merge.  */
 283         }
 284       else if (!(lra_intersected_live_ranges_p
 285                  (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
 286                   lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
 287         {
 288           coalesced_moves++;
 289           if (lra_dump_file != NULL)
 290             fprintf
 291               (lra_dump_file,
 292                "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
 293                INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
 294                dregno, ORIGINAL_REGNO (SET_DEST (set)),
 295                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
 296           bitmap_ior_into (&involved_insns_bitmap,
 297                            &lra_reg_info[sregno].insn_bitmap);
 298           bitmap_ior_into (&involved_insns_bitmap,
 299                            &lra_reg_info[dregno].insn_bitmap);
 300           merge_pseudos (sregno, dregno);
 301         }
 302     }
 303   bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
 304   FOR_EACH_BB_FN (bb, cfun)
 305     {
 306       update_live_info (df_get_live_in (bb));
 307       update_live_info (df_get_live_out (bb));
 308       FOR_BB_INSNS_SAFE (bb, insn, next)
 309         if (INSN_P (insn)
 310             && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
 311           {
 312             if (! substitute_within_insn (insn))
 313               continue;
 314             lra_update_insn_regno_info (insn);
 315             if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
 316               {
 317                 /* Coalesced move.  */
 318                 if (lra_dump_file != NULL)
 319                   fprintf (lra_dump_file, "      Removing move %i (freq=%d)\n",
 320                            INSN_UID (insn),
 321                            REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
 322                 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   for (i = 0; i < max_regno; i++)
 344     if (first_coalesced_pseudo[i] == i
 345         && first_coalesced_pseudo[i] != next_coalesced_pseudo[i])
 346       {
 347         lra_set_regno_unique_value (i);
 348         if (lra_dump_file != NULL)
 349           fprintf (lra_dump_file,
 350                    "     Make unique value for coalescing result r%d\n", i);
 351       }
 352   bitmap_clear (&used_pseudos_bitmap);
 353   bitmap_clear (&involved_insns_bitmap);
 354   bitmap_clear (&coalesced_pseudos_bitmap);
 355   if (lra_dump_file != NULL && coalesced_moves != 0)
 356     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
 357   free (sorted_moves);
 358   free (next_coalesced_pseudo);
 359   free (first_coalesced_pseudo);
 360   timevar_pop (TV_LRA_COALESCE);
 361   return coalesced_moves != 0;
 362 }