gcc/lra-coalesce.c

   1 /* Coalesce spilled pseudos.
   2    Copyright (C) 2010, 2011, 2012
   3    Free Software Foundation, Inc.
   4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22
  23 /* This file contains a pass making some simple RTL code
  24    transformations by coalescing pseudos to remove some move insns.
  25
  26    Spilling pseudos in LRA can create memory-memory moves.  We should
  27    remove potential memory-memory moves before the next constraint
  28    pass because the constraint pass will generate additional insns for
  29    such moves and all these insns will be hard to remove afterwards.
  30
  31    Here we coalesce only spilled pseudos.  Coalescing non-spilled
  32    pseudos (with different hard regs) might result in spilling
  33    additional pseudos because of possible conflicts with other
  34    non-spilled pseudos and, as a consequence, in more constraint
  35    passes and even LRA infinite cycling.  Trivial the same hard
  36    register moves will be removed by subsequent compiler passes.
  37
  38    We don't coalesce special reload pseudos.  It complicates LRA code
  39    a lot without visible generated code improvement.
  40
  41    The pseudo live-ranges are used to find conflicting pseudos during
  42    coalescing.
  43
  44    Most frequently executed moves is tried to be coalesced first.  */
  45
  46 #include "config.h"
  47 #include "system.h"
  48 #include "coretypes.h"
  49 #include "tm.h"
  50 #include "rtl.h"
  51 #include "tm_p.h"
  52 #include "insn-config.h"
  53 #include "recog.h"
  54 #include "output.h"
  55 #include "regs.h"
  56 #include "hard-reg-set.h"
  57 #include "flags.h"
  58 #include "function.h"
  59 #include "expr.h"
  60 #include "basic-block.h"
  61 #include "except.h"
  62 #include "timevar.h"
  63 #include "ira.h"
  64 #include "lra-int.h"
  65 #include "df.h"
  66
  67 /* Arrays whose elements represent the first and the next pseudo
  68    (regno) in the coalesced pseudos group to which given pseudo (its
  69    regno is the index) belongs.  The next of the last pseudo in the
  70    group refers to the first pseudo in the group, in other words the
  71    group is represented by a cyclic list.  */
  72 static int *first_coalesced_pseudo, *next_coalesced_pseudo;
  73
  74 /* The function is used to sort moves according to their execution
  75    frequencies.  */
  76 static int
  77 move_freq_compare_func (const void *v1p, const void *v2p)
  78 {
  79   rtx mv1 = *(const rtx *) v1p;
  80   rtx mv2 = *(const rtx *) v2p;
  81   int pri1, pri2;
  82
  83   pri1 = BLOCK_FOR_INSN (mv1)->frequency;
  84   pri2 = BLOCK_FOR_INSN (mv2)->frequency;
  85   if (pri2 - pri1)
  86     return pri2 - pri1;
  87
  88   /* If frequencies are equal, sort by moves, so that the results of
  89      qsort leave nothing to chance.  */
  90   return (int) INSN_UID (mv1) - (int) INSN_UID (mv2);
  91 }
  92
  93 /* Pseudos which go away after coalescing.  */
  94 static bitmap_head coalesced_pseudos_bitmap;
  95
  96 /* Merge two sets of coalesced pseudos given correspondingly by
  97    pseudos REGNO1 and REGNO2 (more accurately merging REGNO2 group
  98    into REGNO1 group).  Set up COALESCED_PSEUDOS_BITMAP.  */
  99 static void
 100 merge_pseudos (int regno1, int regno2)
 101 {
 102   int regno, first, first2, last, next;
 103
 104   first = first_coalesced_pseudo[regno1];
 105   if ((first2 = first_coalesced_pseudo[regno2]) == first)
 106     return;
 107   for (last = regno2, regno = next_coalesced_pseudo[regno2];;
 108        regno = next_coalesced_pseudo[regno])
 109     {
 110       first_coalesced_pseudo[regno] = first;
 111       bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
 112       if (regno == regno2)
 113         break;
 114       last = regno;
 115     }
 116   next = next_coalesced_pseudo[first];
 117   next_coalesced_pseudo[first] = regno2;
 118   next_coalesced_pseudo[last] = next;
 119   lra_reg_info[first].live_ranges
 120     = (lra_merge_live_ranges
 121        (lra_reg_info[first].live_ranges,
 122         lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
 123   if (GET_MODE_SIZE (lra_reg_info[first].biggest_mode)
 124       < GET_MODE_SIZE (lra_reg_info[first2].biggest_mode))
 125     lra_reg_info[first].biggest_mode = lra_reg_info[first2].biggest_mode;
 126 }
 127
 128 /* Change pseudos in *LOC on their coalescing group
 129    representatives.  */
 130 static bool
 131 substitute (rtx *loc)
 132 {
 133   int i, regno;
 134   const char *fmt;
 135   enum rtx_code code;
 136   bool res;
 137
 138   if (*loc == NULL_RTX)
 139     return false;
 140   code = GET_CODE (*loc);
 141   if (code == REG)
 142     {
 143       regno = REGNO (*loc);
 144       if (regno < FIRST_PSEUDO_REGISTER
 145           || first_coalesced_pseudo[regno] == regno)
 146         return false;
 147       *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
 148       return true;
 149     }
 150
 151   res = false;
 152   fmt = GET_RTX_FORMAT (code);
 153   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 154     {
 155       if (fmt[i] == 'e')
 156         {
 157           if (substitute (&XEXP (*loc, i)))
 158             res = true;
 159         }
 160       else if (fmt[i] == 'E')
 161         {
 162           int j;
 163
 164           for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
 165             if (substitute (&XVECEXP (*loc, i, j)))
 166               res = true;
 167         }
 168     }
 169   return res;
 170 }
 171
 172 /* The current iteration (1, 2, ...) of the coalescing pass.  */
 173 int lra_coalesce_iter;
 174
 175 /* Return true if the move involving REGNO1 and REGNO2 is a potential
 176    memory-memory move.  */
 177 static bool
 178 mem_move_p (int regno1, int regno2)
 179 {
 180   return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
 181 }
 182
 183 /* Pseudos used instead of the coalesced pseudos.  */
 184 static bitmap_head used_pseudos_bitmap;
 185
 186 /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
 187    bitmap).  */
 188 static void
 189 update_live_info (bitmap lr_bitmap)
 190 {
 191   unsigned int j;
 192   bitmap_iterator bi;
 193
 194   bitmap_clear (&used_pseudos_bitmap);
 195   EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
 196                             FIRST_PSEUDO_REGISTER, j, bi)
 197     bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
 198   if (! bitmap_empty_p (&used_pseudos_bitmap))
 199     {
 200       bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
 201       bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
 202     }
 203 }
 204
 205 /* Return true if pseudo REGNO can be potentially coalesced.  Use
 206    SPLIT_PSEUDO_BITMAP to find pseudos whose live ranges were
 207    split.  */
 208 static bool
 209 coalescable_pseudo_p (int regno, bitmap split_origin_bitmap)
 210 {
 211   lra_assert (regno >= FIRST_PSEUDO_REGISTER);
 212   /* Don't coalesce inheritance pseudos because spilled inheritance
 213      pseudos will be removed in subsequent 'undo inheritance'
 214      pass.  */
 215   return (lra_reg_info[regno].restore_regno < 0
 216           /* We undo splits for spilled pseudos whose live ranges were
 217              split.  So don't coalesce them, it is not necessary and
 218              the undo transformations would be wrong.  */
 219           && ! bitmap_bit_p (split_origin_bitmap, regno)
 220           /* We don't want to coalesce regnos with equivalences, at
 221              least without updating this info.  */
 222           && ira_reg_equiv[regno].constant == NULL_RTX
 223           && ira_reg_equiv[regno].memory == NULL_RTX
 224           && ira_reg_equiv[regno].invariant == NULL_RTX);
 225 }
 226
 227 /* The major function for aggressive pseudo coalescing of moves only
 228    if the both pseudos were spilled and not special reload pseudos.  */
 229 bool
 230 lra_coalesce (void)
 231 {
 232   basic_block bb;
 233   rtx mv, set, insn, next, *sorted_moves;
 234   int i, mv_num, sregno, dregno, restore_regno;
 235   unsigned int regno;
 236   int coalesced_moves;
 237   int max_regno = max_reg_num ();
 238   bitmap_head involved_insns_bitmap, split_origin_bitmap;
 239   bitmap_iterator bi;
 240
 241   timevar_push (TV_LRA_COALESCE);
 242
 243   if (lra_dump_file != NULL)
 244     fprintf (lra_dump_file,
 245              "\n********** Pseudos coalescing #%d: **********\n\n",
 246              ++lra_coalesce_iter);
 247   first_coalesced_pseudo = XNEWVEC (int, max_regno);
 248   next_coalesced_pseudo = XNEWVEC (int, max_regno);
 249   for (i = 0; i < max_regno; i++)
 250     first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
 251   sorted_moves = XNEWVEC (rtx, get_max_uid ());
 252   mv_num = 0;
 253   /* Collect pseudos whose live ranges were split.  */
 254   bitmap_initialize (&split_origin_bitmap, &reg_obstack);
 255   EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, regno, bi)
 256     if ((restore_regno = lra_reg_info[regno].restore_regno) >= 0)
 257       bitmap_set_bit (&split_origin_bitmap, restore_regno);
 258   /* Collect moves.  */
 259   coalesced_moves = 0;
 260   FOR_EACH_BB (bb)
 261     {
 262       FOR_BB_INSNS_SAFE (bb, insn, next)
 263         if (INSN_P (insn)
 264             && (set = single_set (insn)) != NULL_RTX
 265             && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
 266             && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
 267             && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
 268             && mem_move_p (sregno, dregno)
 269             && coalescable_pseudo_p (sregno, &split_origin_bitmap)
 270             && coalescable_pseudo_p (dregno, &split_origin_bitmap)
 271             && ! side_effects_p (set)
 272             && !(lra_intersected_live_ranges_p
 273                  (lra_reg_info[sregno].live_ranges,
 274                   lra_reg_info[dregno].live_ranges)))
 275           sorted_moves[mv_num++] = insn;
 276     }
 277   bitmap_clear (&split_origin_bitmap);
 278   qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
 279   /* Coalesced copies, most frequently executed first.  */
 280   bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
 281   bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
 282   for (i = 0; i < mv_num; i++)
 283     {
 284       mv = sorted_moves[i];
 285       set = single_set (mv);
 286       lra_assert (set != NULL && REG_P (SET_SRC (set))
 287                   && REG_P (SET_DEST (set)));
 288       sregno = REGNO (SET_SRC (set));
 289       dregno = REGNO (SET_DEST (set));
 290       if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
 291         {
 292           coalesced_moves++;
 293           if (lra_dump_file != NULL)
 294             fprintf
 295               (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
 296                INSN_UID (mv), sregno, dregno,
 297                BLOCK_FOR_INSN (mv)->frequency);
 298           /* We updated involved_insns_bitmap when doing the merge.  */
 299         }
 300       else if (!(lra_intersected_live_ranges_p
 301                  (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
 302                   lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
 303         {
 304           coalesced_moves++;
 305           if (lra_dump_file != NULL)
 306             fprintf
 307               (lra_dump_file,
 308                "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
 309                INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
 310                dregno, ORIGINAL_REGNO (SET_DEST (set)),
 311                BLOCK_FOR_INSN (mv)->frequency);
 312           bitmap_ior_into (&involved_insns_bitmap,
 313                            &lra_reg_info[sregno].insn_bitmap);
 314           bitmap_ior_into (&involved_insns_bitmap,
 315                            &lra_reg_info[dregno].insn_bitmap);
 316           merge_pseudos (sregno, dregno);
 317         }
 318     }
 319   bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
 320   FOR_EACH_BB (bb)
 321     {
 322       update_live_info (df_get_live_in (bb));
 323       update_live_info (df_get_live_out (bb));
 324       FOR_BB_INSNS_SAFE (bb, insn, next)
 325         if (INSN_P (insn)
 326             && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
 327           {
 328             if (! substitute (&insn))
 329               continue;
 330             lra_update_insn_regno_info (insn);
 331             if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
 332               {
 333                 /* Coalesced move.  */
 334                 if (lra_dump_file != NULL)
 335                   fprintf (lra_dump_file, "      Removing move %i (freq=%d)\n",
 336                          INSN_UID (insn), BLOCK_FOR_INSN (insn)->frequency);
 337                 lra_set_insn_deleted (insn);
 338               }
 339           }
 340     }
 341   bitmap_clear (&used_pseudos_bitmap);
 342   bitmap_clear (&involved_insns_bitmap);
 343   bitmap_clear (&coalesced_pseudos_bitmap);
 344   if (lra_dump_file != NULL && coalesced_moves != 0)
 345     fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
 346   free (sorted_moves);
 347   free (next_coalesced_pseudo);
 348   free (first_coalesced_pseudo);
 349   timevar_pop (TV_LRA_COALESCE);
 350   return coalesced_moves != 0;
 351 }