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