gcc/lra-coalesce.c

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