[thirdparty/gcc.git] / gcc / lra-coalesce.c

/* Coalesce spilled pseudos.
   Copyright (C) 2010-2015 Free Software Foundation, Inc.
   Contributed by Vladimir Makarov <vmakarov@redhat.com>.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.	If not see
<http://www.gnu.org/licenses/>.	 */


/* This file contains a pass making some simple RTL code
   transformations by coalescing pseudos to remove some move insns.

   Spilling pseudos in LRA can create memory-memory moves.  We should
   remove potential memory-memory moves before the next constraint
   pass because the constraint pass will generate additional insns for
   such moves and all these insns will be hard to remove afterwards.

   Here we coalesce only spilled pseudos.  Coalescing non-spilled
   pseudos (with different hard regs) might result in spilling
   additional pseudos because of possible conflicts with other
   non-spilled pseudos and, as a consequence, in more constraint
   passes and even LRA infinite cycling.  Trivial the same hard
   register moves will be removed by subsequent compiler passes.

   We don't coalesce special reload pseudos.  It complicates LRA code
   a lot without visible generated code improvement.

   The pseudo live-ranges are used to find conflicting pseudos during
   coalescing.

   Most frequently executed moves is tried to be coalesced first.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "rtl.h"
#include "df.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "output.h"
#include "regs.h"
#include "flags.h"
#include "alias.h"
#include "expmed.h"
#include "dojump.h"
#include "explow.h"
#include "calls.h"
#include "emit-rtl.h"
#include "varasm.h"
#include "stmt.h"
#include "expr.h"
#include "except.h"
#include "timevar.h"
#include "ira.h"
#include "alloc-pool.h"
#include "lra.h"
#include "insn-attr.h"
#include "insn-codes.h"
#include "lra-int.h"

/* Arrays whose elements represent the first and the next pseudo
   (regno) in the coalesced pseudos group to which given pseudo (its
   regno is the index) belongs.	 The next of the last pseudo in the
   group refers to the first pseudo in the group, in other words the
   group is represented by a cyclic list.  */
static int *first_coalesced_pseudo, *next_coalesced_pseudo;

/* The function is used to sort moves according to their execution
   frequencies.	 */
static int
move_freq_compare_func (const void *v1p, const void *v2p)
{
  rtx_insn *mv1 = *(rtx_insn * const *) v1p;
  rtx_insn *mv2 = *(rtx_insn * const *) v2p;
  int pri1, pri2;

  pri1 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv1));
  pri2 = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv2));
  if (pri2 - pri1)
    return pri2 - pri1;

  /* If frequencies are equal, sort by moves, so that the results of
     qsort leave nothing to chance.  */
  return (int) INSN_UID (mv1) - (int) INSN_UID (mv2);
}

/* Pseudos which go away after coalescing.  */
static bitmap_head coalesced_pseudos_bitmap;

/* Merge two sets of coalesced pseudos given correspondingly by
   pseudos REGNO1 and REGNO2 (more accurately merging REGNO2 group
   into REGNO1 group).	Set up COALESCED_PSEUDOS_BITMAP.  */
static void
merge_pseudos (int regno1, int regno2)
{
  int regno, first, first2, last, next;

  first = first_coalesced_pseudo[regno1];
  if ((first2 = first_coalesced_pseudo[regno2]) == first)
    return;
  for (last = regno2, regno = next_coalesced_pseudo[regno2];;
       regno = next_coalesced_pseudo[regno])
    {
      first_coalesced_pseudo[regno] = first;
      bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
      if (regno == regno2)
	break;
      last = regno;
    }
  next = next_coalesced_pseudo[first];
  next_coalesced_pseudo[first] = regno2;
  next_coalesced_pseudo[last] = next;
  lra_reg_info[first].live_ranges
    = (lra_merge_live_ranges
       (lra_reg_info[first].live_ranges,
	lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
  if (GET_MODE_SIZE (lra_reg_info[first].biggest_mode)
      < GET_MODE_SIZE (lra_reg_info[first2].biggest_mode))
    lra_reg_info[first].biggest_mode = lra_reg_info[first2].biggest_mode;
}

/* Change pseudos in *LOC on their coalescing group
   representatives.  */
static bool
substitute (rtx *loc)
{
  int i, regno;
  const char *fmt;
  enum rtx_code code;
  bool res;

  if (*loc == NULL_RTX)
    return false;
  code = GET_CODE (*loc);
  if (code == REG)
    {
      regno = REGNO (*loc);
      if (regno < FIRST_PSEUDO_REGISTER
	  || first_coalesced_pseudo[regno] == regno)
	return false;
      *loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
      return true;
    }

  res = false;
  fmt = GET_RTX_FORMAT (code);
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    {
      if (fmt[i] == 'e')
	{
	  if (substitute (&XEXP (*loc, i)))
	    res = true;
	}
      else if (fmt[i] == 'E')
	{
	  int j;

	  for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
	    if (substitute (&XVECEXP (*loc, i, j)))
	      res = true;
	}
    }
  return res;
}

/* Specialize "substitute" for use on an insn.  This can't change
   the insn ptr, just the contents of the insn.  */

static bool
substitute_within_insn (rtx_insn *insn)
{
  rtx loc = insn;
  return substitute (&loc);
}

/* The current iteration (1, 2, ...) of the coalescing pass.  */
int lra_coalesce_iter;

/* Return true if the move involving REGNO1 and REGNO2 is a potential
   memory-memory move.	*/
static bool
mem_move_p (int regno1, int regno2)
{
  return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
}

/* Pseudos used instead of the coalesced pseudos.  */
static bitmap_head used_pseudos_bitmap;

/* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
   bitmap).  */
static void
update_live_info (bitmap lr_bitmap)
{
  unsigned int j;
  bitmap_iterator bi;

  bitmap_clear (&used_pseudos_bitmap);
  EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
			    FIRST_PSEUDO_REGISTER, j, bi)
    bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
  if (! bitmap_empty_p (&used_pseudos_bitmap))
    {
      bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
      bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
    }
}

/* Return true if pseudo REGNO can be potentially coalesced.  */
static bool
coalescable_pseudo_p (int regno)
{
  lra_assert (regno >= FIRST_PSEUDO_REGISTER);
  return (/* We don't want to coalesce regnos with equivalences, at
	     least without updating this info.  */
	  ira_reg_equiv[regno].constant == NULL_RTX
	  && ira_reg_equiv[regno].memory == NULL_RTX
	  && ira_reg_equiv[regno].invariant == NULL_RTX);
}

/* The major function for aggressive pseudo coalescing of moves only
   if the both pseudos were spilled and not special reload pseudos.  */
bool
lra_coalesce (void)
{
  basic_block bb;
  rtx_insn *mv, *insn, *next, **sorted_moves;
  rtx set;
  int i, mv_num, sregno, dregno;
  unsigned int regno;
  int coalesced_moves;
  int max_regno = max_reg_num ();
  bitmap_head involved_insns_bitmap;
  bitmap_head result_pseudo_vals_bitmap;
  bitmap_iterator bi;

  timevar_push (TV_LRA_COALESCE);

  if (lra_dump_file != NULL)
    fprintf (lra_dump_file,
	     "\n********** Pseudos coalescing #%d: **********\n\n",
	     ++lra_coalesce_iter);
  first_coalesced_pseudo = XNEWVEC (int, max_regno);
  next_coalesced_pseudo = XNEWVEC (int, max_regno);
  for (i = 0; i < max_regno; i++)
    first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
  sorted_moves = XNEWVEC (rtx_insn *, get_max_uid ());
  mv_num = 0;
  /* Collect moves.  */
  coalesced_moves = 0;
  FOR_EACH_BB_FN (bb, cfun)
    {
      FOR_BB_INSNS_SAFE (bb, insn, next)
	if (INSN_P (insn)
	    && (set = single_set (insn)) != NULL_RTX
	    && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
	    && (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
	    && (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
	    && mem_move_p (sregno, dregno)
	    && coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
	    && ! side_effects_p (set)
	    && !(lra_intersected_live_ranges_p
		 (lra_reg_info[sregno].live_ranges,
		  lra_reg_info[dregno].live_ranges)))
	  sorted_moves[mv_num++] = insn;
    }
  qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
  /* Coalesced copies, most frequently executed first.	*/
  bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
  bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
  for (i = 0; i < mv_num; i++)
    {
      mv = sorted_moves[i];
      set = single_set (mv);
      lra_assert (set != NULL && REG_P (SET_SRC (set))
		  && REG_P (SET_DEST (set)));
      sregno = REGNO (SET_SRC (set));
      dregno = REGNO (SET_DEST (set));
      if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
	{
	  coalesced_moves++;
	  if (lra_dump_file != NULL)
	    fprintf
	      (lra_dump_file, "      Coalescing move %i:r%d-r%d (freq=%d)\n",
	       INSN_UID (mv), sregno, dregno,
	       REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
	  /* We updated involved_insns_bitmap when doing the merge.  */
	}
      else if (!(lra_intersected_live_ranges_p
		 (lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
		  lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
	{
	  coalesced_moves++;
	  if (lra_dump_file != NULL)
	    fprintf
	      (lra_dump_file,
	       "  Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
	       INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
	       dregno, ORIGINAL_REGNO (SET_DEST (set)),
	       REG_FREQ_FROM_BB (BLOCK_FOR_INSN (mv)));
	  bitmap_ior_into (&involved_insns_bitmap,
			   &lra_reg_info[sregno].insn_bitmap);
	  bitmap_ior_into (&involved_insns_bitmap,
			   &lra_reg_info[dregno].insn_bitmap);
	  merge_pseudos (sregno, dregno);
	}
    }
  bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
  FOR_EACH_BB_FN (bb, cfun)
    {
      update_live_info (df_get_live_in (bb));
      update_live_info (df_get_live_out (bb));
      FOR_BB_INSNS_SAFE (bb, insn, next)
	if (INSN_P (insn)
	    && bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
	  {
	    if (! substitute_within_insn (insn))
	      continue;
	    lra_update_insn_regno_info (insn);
	    if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
	      {
		/* Coalesced move.  */
		if (lra_dump_file != NULL)
		  fprintf (lra_dump_file, "	 Removing move %i (freq=%d)\n",
			   INSN_UID (insn),
			   REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)));
		lra_set_insn_deleted (insn);
	      }
	  }
    }
  /* If we have situation after inheritance pass:

     r1 <- ...  insn originally setting p1
     i1 <- r1   setting inheritance i1 from reload r1
       ...
     ... <- ... p2 ... dead p2
     ..
     p1 <- i1
     r2 <- i1
     ...<- ... r2 ...

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