gcc/lra-coalesce.c

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