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