1 /* Coalesce spilled pseudos.
2 Copyright (C) 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
23 /* This file contains a pass making some simple RTL code
24 transformations by coalescing pseudos to remove some move insns.
26 Spilling pseudos in LRA can create memory-memory moves. We should
27 remove potential memory-memory moves before the next constraint
28 pass because the constraint pass will generate additional insns for
29 such moves and all these insns will be hard to remove afterwards.
31 Here we coalesce only spilled pseudos. Coalescing non-spilled
32 pseudos (with different hard regs) might result in spilling
33 additional pseudos because of possible conflicts with other
34 non-spilled pseudos and, as a consequence, in more constraint
35 passes and even LRA infinite cycling. Trivial the same hard
36 register moves will be removed by subsequent compiler passes.
38 We don't coalesce special reload pseudos. It complicates LRA code
39 a lot without visible generated code improvement.
41 The pseudo live-ranges are used to find conflicting pseudos during
44 Most frequently executed moves is tried to be coalesced first. */
48 #include "coretypes.h"
52 #include "insn-config.h"
56 #include "hard-reg-set.h"
60 #include "basic-block.h"
67 /* Arrays whose elements represent the first and the next pseudo
68 (regno) in the coalesced pseudos group to which given pseudo (its
69 regno is the index) belongs. The next of the last pseudo in the
70 group refers to the first pseudo in the group, in other words the
71 group is represented by a cyclic list. */
72 static int *first_coalesced_pseudo
, *next_coalesced_pseudo
;
74 /* The function is used to sort moves according to their execution
77 move_freq_compare_func (const void *v1p
, const void *v2p
)
79 rtx mv1
= *(const rtx
*) v1p
;
80 rtx mv2
= *(const rtx
*) v2p
;
83 pri1
= BLOCK_FOR_INSN (mv1
)->frequency
;
84 pri2
= BLOCK_FOR_INSN (mv2
)->frequency
;
88 /* If frequencies are equal, sort by moves, so that the results of
89 qsort leave nothing to chance. */
90 return (int) INSN_UID (mv1
) - (int) INSN_UID (mv2
);
93 /* Pseudos which go away after coalescing. */
94 static bitmap_head coalesced_pseudos_bitmap
;
96 /* Merge two sets of coalesced pseudos given correspondingly by
97 pseudos REGNO1 and REGNO2 (more accurately merging REGNO2 group
98 into REGNO1 group). Set up COALESCED_PSEUDOS_BITMAP. */
100 merge_pseudos (int regno1
, int regno2
)
102 int regno
, first
, first2
, last
, next
;
104 first
= first_coalesced_pseudo
[regno1
];
105 if ((first2
= first_coalesced_pseudo
[regno2
]) == first
)
107 for (last
= regno2
, regno
= next_coalesced_pseudo
[regno2
];;
108 regno
= next_coalesced_pseudo
[regno
])
110 first_coalesced_pseudo
[regno
] = first
;
111 bitmap_set_bit (&coalesced_pseudos_bitmap
, regno
);
116 next
= next_coalesced_pseudo
[first
];
117 next_coalesced_pseudo
[first
] = regno2
;
118 next_coalesced_pseudo
[last
] = next
;
119 lra_reg_info
[first
].live_ranges
120 = (lra_merge_live_ranges
121 (lra_reg_info
[first
].live_ranges
,
122 lra_copy_live_range_list (lra_reg_info
[first2
].live_ranges
)));
123 if (GET_MODE_SIZE (lra_reg_info
[first
].biggest_mode
)
124 < GET_MODE_SIZE (lra_reg_info
[first2
].biggest_mode
))
125 lra_reg_info
[first
].biggest_mode
= lra_reg_info
[first2
].biggest_mode
;
128 /* Change pseudos in *LOC on their coalescing group
131 substitute (rtx
*loc
)
138 if (*loc
== NULL_RTX
)
140 code
= GET_CODE (*loc
);
143 regno
= REGNO (*loc
);
144 if (regno
< FIRST_PSEUDO_REGISTER
145 || first_coalesced_pseudo
[regno
] == regno
)
147 *loc
= regno_reg_rtx
[first_coalesced_pseudo
[regno
]];
152 fmt
= GET_RTX_FORMAT (code
);
153 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
157 if (substitute (&XEXP (*loc
, i
)))
160 else if (fmt
[i
] == 'E')
164 for (j
= XVECLEN (*loc
, i
) - 1; j
>= 0; j
--)
165 if (substitute (&XVECEXP (*loc
, i
, j
)))
172 /* The current iteration (1, 2, ...) of the coalescing pass. */
173 int lra_coalesce_iter
;
175 /* Return true if the move involving REGNO1 and REGNO2 is a potential
176 memory-memory move. */
178 mem_move_p (int regno1
, int regno2
)
180 return reg_renumber
[regno1
] < 0 && reg_renumber
[regno2
] < 0;
183 /* Pseudos used instead of the coalesced pseudos. */
184 static bitmap_head used_pseudos_bitmap
;
186 /* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
189 update_live_info (bitmap lr_bitmap
)
194 bitmap_clear (&used_pseudos_bitmap
);
195 EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap
, lr_bitmap
,
196 FIRST_PSEUDO_REGISTER
, j
, bi
)
197 bitmap_set_bit (&used_pseudos_bitmap
, first_coalesced_pseudo
[j
]);
198 if (! bitmap_empty_p (&used_pseudos_bitmap
))
200 bitmap_and_compl_into (lr_bitmap
, &coalesced_pseudos_bitmap
);
201 bitmap_ior_into (lr_bitmap
, &used_pseudos_bitmap
);
205 /* Return true if pseudo REGNO can be potentially coalesced. Use
206 SPLIT_PSEUDO_BITMAP to find pseudos whose live ranges were
209 coalescable_pseudo_p (int regno
, bitmap split_origin_bitmap
)
211 lra_assert (regno
>= FIRST_PSEUDO_REGISTER
);
212 /* Don't coalesce inheritance pseudos because spilled inheritance
213 pseudos will be removed in subsequent 'undo inheritance'
215 return (lra_reg_info
[regno
].restore_regno
< 0
216 /* We undo splits for spilled pseudos whose live ranges were
217 split. So don't coalesce them, it is not necessary and
218 the undo transformations would be wrong. */
219 && ! bitmap_bit_p (split_origin_bitmap
, regno
)
220 /* We don't want to coalesce regnos with equivalences, at
221 least without updating this info. */
222 && ira_reg_equiv
[regno
].constant
== NULL_RTX
223 && ira_reg_equiv
[regno
].memory
== NULL_RTX
224 && ira_reg_equiv
[regno
].invariant
== NULL_RTX
);
227 /* The major function for aggressive pseudo coalescing of moves only
228 if the both pseudos were spilled and not special reload pseudos. */
233 rtx mv
, set
, insn
, next
, *sorted_moves
;
234 int i
, mv_num
, sregno
, dregno
, restore_regno
;
237 int max_regno
= max_reg_num ();
238 bitmap_head involved_insns_bitmap
, split_origin_bitmap
;
241 timevar_push (TV_LRA_COALESCE
);
243 if (lra_dump_file
!= NULL
)
244 fprintf (lra_dump_file
,
245 "\n********** Pseudos coalescing #%d: **********\n\n",
246 ++lra_coalesce_iter
);
247 first_coalesced_pseudo
= XNEWVEC (int, max_regno
);
248 next_coalesced_pseudo
= XNEWVEC (int, max_regno
);
249 for (i
= 0; i
< max_regno
; i
++)
250 first_coalesced_pseudo
[i
] = next_coalesced_pseudo
[i
] = i
;
251 sorted_moves
= XNEWVEC (rtx
, get_max_uid ());
253 /* Collect pseudos whose live ranges were split. */
254 bitmap_initialize (&split_origin_bitmap
, ®_obstack
);
255 EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs
, 0, regno
, bi
)
256 if ((restore_regno
= lra_reg_info
[regno
].restore_regno
) >= 0)
257 bitmap_set_bit (&split_origin_bitmap
, restore_regno
);
262 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
264 && (set
= single_set (insn
)) != NULL_RTX
265 && REG_P (SET_DEST (set
)) && REG_P (SET_SRC (set
))
266 && (sregno
= REGNO (SET_SRC (set
))) >= FIRST_PSEUDO_REGISTER
267 && (dregno
= REGNO (SET_DEST (set
))) >= FIRST_PSEUDO_REGISTER
268 && mem_move_p (sregno
, dregno
)
269 && coalescable_pseudo_p (sregno
, &split_origin_bitmap
)
270 && coalescable_pseudo_p (dregno
, &split_origin_bitmap
)
271 && ! side_effects_p (set
)
272 && !(lra_intersected_live_ranges_p
273 (lra_reg_info
[sregno
].live_ranges
,
274 lra_reg_info
[dregno
].live_ranges
)))
275 sorted_moves
[mv_num
++] = insn
;
277 bitmap_clear (&split_origin_bitmap
);
278 qsort (sorted_moves
, mv_num
, sizeof (rtx
), move_freq_compare_func
);
279 /* Coalesced copies, most frequently executed first. */
280 bitmap_initialize (&coalesced_pseudos_bitmap
, ®_obstack
);
281 bitmap_initialize (&involved_insns_bitmap
, ®_obstack
);
282 for (i
= 0; i
< mv_num
; i
++)
284 mv
= sorted_moves
[i
];
285 set
= single_set (mv
);
286 lra_assert (set
!= NULL
&& REG_P (SET_SRC (set
))
287 && REG_P (SET_DEST (set
)));
288 sregno
= REGNO (SET_SRC (set
));
289 dregno
= REGNO (SET_DEST (set
));
290 if (first_coalesced_pseudo
[sregno
] == first_coalesced_pseudo
[dregno
])
293 if (lra_dump_file
!= NULL
)
295 (lra_dump_file
, " Coalescing move %i:r%d-r%d (freq=%d)\n",
296 INSN_UID (mv
), sregno
, dregno
,
297 BLOCK_FOR_INSN (mv
)->frequency
);
298 /* We updated involved_insns_bitmap when doing the merge. */
300 else if (!(lra_intersected_live_ranges_p
301 (lra_reg_info
[first_coalesced_pseudo
[sregno
]].live_ranges
,
302 lra_reg_info
[first_coalesced_pseudo
[dregno
]].live_ranges
)))
305 if (lra_dump_file
!= NULL
)
308 " Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
309 INSN_UID (mv
), sregno
, ORIGINAL_REGNO (SET_SRC (set
)),
310 dregno
, ORIGINAL_REGNO (SET_DEST (set
)),
311 BLOCK_FOR_INSN (mv
)->frequency
);
312 bitmap_ior_into (&involved_insns_bitmap
,
313 &lra_reg_info
[sregno
].insn_bitmap
);
314 bitmap_ior_into (&involved_insns_bitmap
,
315 &lra_reg_info
[dregno
].insn_bitmap
);
316 merge_pseudos (sregno
, dregno
);
319 bitmap_initialize (&used_pseudos_bitmap
, ®_obstack
);
322 update_live_info (df_get_live_in (bb
));
323 update_live_info (df_get_live_out (bb
));
324 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
326 && bitmap_bit_p (&involved_insns_bitmap
, INSN_UID (insn
)))
328 if (! substitute (&insn
))
330 lra_update_insn_regno_info (insn
);
331 if ((set
= single_set (insn
)) != NULL_RTX
&& set_noop_p (set
))
333 /* Coalesced move. */
334 if (lra_dump_file
!= NULL
)
335 fprintf (lra_dump_file
, " Removing move %i (freq=%d)\n",
336 INSN_UID (insn
), BLOCK_FOR_INSN (insn
)->frequency
);
337 lra_set_insn_deleted (insn
);
341 bitmap_clear (&used_pseudos_bitmap
);
342 bitmap_clear (&involved_insns_bitmap
);
343 bitmap_clear (&coalesced_pseudos_bitmap
);
344 if (lra_dump_file
!= NULL
&& coalesced_moves
!= 0)
345 fprintf (lra_dump_file
, "Coalesced Moves = %d\n", coalesced_moves
);
347 free (next_coalesced_pseudo
);
348 free (first_coalesced_pseudo
);
349 timevar_pop (TV_LRA_COALESCE
);
350 return coalesced_moves
!= 0;