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