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