gcc/lra-coalesce.c

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