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