gcc/lra-coalesce.c

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