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   int coalesced_moves;
 228   int max_regno = max_reg_num ();
 229   bitmap_head involved_insns_bitmap;
 230
 231   timevar_push (TV_LRA_COALESCE);
 232
 233   if (lra_dump_file != NULL)
 234     fprintf (lra_dump_file,
 235              "\n********** Pseudos coalescing #%d: **********\n\n",
 236              ++lra_coalesce_iter);
 237   first_coalesced_pseudo = XNEWVEC (int, max_regno);
 238   next_coalesced_pseudo = XNEWVEC (int, max_regno);
 239   for (i = 0; i < max_regno; i++)
 240     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
 241   sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
 242   mv_num = 0;
 243   /* Collect moves.  */
 244   coalesced_moves = 0;
 245   FOR_EACH_BB_FN (bb, cfun)
 246     {
 247       FOR_BB_INSNS_SAFE (bb, insn, next)
 248         if (INSN_P (insn)
 249             && (set = single_set (insn)) != NULL_RTX
 250             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 251             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 252             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 253             && mem_move_p (sregno, dregno)
 254             && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
 255             && ! side_effects_p (set)
 256             && !(lra_intersected_live_ranges_p
 257                  (lra_reg_info[sregno].live_ranges,
 258                   lra_reg_info[dregno].live_ranges)))
 259           sorted_moves[mv_num++] = insn;
 260     }
 261   qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
 262   /* Coalesced copies, most frequently executed first.  */
 263   bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
 264   bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
 265   for (i = 0; i < mv_num; i++)
 266     {
 267       mv = sorted_moves[i];
 268       set = single_set (mv);
 269       lra_assert (set != NULL && REG_P (SET_SRC (set))
 270                   && REG_P (SET_DEST (set)));
 271       sregno = REGNO (SET_SRC (set));
 272       dregno = REGNO (SET_DEST (set));
 273       if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
 274         {
 275           coalesced_moves++;
 276           if (lra_dump_file != NULL)
 277             fprintf
 278               (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
 279                INSN_UID (mv), sregno, dregno,
 280                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
 281           /* We updated involved_insns_bitmap when doing the merge.  */
 282         }
 283       else if (!(lra_intersected_live_ranges_p
 284                  (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
 285                   lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
 286         {
 287           coalesced_moves++;
 288           if (lra_dump_file != NULL)
 289             fprintf
 290               (lra_dump_file,
 291                "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
 292                INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
 293                dregno, ORIGINAL_REGNO (SET_DEST (set)),
 294                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
 295           bitmap_ior_into (&involved_insns_bitmap,
 296                            &lra_reg_info[sregno].insn_bitmap);
 297           bitmap_ior_into (&involved_insns_bitmap,
 298                            &lra_reg_info[dregno].insn_bitmap);
 299           merge_pseudos (sregno, dregno);
 300         }
 301     }
 302   bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
 303   FOR_EACH_BB_FN (bb, cfun)
 304     {
 305       update_live_info (df_get_live_in (bb));
 306       update_live_info (df_get_live_out (bb));
 307       FOR_BB_INSNS_SAFE (bb, insn, next)
 308         if (INSN_P (insn)
 309             && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
 310           {
 311             if (! substitute_within_insn (insn))
 312               continue;
 313             lra_update_insn_regno_info (insn);
 314             if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
 315               {
 316                 /* Coalesced move.  */
 317                 if (lra_dump_file != NULL)
 318                   fprintf (lra_dump_file, "      Removing move %i (freq=%d)\n",
 319                            INSN_UID (insn),
 320                            REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
 321                 lra_set_insn_deleted (insn);
 322               }
 323           }
 324     }
 325   /* If we have situation after inheritance pass:
 326
 327      r1 <- p1   insn originally setting p1
 328      i1 <- r1   setting inheritance i1 from reload r1
 329        ...
 330      ... <- ... p2 ... dead p2
 331      ..
 332      p1 <- i1
 333      r2 <- i1
 334      ...<- ... r2 ...
 335
 336      And we are coalescing p1 and p2 using p1.  In this case i1 and p1
 337      should have different values, otherwise they can get the same
 338      hard reg and this is wrong for insn using p2 before coalescing.
 339      The situation even can be more complicated when new reload
 340      pseudos occur after the inheriatnce.  So invalidate the result
 341      pseudos.  */
 342   for (i = 0; i < max_regno; i++)
 343     if (first_coalesced_pseudo[i] == i
 344         && first_coalesced_pseudo[i] != next_coalesced_pseudo[i])
 345       {
 346         lra_set_regno_unique_value (i);
 347         if (lra_dump_file != NULL)
 348           fprintf (lra_dump_file,
 349                    "     Make unique value for coalescing result r%d\n", i);
 350       }
 351   bitmap_clear (&used_pseudos_bitmap);
 352   bitmap_clear (&involved_insns_bitmap);
 353   bitmap_clear (&coalesced_pseudos_bitmap);
 354   if (lra_dump_file != NULL && coalesced_moves != 0)
 355     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
 356   free (sorted_moves);
 357   free (next_coalesced_pseudo);
 358   free (first_coalesced_pseudo);
 359   timevar_pop (TV_LRA_COALESCE);
 360   return coalesced_moves != 0;
 361 }