1/* Coalesce spilled pseudos.
2   Copyright (C) 2010-2020 Free Software Foundation, Inc.
3   Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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.  */
64static int *first_coalesced_pseudo, *next_coalesced_pseudo;
65
66/* The function is used to sort moves according to their execution
67   frequencies.	 */
68static int
69move_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.  */
86static 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.  */
91static void
92merge_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.  */
122static bool
123substitute (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
167static bool
168substitute_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.  */
175int lra_coalesce_iter;
176
177/* Return true if the move involving REGNO1 and REGNO2 is a potential
178   memory-memory move.	*/
179static bool
180mem_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.  */
186static bitmap_head used_pseudos_bitmap;
187
188/* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
189   bitmap).  */
190static void
191update_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.  */
208static bool
209coalescable_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.  */
221bool
222lra_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, &reg_obstack);
265  bitmap_initialize (&involved_insns_bitmap, &reg_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, &reg_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