Line data Source code
1 : /* Coalesce spilled pseudos.
2 : Copyright (C) 2010-2026 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
69 16892 : move_freq_compare_func (const void *v1p, const void *v2p)
70 : {
71 16892 : rtx_insn *mv1 = *(rtx_insn * const *) v1p;
72 16892 : rtx_insn *mv2 = *(rtx_insn * const *) v2p;
73 16892 : int pri1, pri2;
74 :
75 16892 : pri1 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv1));
76 16892 : pri2 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv2));
77 16892 : if (pri2 - pri1)
78 7606 : return pri2 - pri1;
79 :
80 : /* If frequencies are equal, sort by moves, so that the results of
81 : qsort leave nothing to chance. */
82 9286 : 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
92 1255 : merge_pseudos (int regno1, int regno2)
93 : {
94 1255 : int regno, first, first2, last, next;
95 :
96 1255 : first = first_coalesced_pseudo[regno1];
97 1255 : if ((first2 = first_coalesced_pseudo[regno2]) == first)
98 : return;
99 1255 : for (last = regno2, regno = next_coalesced_pseudo[regno2];;
100 53 : regno = next_coalesced_pseudo[regno])
101 : {
102 1308 : first_coalesced_pseudo[regno] = first;
103 1308 : bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
104 1308 : if (regno == regno2)
105 : break;
106 53 : last = regno;
107 : }
108 1255 : next = next_coalesced_pseudo[first];
109 1255 : next_coalesced_pseudo[first] = regno2;
110 1255 : next_coalesced_pseudo[last] = next;
111 1255 : lra_reg_info[first].live_ranges
112 1255 : = (lra_merge_live_ranges
113 1255 : (lra_reg_info[first].live_ranges,
114 1255 : lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
115 1255 : lra_update_biggest_mode (first, lra_reg_info[first2].biggest_mode);
116 : }
117 :
118 : /* Change pseudos in *LOC on their coalescing group
119 : representatives. */
120 : static bool
121 85894 : substitute (rtx *loc)
122 : {
123 85894 : int i, regno;
124 85894 : const char *fmt;
125 85894 : enum rtx_code code;
126 85894 : bool res;
127 :
128 85894 : if (*loc == NULL_RTX)
129 : return false;
130 74931 : code = GET_CODE (*loc);
131 74931 : if (code == REG)
132 : {
133 31955 : regno = REGNO (*loc);
134 31955 : if (regno < FIRST_PSEUDO_REGISTER
135 28678 : || first_coalesced_pseudo[regno] == regno)
136 : return false;
137 7649 : *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
138 7649 : return true;
139 : }
140 :
141 42976 : res = false;
142 42976 : fmt = GET_RTX_FORMAT (code);
143 178637 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
144 : {
145 135661 : if (fmt[i] == 'e')
146 : {
147 72482 : if (substitute (&XEXP (*loc, i)))
148 135661 : res = true;
149 : }
150 63179 : else if (fmt[i] == 'E')
151 : {
152 1187 : int j;
153 :
154 3636 : for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
155 2449 : if (substitute (&XVECEXP (*loc, i, j)))
156 420 : res = true;
157 : }
158 : }
159 : return res;
160 : }
161 :
162 : /* Specialize "substitute" for use on an insn. This can't change
163 : the insn ptr, just the contents of the insn. */
164 :
165 : static bool
166 10963 : substitute_within_insn (rtx_insn *insn)
167 : {
168 10963 : rtx loc = insn;
169 0 : return substitute (&loc);
170 : }
171 :
172 : /* The current iteration (1, 2, ...) of the coalescing pass. */
173 : int lra_coalesce_iter;
174 :
175 : /* Return true if the move involving REGNO1 and REGNO2 is a potential
176 : memory-memory move. */
177 : static bool
178 3753772 : mem_move_p (int regno1, int regno2)
179 : {
180 3753772 : return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
181 : }
182 :
183 : /* Pseudos used instead of the coalesced pseudos. */
184 : static bitmap_head used_pseudos_bitmap;
185 :
186 : /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
187 : bitmap). */
188 : static void
189 3250426 : update_live_info (bitmap lr_bitmap)
190 : {
191 3250426 : unsigned int j;
192 3250426 : bitmap_iterator bi;
193 :
194 3250426 : bitmap_clear (&used_pseudos_bitmap);
195 3298018 : EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
196 : FIRST_PSEUDO_REGISTER, j, bi)
197 47592 : bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
198 3250426 : if (! bitmap_empty_p (&used_pseudos_bitmap))
199 : {
200 38094 : bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
201 38094 : bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
202 : }
203 3250426 : }
204 :
205 : /* Return true if pseudo REGNO can be potentially coalesced. */
206 : static bool
207 6781 : coalescable_pseudo_p (int regno)
208 : {
209 6781 : lra_assert (regno >= FIRST_PSEUDO_REGISTER);
210 6781 : return (/* We don't want to coalesce regnos with equivalences, at
211 : least without updating this info. */
212 6781 : ira_reg_equiv[regno].constant == NULL_RTX
213 6779 : && ira_reg_equiv[regno].memory == NULL_RTX
214 13556 : && ira_reg_equiv[regno].invariant == NULL_RTX);
215 : }
216 :
217 : /* The major function for aggressive pseudo coalescing of moves only
218 : if the both pseudos were spilled and not special reload pseudos. */
219 : bool
220 26711 : lra_coalesce (void)
221 : {
222 26711 : basic_block bb;
223 26711 : rtx_insn *mv, *insn, *next, **sorted_moves;
224 26711 : rtx set;
225 26711 : int i, mv_num, sregno, dregno;
226 26711 : int coalesced_moves;
227 26711 : int max_regno = max_reg_num ();
228 26711 : bitmap_head involved_insns_bitmap;
229 :
230 26711 : timevar_push (TV_LRA_COALESCE);
231 :
232 26711 : if (lra_dump_file != NULL)
233 0 : fprintf (lra_dump_file,
234 : "\n********** Pseudos coalescing #%d: **********\n\n",
235 : ++lra_coalesce_iter);
236 26711 : first_coalesced_pseudo = XNEWVEC (int, max_regno);
237 26711 : next_coalesced_pseudo = XNEWVEC (int, max_regno);
238 13920262 : for (i = 0; i < max_regno; i++)
239 13893551 : first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
240 26711 : sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
241 26711 : mv_num = 0;
242 : /* Collect moves. */
243 26711 : coalesced_moves = 0;
244 1651924 : FOR_EACH_BB_FN (bb, cfun)
245 : {
246 51604254 : FOR_BB_INSNS_SAFE (bb, insn, next)
247 24176914 : if (INSN_P (insn)
248 20438107 : && (set = single_set (insn)) != NULL_RTX
249 13073064 : && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
250 4304195 : && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
251 4107615 : && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
252 3753772 : && mem_move_p (sregno, dregno)
253 3394 : && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
254 3387 : && ! side_effects_p (set)
255 24180301 : && !(lra_intersected_live_ranges_p
256 3387 : (lra_reg_info[sregno].live_ranges,
257 3387 : lra_reg_info[dregno].live_ranges)))
258 2209 : sorted_moves[mv_num++] = insn;
259 : }
260 26711 : qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
261 : /* Coalesced copies, most frequently executed first. */
262 26711 : bitmap_initialize (&coalesced_pseudos_bitmap, ®_obstack);
263 26711 : bitmap_initialize (&involved_insns_bitmap, ®_obstack);
264 28920 : for (i = 0; i < mv_num; i++)
265 : {
266 2209 : mv = sorted_moves[i];
267 2209 : set = single_set (mv);
268 2209 : lra_assert (set != NULL && REG_P (SET_SRC (set))
269 : && REG_P (SET_DEST (set)));
270 2209 : sregno = REGNO (SET_SRC (set));
271 2209 : dregno = REGNO (SET_DEST (set));
272 2209 : if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
273 : {
274 954 : coalesced_moves++;
275 954 : if (lra_dump_file != NULL)
276 0 : fprintf
277 0 : (lra_dump_file, " Coalescing move %i:r%d-r%d (freq=%d)\n",
278 0 : INSN_UID (mv), sregno, dregno,
279 0 : REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
280 : /* We updated involved_insns_bitmap when doing the merge. */
281 : }
282 1255 : else if (!(lra_intersected_live_ranges_p
283 1255 : (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
284 1255 : lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
285 : {
286 1255 : coalesced_moves++;
287 1255 : if (lra_dump_file != NULL)
288 0 : fprintf
289 0 : (lra_dump_file,
290 : " Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
291 0 : INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
292 0 : dregno, ORIGINAL_REGNO (SET_DEST (set)),
293 0 : REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
294 1255 : bitmap_ior_into (&involved_insns_bitmap,
295 1255 : &lra_reg_info[sregno].insn_bitmap);
296 1255 : bitmap_ior_into (&involved_insns_bitmap,
297 1255 : &lra_reg_info[dregno].insn_bitmap);
298 1255 : merge_pseudos (sregno, dregno);
299 : }
300 : }
301 26711 : bitmap_initialize (&used_pseudos_bitmap, ®_obstack);
302 1651924 : FOR_EACH_BB_FN (bb, cfun)
303 : {
304 1625213 : update_live_info (df_get_live_in (bb));
305 1625213 : update_live_info (df_get_live_out (bb));
306 51604254 : FOR_BB_INSNS_SAFE (bb, insn, next)
307 24176914 : if (INSN_P (insn)
308 24176914 : && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
309 : {
310 10963 : if (! substitute_within_insn (insn))
311 5524 : continue;
312 5439 : lra_update_insn_regno_info (insn);
313 5439 : if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
314 : {
315 : /* Coalesced move. */
316 2209 : if (lra_dump_file != NULL)
317 0 : fprintf (lra_dump_file, " Removing move %i (freq=%d)\n",
318 0 : INSN_UID (insn),
319 0 : REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
320 2209 : lra_set_insn_deleted (insn);
321 : }
322 : }
323 : }
324 : /* If we have situation after inheritance pass:
325 :
326 : r1 <- p1 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 : The situation even can be more complicated when new reload
339 : pseudos occur after the inheriatnce. So invalidate the result
340 : pseudos. */
341 13920262 : for (i = 0; i < max_regno; i++)
342 13893551 : if (first_coalesced_pseudo[i] == i
343 13892296 : && first_coalesced_pseudo[i] != next_coalesced_pseudo[i])
344 : {
345 1065 : lra_set_regno_unique_value (i);
346 1065 : if (lra_dump_file != NULL)
347 0 : fprintf (lra_dump_file,
348 : " Make unique value for coalescing result r%d\n", i);
349 : }
350 26711 : bitmap_clear (&used_pseudos_bitmap);
351 26711 : bitmap_clear (&involved_insns_bitmap);
352 26711 : bitmap_clear (&coalesced_pseudos_bitmap);
353 26711 : if (lra_dump_file != NULL && coalesced_moves != 0)
354 0 : fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
355 26711 : free (sorted_moves);
356 26711 : free (next_coalesced_pseudo);
357 26711 : free (first_coalesced_pseudo);
358 26711 : timevar_pop (TV_LRA_COALESCE);
359 26711 : return coalesced_moves != 0;
360 : }
|
