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