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