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