gcc/lra-coalesce.c

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