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