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.  */
 205 static bool
 206 coalescable_pseudo_p (int regno)
 207 {
 208   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 209   return (/* We don't want to coalesce regnos with equivalences, at
 210              least without updating this info.  */
 211           ira_reg_equiv[regno].constant == NULL_RTX
 212           && ira_reg_equiv[regno].memory == NULL_RTX
 213           && ira_reg_equiv[regno].invariant == NULL_RTX);
 214 }
 215
 216 /* The major function for aggressive pseudo coalescing of moves only
 217    if the both pseudos were spilled and not special reload pseudos.  */
 218 bool
 219 lra_coalesce (void)
 220 {
 221   basic_block bb;
 222   rtx mv, set, insn, next, *sorted_moves;
 223   int i, mv_num, sregno, dregno;
 224   unsigned int regno;
 225   int coalesced_moves;
 226   int max_regno = max_reg_num ();
 227   bitmap_head involved_insns_bitmap;
 228   bitmap_head result_pseudo_vals_bitmap;
 229   bitmap_iterator bi;
 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, 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                BLOCK_FOR_INSN (mv)->frequency);
 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                BLOCK_FOR_INSN (mv)->frequency);
 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 (&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), BLOCK_FOR_INSN (insn)->frequency);
 320                 lra_set_insn_deleted (insn);
 321               }
 322           }
 323     }
 324   /* If we have situation after inheritance pass:
 325
 326      r1 <- ...  insn originally setting p1
 327      i1 <- r1   setting inheritance i1 from reload r1
 328        ...
 329      ... <- ... p2 ... dead p2
 330      ..
 331      p1 <- i1
 332      r2 <- i1
 333      ...<- ... r2 ...
 334
 335      And we are coalescing p1 and p2 using p1.  In this case i1 and p1
 336      should have different values, otherwise they can get the same
 337      hard reg and this is wrong for insn using p2 before coalescing.
 338      So invalidate such inheritance pseudo values.  */
 339   bitmap_initialize (&result_pseudo_vals_bitmap, &reg_obstack);
 340   EXECUTE_IF_SET_IN_BITMAP (&coalesced_pseudos_bitmap, 0, regno, bi)
 341     bitmap_set_bit (&result_pseudo_vals_bitmap,
 342                     lra_reg_info[first_coalesced_pseudo[regno]].val);
 343   EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi)
 344     if (bitmap_bit_p (&result_pseudo_vals_bitmap, lra_reg_info[regno].val))
 345       {
 346         lra_set_regno_unique_value (regno);
 347         if (lra_dump_file != NULL)
 348           fprintf (lra_dump_file,
 349                    "     Make unique value for inheritance r%d\n", regno);
 350       }
 351   bitmap_clear (&result_pseudo_vals_bitmap);
 352   bitmap_clear (&used_pseudos_bitmap);
 353   bitmap_clear (&involved_insns_bitmap);
 354   bitmap_clear (&coalesced_pseudos_bitmap);
 355   if (lra_dump_file != NULL && coalesced_moves != 0)
 356     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
 357   free (sorted_moves);
 358   free (next_coalesced_pseudo);
 359   free (first_coalesced_pseudo);
 360   timevar_pop (TV_LRA_COALESCE);
 361   return coalesced_moves != 0;
 362 }