|
111
|
1 /* Coalesce spilled pseudos.
|
|
131
|
2 Copyright (C) 2010-2018 Free Software Foundation, Inc.
|
|
111
|
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 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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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 }
|
