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