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 "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_insn *mv1 = *(rtx_insn * const *) v1p;
  79   rtx_insn *mv2 = *(rtx_insn * const *) v2p;
  80   int pri1, pri2;
  81
  82   pri1 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv1));
  83   pri2 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv2));
  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 /* Specialize "substitute" for use on an insn.  This can't change
 172    the insn ptr, just the contents of the insn.  */
 173
 174 static bool
 175 substitute_within_insn (rtx_insn *insn)
 176 {
 177   rtx loc = insn;
 178   return substitute (&loc);
 179 }
 180
 181 /* The current iteration (1, 2, ...) of the coalescing pass.  */
 182 int lra_coalesce_iter;
 183
 184 /* Return true if the move involving REGNO1 and REGNO2 is a potential
 185    memory-memory move.  */
 186 static bool
 187 mem_move_p (int regno1, int regno2)
 188 {
 189   return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
 190 }
 191
 192 /* Pseudos used instead of the coalesced pseudos.  */
 193 static bitmap_head used_pseudos_bitmap;
 194
 195 /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
 196    bitmap).  */
 197 static void
 198 update_live_info (bitmap lr_bitmap)
 199 {
 200   unsigned int j;
 201   bitmap_iterator bi;
 202
 203   bitmap_clear (&used_pseudos_bitmap);
 204   EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
 205                             FIRST_PSEUDO_REGISTER, j, bi)
 206     bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
 207   if (! bitmap_empty_p (&used_pseudos_bitmap))
 208     {
 209       bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
 210       bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
 211     }
 212 }
 213
 214 /* Return true if pseudo REGNO can be potentially coalesced.  */
 215 static bool
 216 coalescable_pseudo_p (int regno)
 217 {
 218   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 219   return (/* 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_insn *mv, *insn, *next, **sorted_moves;
 233   rtx set;
 234   int i, mv_num, sregno, dregno;
 235   unsigned int regno;
 236   int coalesced_moves;
 237   int max_regno = max_reg_num ();
 238   bitmap_head involved_insns_bitmap;
 239   bitmap_head result_pseudo_vals_bitmap;
 240   bitmap_iterator bi;
 241
 242   timevar_push (TV_LRA_COALESCE);
 243
 244   if (lra_dump_file != NULL)
 245     fprintf (lra_dump_file,
 246              "\n********** Pseudos coalescing #%d: **********\n\n",
 247              ++lra_coalesce_iter);
 248   first_coalesced_pseudo = XNEWVEC (int, max_regno);
 249   next_coalesced_pseudo = XNEWVEC (int, max_regno);
 250   for (i = 0; i < max_regno; i++)
 251     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
 252   sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
 253   mv_num = 0;
 254   /* Collect moves.  */
 255   coalesced_moves = 0;
 256   FOR_EACH_BB_FN (bb, cfun)
 257     {
 258       FOR_BB_INSNS_SAFE (bb, insn, next)
 259         if (INSN_P (insn)
 260             && (set = single_set (insn)) != NULL_RTX
 261             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 262             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 263             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 264             && mem_move_p (sregno, dregno)
 265             && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
 266             && ! side_effects_p (set)
 267             && !(lra_intersected_live_ranges_p
 268                  (lra_reg_info[sregno].live_ranges,
 269                   lra_reg_info[dregno].live_ranges)))
 270           sorted_moves[mv_num++] = insn;
 271     }
 272   qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
 273   /* Coalesced copies, most frequently executed first.  */
 274   bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
 275   bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
 276   for (i = 0; i < mv_num; i++)
 277     {
 278       mv = sorted_moves[i];
 279       set = single_set (mv);
 280       lra_assert (set != NULL && REG_P (SET_SRC (set))
 281                   && REG_P (SET_DEST (set)));
 282       sregno = REGNO (SET_SRC (set));
 283       dregno = REGNO (SET_DEST (set));
 284       if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
 285         {
 286           coalesced_moves++;
 287           if (lra_dump_file != NULL)
 288             fprintf
 289               (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
 290                INSN_UID (mv), sregno, dregno,
 291                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
 292           /* We updated involved_insns_bitmap when doing the merge.  */
 293         }
 294       else if (!(lra_intersected_live_ranges_p
 295                  (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
 296                   lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
 297         {
 298           coalesced_moves++;
 299           if (lra_dump_file != NULL)
 300             fprintf
 301               (lra_dump_file,
 302                "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
 303                INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
 304                dregno, ORIGINAL_REGNO (SET_DEST (set)),
 305                REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
 306           bitmap_ior_into (&involved_insns_bitmap,
 307                            &lra_reg_info[sregno].insn_bitmap);
 308           bitmap_ior_into (&involved_insns_bitmap,
 309                            &lra_reg_info[dregno].insn_bitmap);
 310           merge_pseudos (sregno, dregno);
 311         }
 312     }
 313   bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
 314   FOR_EACH_BB_FN (bb, cfun)
 315     {
 316       update_live_info (df_get_live_in (bb));
 317       update_live_info (df_get_live_out (bb));
 318       FOR_BB_INSNS_SAFE (bb, insn, next)
 319         if (INSN_P (insn)
 320             && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
 321           {
 322             if (! substitute_within_insn (insn))
 323               continue;
 324             lra_update_insn_regno_info (insn);
 325             if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
 326               {
 327                 /* Coalesced move.  */
 328                 if (lra_dump_file != NULL)
 329                   fprintf (lra_dump_file, "      Removing move %i (freq=%d)\n",
 330                            INSN_UID (insn),
 331                            REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
 332                 lra_set_insn_deleted (insn);
 333               }
 334           }
 335     }
 336   /* If we have situation after inheritance pass:
 337
 338      r1 <- ...  insn originally setting p1
 339      i1 <- r1   setting inheritance i1 from reload r1
 340        ...
 341      ... <- ... p2 ... dead p2
 342      ..
 343      p1 <- i1
 344      r2 <- i1
 345      ...<- ... r2 ...
 346
 347      And we are coalescing p1 and p2 using p1.  In this case i1 and p1
 348      should have different values, otherwise they can get the same
 349      hard reg and this is wrong for insn using p2 before coalescing.
 350      So invalidate such inheritance pseudo values.  */
 351   bitmap_initialize (&result_pseudo_vals_bitmap, &reg_obstack);
 352   EXECUTE_IF_SET_IN_BITMAP (&coalesced_pseudos_bitmap, 0, regno, bi)
 353     bitmap_set_bit (&result_pseudo_vals_bitmap,
 354                     lra_reg_info[first_coalesced_pseudo[regno]].val);
 355   EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi)
 356     if (bitmap_bit_p (&result_pseudo_vals_bitmap, lra_reg_info[regno].val))
 357       {
 358         lra_set_regno_unique_value (regno);
 359         if (lra_dump_file != NULL)
 360           fprintf (lra_dump_file,
 361                    "     Make unique value for inheritance r%d\n", regno);
 362       }
 363   bitmap_clear (&result_pseudo_vals_bitmap);
 364   bitmap_clear (&used_pseudos_bitmap);
 365   bitmap_clear (&involved_insns_bitmap);
 366   bitmap_clear (&coalesced_pseudos_bitmap);
 367   if (lra_dump_file != NULL && coalesced_moves != 0)
 368     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
 369   free (sorted_moves);
 370   free (next_coalesced_pseudo);
 371   free (first_coalesced_pseudo);
 372   timevar_pop (TV_LRA_COALESCE);
 373   return coalesced_moves != 0;
 374 }