gcc/lra-coalesce.c

   1 /* Coalesce spilled pseudos.
   2    Copyright (C) 2010-2013 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 "expr.h"
  59 #include "basic-block.h"
  60 #include "except.h"
  61 #include "timevar.h"
  62 #include "ira.h"
  63 #include "lra-int.h"
  64 #include "df.h"
  65
  66 /* Arrays whose elements represent the first and the next pseudo
  67    (regno) in the coalesced pseudos group to which given pseudo (its
  68    regno is the index) belongs.  The next of the last pseudo in the
  69    group refers to the first pseudo in the group, in other words the
  70    group is represented by a cyclic list.  */
  71 static int *first_coalesced_pseudo, *next_coalesced_pseudo;
  72
  73 /* The function is used to sort moves according to their execution
  74    frequencies.  */
  75 static int
  76 move_freq_compare_func (const void *v1p, const void *v2p)
  77 {
  78   rtx mv1 = *(const rtx *) v1p;
  79   rtx mv2 = *(const rtx *) v2p;
  80   int pri1, pri2;
  81
  82   pri1 = BLOCK_FOR_INSN (mv1)->frequency;
  83   pri2 = BLOCK_FOR_INSN (mv2)->frequency;
  84   if (pri2 - pri1)
  85     return pri2 - pri1;
  86
  87   /* If frequencies are equal, sort by moves, so that the results of
  88      qsort leave nothing to chance.  */
  89   return (int) INSN_UID (mv1) - (int) INSN_UID (mv2);
  90 }
  91
  92 /* Pseudos which go away after coalescing.  */
  93 static bitmap_head coalesced_pseudos_bitmap;
  94
  95 /* Merge two sets of coalesced pseudos given correspondingly by
  96    pseudos REGNO1 and REGNO2 (more accurately merging REGNO2 group
  97    into REGNO1 group).  Set up COALESCED_PSEUDOS_BITMAP.  */
  98 static void
  99 merge_pseudos (int regno1, int regno2)
 100 {
 101   int regno, first, first2, last, next;
 102
 103   first = first_coalesced_pseudo[regno1];
 104   if ((first2 = first_coalesced_pseudo[regno2]) == first)
 105     return;
 106   for (last = regno2, regno = next_coalesced_pseudo[regno2];;
 107        regno = next_coalesced_pseudo[regno])
 108     {
 109       first_coalesced_pseudo[regno] = first;
 110       bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
 111       if (regno == regno2)
 112         break;
 113       last = regno;
 114     }
 115   next = next_coalesced_pseudo[first];
 116   next_coalesced_pseudo[first] = regno2;
 117   next_coalesced_pseudo[last] = next;
 118   lra_reg_info[first].live_ranges
 119     = (lra_merge_live_ranges
 120        (lra_reg_info[first].live_ranges,
 121         lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
 122   if (GET_MODE_SIZE (lra_reg_info[first].biggest_mode)
 123       < GET_MODE_SIZE (lra_reg_info[first2].biggest_mode))
 124     lra_reg_info[first].biggest_mode = lra_reg_info[first2].biggest_mode;
 125 }
 126
 127 /* Change pseudos in *LOC on their coalescing group
 128    representatives.  */
 129 static bool
 130 substitute (rtx *loc)
 131 {
 132   int i, regno;
 133   const char *fmt;
 134   enum rtx_code code;
 135   bool res;
 136
 137   if (*loc == NULL_RTX)
 138     return false;
 139   code = GET_CODE (*loc);
 140   if (code == REG)
 141     {
 142       regno = REGNO (*loc);
 143       if (regno < FIRST_PSEUDO_REGISTER
 144           || first_coalesced_pseudo[regno] == regno)
 145         return false;
 146       *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
 147       return true;
 148     }
 149
 150   res = false;
 151   fmt = GET_RTX_FORMAT (code);
 152   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 153     {
 154       if (fmt[i] == 'e')
 155         {
 156           if (substitute (&XEXP (*loc, i)))
 157             res = true;
 158         }
 159       else if (fmt[i] == 'E')
 160         {
 161           int j;
 162
 163           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 164             if (substitute (&XVECEXP (*loc, i, j)))
 165               res = true;
 166         }
 167     }
 168   return res;
 169 }
 170
 171 /* The current iteration (1, 2, ...) of the coalescing pass.  */
 172 int lra_coalesce_iter;
 173
 174 /* Return true if the move involving REGNO1 and REGNO2 is a potential
 175    memory-memory move.  */
 176 static bool
 177 mem_move_p (int regno1, int regno2)
 178 {
 179   return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
 180 }
 181
 182 /* Pseudos used instead of the coalesced pseudos.  */
 183 static bitmap_head used_pseudos_bitmap;
 184
 185 /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
 186    bitmap).  */
 187 static void
 188 update_live_info (bitmap lr_bitmap)
 189 {
 190   unsigned int j;
 191   bitmap_iterator bi;
 192
 193   bitmap_clear (&used_pseudos_bitmap);
 194   EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
 195                             FIRST_PSEUDO_REGISTER, j, bi)
 196     bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
 197   if (! bitmap_empty_p (&used_pseudos_bitmap))
 198     {
 199       bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
 200       bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
 201     }
 202 }
 203
 204 /* Return true if pseudo REGNO can be potentially coalesced.  Use
 205    SPLIT_PSEUDO_BITMAP to find pseudos whose live ranges were
 206    split.  */
 207 static bool
 208 coalescable_pseudo_p (int regno, bitmap split_origin_bitmap)
 209 {
 210   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 211   /* Don't coalesce inheritance pseudos because spilled inheritance
 212      pseudos will be removed in subsequent 'undo inheritance'
 213      pass.  */
 214   return (lra_reg_info[regno].restore_regno < 0
 215           /* We undo splits for spilled pseudos whose live ranges were
 216              split.  So don't coalesce them, it is not necessary and
 217              the undo transformations would be wrong.  */
 218           && ! bitmap_bit_p (split_origin_bitmap, regno)
 219           /* We don't want to coalesce regnos with equivalences, at
 220              least without updating this info.  */
 221           && ira_reg_equiv[regno].constant == NULL_RTX
 222           && ira_reg_equiv[regno].memory == NULL_RTX
 223           && ira_reg_equiv[regno].invariant == NULL_RTX);
 224 }
 225
 226 /* The major function for aggressive pseudo coalescing of moves only
 227    if the both pseudos were spilled and not special reload pseudos.  */
 228 bool
 229 lra_coalesce (void)
 230 {
 231   basic_block bb;
 232   rtx mv, set, insn, next, *sorted_moves;
 233   int i, mv_num, sregno, dregno, restore_regno;
 234   unsigned int regno;
 235   int coalesced_moves;
 236   int max_regno = max_reg_num ();
 237   bitmap_head involved_insns_bitmap, split_origin_bitmap;
 238   bitmap_iterator bi;
 239
 240   timevar_push (TV_LRA_COALESCE);
 241
 242   if (lra_dump_file != NULL)
 243     fprintf (lra_dump_file,
 244              "\n********** Pseudos coalescing #%d: **********\n\n",
 245              ++lra_coalesce_iter);
 246   first_coalesced_pseudo = XNEWVEC (int, max_regno);
 247   next_coalesced_pseudo = XNEWVEC (int, max_regno);
 248   for (i = 0; i < max_regno; i++)
 249     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
 250   sorted_moves = XNEWVEC (rtx, get_max_uid ());
 251   mv_num = 0;
 252   /* Collect pseudos whose live ranges were split.  */
 253   bitmap_initialize (&split_origin_bitmap, &reg_obstack);
 254   EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, regno, bi)
 255     if ((restore_regno = lra_reg_info[regno].restore_regno) >= 0)
 256       bitmap_set_bit (&split_origin_bitmap, restore_regno);
 257   /* Collect moves.  */
 258   coalesced_moves = 0;
 259   FOR_EACH_BB (bb)
 260     {
 261       FOR_BB_INSNS_SAFE (bb, insn, next)
 262         if (INSN_P (insn)
 263             && (set = single_set (insn)) != NULL_RTX
 264             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 265             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 266             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 267             && mem_move_p (sregno, dregno)
 268             && coalescable_pseudo_p (sregno, &split_origin_bitmap)
 269             && coalescable_pseudo_p (dregno, &split_origin_bitmap)
 270             && ! side_effects_p (set)
 271             && !(lra_intersected_live_ranges_p
 272                  (lra_reg_info[sregno].live_ranges,
 273                   lra_reg_info[dregno].live_ranges)))
 274           sorted_moves[mv_num++] = insn;
 275     }
 276   bitmap_clear (&split_origin_bitmap);
 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                BLOCK_FOR_INSN (mv)->frequency);
 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                BLOCK_FOR_INSN (mv)->frequency);
 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 (bb)
 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 (&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), BLOCK_FOR_INSN (insn)->frequency);
 336                 lra_set_insn_deleted (insn);
 337               }
 338           }
 339     }
 340   bitmap_clear (&used_pseudos_bitmap);
 341   bitmap_clear (&involved_insns_bitmap);
 342   bitmap_clear (&coalesced_pseudos_bitmap);
 343   if (lra_dump_file != NULL && coalesced_moves != 0)
 344     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
 345   free (sorted_moves);
 346   free (next_coalesced_pseudo);
 347   free (first_coalesced_pseudo);
 348   timevar_pop (TV_LRA_COALESCE);
 349   return coalesced_moves != 0;
 350 }