Daily bump.
[official-gcc.git] / gcc / lra-coalesce.c
blob045691d5257bd55222687e9c6233c039bc8a8a32
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 "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"
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. */
95 static int *first_coalesced_pseudo, *next_coalesced_pseudo;
97 /* The function is used to sort moves according to their execution
98 frequencies. */
99 static int
100 move_freq_compare_func (const void *v1p, const void *v2p)
102 rtx_insn *mv1 = *(rtx_insn * const *) v1p;
103 rtx_insn *mv2 = *(rtx_insn * const *) v2p;
104 int pri1, pri2;
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;
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);
116 /* Pseudos which go away after coalescing. */
117 static bitmap_head coalesced_pseudos_bitmap;
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. */
122 static void
123 merge_pseudos (int regno1, int regno2)
125 int regno, first, first2, last, next;
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])
133 first_coalesced_pseudo[regno] = first;
134 bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
135 if (regno == regno2)
136 break;
137 last = regno;
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;
151 /* Change pseudos in *LOC on their coalescing group
152 representatives. */
153 static bool
154 substitute (rtx *loc)
156 int i, regno;
157 const char *fmt;
158 enum rtx_code code;
159 bool res;
161 if (*loc == NULL_RTX)
162 return false;
163 code = GET_CODE (*loc);
164 if (code == REG)
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;
174 res = false;
175 fmt = GET_RTX_FORMAT (code);
176 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
178 if (fmt[i] == 'e')
180 if (substitute (&XEXP (*loc, i)))
181 res = true;
183 else if (fmt[i] == 'E')
185 int j;
187 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
188 if (substitute (&XVECEXP (*loc, i, j)))
189 res = true;
192 return res;
195 /* Specialize "substitute" for use on an insn. This can't change
196 the insn ptr, just the contents of the insn. */
198 static bool
199 substitute_within_insn (rtx_insn *insn)
201 rtx loc = insn;
202 return substitute (&loc);
205 /* The current iteration (1, 2, ...) of the coalescing pass. */
206 int lra_coalesce_iter;
208 /* Return true if the move involving REGNO1 and REGNO2 is a potential
209 memory-memory move. */
210 static bool
211 mem_move_p (int regno1, int regno2)
213 return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
216 /* Pseudos used instead of the coalesced pseudos. */
217 static bitmap_head used_pseudos_bitmap;
219 /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
220 bitmap). */
221 static void
222 update_live_info (bitmap lr_bitmap)
224 unsigned int j;
225 bitmap_iterator bi;
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))
233 bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
234 bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
238 /* Return true if pseudo REGNO can be potentially coalesced. */
239 static bool
240 coalescable_pseudo_p (int regno)
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);
250 /* The major function for aggressive pseudo coalescing of moves only
251 if the both pseudos were spilled and not special reload pseudos. */
252 bool
253 lra_coalesce (void)
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;
266 timevar_push (TV_LRA_COALESCE);
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)
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;
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, &reg_obstack);
299 bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
300 for (i = 0; i < mv_num; i++)
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])
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. */
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)))
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);
337 bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
338 FOR_EACH_BB_FN (bb, cfun)
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)))
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))
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);
360 /* If we have situation after inheritance pass:
362 r1 <- ... insn originally setting p1
363 i1 <- r1 setting inheritance i1 from reload r1
365 ... <- ... p2 ... dead p2
367 p1 <- i1
368 r2 <- i1
369 ...<- ... r2 ...
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, &reg_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))
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);
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;