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