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 unsigned int regno; 225 int coalesced_moves; 226 int max_regno = max_reg_num (); 227 bitmap_head involved_insns_bitmap; 228 bitmap_head result_pseudo_vals_bitmap; 229 bitmap_iterator bi; 230 231 timevar_push (TV_LRA_COALESCE); 232 233 if (lra_dump_file != NULL) 234 fprintf (lra_dump_file, 235 "\n********** Pseudos coalescing #%d: **********\n\n", 236 ++lra_coalesce_iter); 237 first_coalesced_pseudo = XNEWVEC (int, max_regno); 238 next_coalesced_pseudo = XNEWVEC (int, max_regno); 239 for (i = 0; i < max_regno; i++) 240 first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i; 241 sorted_moves = XNEWVEC (rtx, get_max_uid ()); 242 mv_num = 0; 243 /* Collect moves. */ 244 coalesced_moves = 0; 245 FOR_EACH_BB (bb) 246 { 247 FOR_BB_INSNS_SAFE (bb, insn, next) 248 if (INSN_P (insn) 249 && (set = single_set (insn)) != NULL_RTX 250 && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)) 251 && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER 252 && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER 253 && mem_move_p (sregno, dregno) 254 && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno) 255 && ! side_effects_p (set) 256 && !(lra_intersected_live_ranges_p 257 (lra_reg_info[sregno].live_ranges, 258 lra_reg_info[dregno].live_ranges))) 259 sorted_moves[mv_num++] = insn; 260 } 261 qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func); 262 /* Coalesced copies, most frequently executed first. */ 263 bitmap_initialize (&coalesced_pseudos_bitmap, ®_obstack); 264 bitmap_initialize (&involved_insns_bitmap, ®_obstack); 265 for (i = 0; i < mv_num; i++) 266 { 267 mv = sorted_moves[i]; 268 set = single_set (mv); 269 lra_assert (set != NULL && REG_P (SET_SRC (set)) 270 && REG_P (SET_DEST (set))); 271 sregno = REGNO (SET_SRC (set)); 272 dregno = REGNO (SET_DEST (set)); 273 if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno]) 274 { 275 coalesced_moves++; 276 if (lra_dump_file != NULL) 277 fprintf 278 (lra_dump_file, " Coalescing move %i:r%d-r%d (freq=%d)\n", 279 INSN_UID (mv), sregno, dregno, 280 BLOCK_FOR_INSN (mv)->frequency); 281 /* We updated involved_insns_bitmap when doing the merge. */ 282 } 283 else if (!(lra_intersected_live_ranges_p 284 (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges, 285 lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges))) 286 { 287 coalesced_moves++; 288 if (lra_dump_file != NULL) 289 fprintf 290 (lra_dump_file, 291 " Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n", 292 INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)), 293 dregno, ORIGINAL_REGNO (SET_DEST (set)), 294 BLOCK_FOR_INSN (mv)->frequency); 295 bitmap_ior_into (&involved_insns_bitmap, 296 &lra_reg_info[sregno].insn_bitmap); 297 bitmap_ior_into (&involved_insns_bitmap, 298 &lra_reg_info[dregno].insn_bitmap); 299 merge_pseudos (sregno, dregno); 300 } 301 } 302 bitmap_initialize (&used_pseudos_bitmap, ®_obstack); 303 FOR_EACH_BB (bb) 304 { 305 update_live_info (df_get_live_in (bb)); 306 update_live_info (df_get_live_out (bb)); 307 FOR_BB_INSNS_SAFE (bb, insn, next) 308 if (INSN_P (insn) 309 && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn))) 310 { 311 if (! substitute (&insn)) 312 continue; 313 lra_update_insn_regno_info (insn); 314 if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set)) 315 { 316 /* Coalesced move. */ 317 if (lra_dump_file != NULL) 318 fprintf (lra_dump_file, " Removing move %i (freq=%d)\n", 319 INSN_UID (insn), BLOCK_FOR_INSN (insn)->frequency); 320 lra_set_insn_deleted (insn); 321 } 322 } 323 } 324 /* If we have situation after inheritance pass: 325 326 r1 <- ... insn originally setting p1 327 i1 <- r1 setting inheritance i1 from reload r1 328 ... 329 ... <- ... p2 ... dead p2 330 .. 331 p1 <- i1 332 r2 <- i1 333 ...<- ... r2 ... 334 335 And we are coalescing p1 and p2 using p1. In this case i1 and p1 336 should have different values, otherwise they can get the same 337 hard reg and this is wrong for insn using p2 before coalescing. 338 So invalidate such inheritance pseudo values. */ 339 bitmap_initialize (&result_pseudo_vals_bitmap, ®_obstack); 340 EXECUTE_IF_SET_IN_BITMAP (&coalesced_pseudos_bitmap, 0, regno, bi) 341 bitmap_set_bit (&result_pseudo_vals_bitmap, 342 lra_reg_info[first_coalesced_pseudo[regno]].val); 343 EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, regno, bi) 344 if (bitmap_bit_p (&result_pseudo_vals_bitmap, lra_reg_info[regno].val)) 345 { 346 lra_set_regno_unique_value (regno); 347 if (lra_dump_file != NULL) 348 fprintf (lra_dump_file, 349 " Make unique value for inheritance r%d\n", regno); 350 } 351 bitmap_clear (&result_pseudo_vals_bitmap); 352 bitmap_clear (&used_pseudos_bitmap); 353 bitmap_clear (&involved_insns_bitmap); 354 bitmap_clear (&coalesced_pseudos_bitmap); 355 if (lra_dump_file != NULL && coalesced_moves != 0) 356 fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves); 357 free (sorted_moves); 358 free (next_coalesced_pseudo); 359 free (first_coalesced_pseudo); 360 timevar_pop (TV_LRA_COALESCE); 361 return coalesced_moves != 0; 362 } 363