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

/* Coalesce spilled pseudos.
   Copyright (C) 2010-2013 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 "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "output.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "function.h"
#include "expr.h"
#include "basic-block.h"
#include "except.h"
#include "timevar.h"
#include "ira.h"
#include "lra-int.h"
#include "df.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 mv1 = *(const rtx *) v1p;
  rtx mv2 = *(const rtx *) v2p;
  int pri1, pri2;

  pri1 = BLOCK_FOR_INSN (mv1)->frequency;
  pri2 = BLOCK_FOR_INSN (mv2)->frequency;
  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;
}

/* 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 mv, set, insn, next, *sorted_moves;
  int i, mv_num, sregno, dregno;
  int coalesced_moves;
  int max_regno = max_reg_num ();
  bitmap_head involved_insns_bitmap;

  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, 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,
	       BLOCK_FOR_INSN (mv)->frequency);
	  /* 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)),
	       BLOCK_FOR_INSN (mv)->frequency);
	  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 (&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), BLOCK_FOR_INSN (insn)->frequency);
		lra_set_insn_deleted (insn);
	      }
	  }
    }
  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
c6a6cdaa	1	/* Coalesce spilled pseudos.
711789cc	2	Copyright (C) 2010-2013 Free Software Foundation, Inc.
c6a6cdaa	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"
	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 "function.h"
	58	#include "expr.h"
	59	#include "basic-block.h"
	60	#include "except.h"
	61	#include "timevar.h"
	62	#include "ira.h"
	63	#include "lra-int.h"
	64	#include "df.h"
	65
	66	/* Arrays whose elements represent the first and the next pseudo
67	(regno) in the coalesced pseudos group to which given pseudo (its
68	regno is the index) belongs. The next of the last pseudo in the
69	group refers to the first pseudo in the group, in other words the
70	group is represented by a cyclic list. */
71	static int first_coalesced_pseudo, next_coalesced_pseudo;
72
73	/* The function is used to sort moves according to their execution
74	frequencies. */
75	static int
76	move_freq_compare_func (const void v1p, const void v2p)
77	{
78	rtx mv1 = (const rtx ) v1p;
79	rtx mv2 = (const rtx ) v2p;
80	int pri1, pri2;
1a8f8886	81
c6a6cdaa	82	pri1 = BLOCK_FOR_INSN (mv1)->frequency;
	83	pri2 = BLOCK_FOR_INSN (mv2)->frequency;
	84	if (pri2 - pri1)
	85	return pri2 - pri1;
	86
	87	/* If frequencies are equal, sort by moves, so that the results of
	88	qsort leave nothing to chance. */
	89	return (int) INSN_UID (mv1) - (int) INSN_UID (mv2);
	90	}
	91
	92	/* Pseudos which go away after coalescing. */
	93	static bitmap_head coalesced_pseudos_bitmap;
	94
	95	/* Merge two sets of coalesced pseudos given correspondingly by
	96	pseudos REGNO1 and REGNO2 (more accurately merging REGNO2 group
	97	into REGNO1 group). Set up COALESCED_PSEUDOS_BITMAP. */
	98	static void
	99	merge_pseudos (int regno1, int regno2)
	100	{
	101	int regno, first, first2, last, next;
	102
	103	first = first_coalesced_pseudo[regno1];
	104	if ((first2 = first_coalesced_pseudo[regno2]) == first)
	105	return;
	106	for (last = regno2, regno = next_coalesced_pseudo[regno2];;
	107	regno = next_coalesced_pseudo[regno])
	108	{
	109	first_coalesced_pseudo[regno] = first;
	110	bitmap_set_bit (&coalesced_pseudos_bitmap, regno);
	111	if (regno == regno2)
	112	break;
	113	last = regno;
	114	}
	115	next = next_coalesced_pseudo[first];
	116	next_coalesced_pseudo[first] = regno2;
	117	next_coalesced_pseudo[last] = next;
	118	lra_reg_info[first].live_ranges
	119	= (lra_merge_live_ranges
	120	(lra_reg_info[first].live_ranges,
	121	lra_copy_live_range_list (lra_reg_info[first2].live_ranges)));
	122	if (GET_MODE_SIZE (lra_reg_info[first].biggest_mode)
	123	< GET_MODE_SIZE (lra_reg_info[first2].biggest_mode))
	124	lra_reg_info[first].biggest_mode = lra_reg_info[first2].biggest_mode;
	125	}
	126
	127	/* Change pseudos in *LOC on their coalescing group
	128	representatives. */
	129	static bool
	130	substitute (rtx *loc)
	131	{
	132	int i, regno;
	133	const char *fmt;
	134	enum rtx_code code;
	135	bool res;
	136
	137	if (*loc == NULL_RTX)
	138	return false;
	139	code = GET_CODE (*loc);
	140	if (code == REG)
	141	{
	142	regno = REGNO (*loc);
	143	if (regno < FIRST_PSEUDO_REGISTER
	144	\|\| first_coalesced_pseudo[regno] == regno)
	145	return false;
146	*loc = regno_reg_rtx[first_coalesced_pseudo[regno]];
147	return true;
148	}
149
150	res = false;
151	fmt = GET_RTX_FORMAT (code);
152	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
153	{
154	if (fmt[i] == 'e')
155	{
156	if (substitute (&XEXP (*loc, i)))
157	res = true;
158	}
159	else if (fmt[i] == 'E')
160	{
161	int j;
162
163	for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
164	if (substitute (&XVECEXP (*loc, i, j)))
165	res = true;
166	}
167	}
168	return res;
169	}
170
171	/* The current iteration (1, 2, ...) of the coalescing pass. */
172	int lra_coalesce_iter;
173
174	/* Return true if the move involving REGNO1 and REGNO2 is a potential
175	memory-memory move. */
176	static bool
177	mem_move_p (int regno1, int regno2)
178	{
179	return reg_renumber[regno1] < 0 && reg_renumber[regno2] < 0;
180	}
181
182	/* Pseudos used instead of the coalesced pseudos. */
183	static bitmap_head used_pseudos_bitmap;
184
185	/* Set up USED_PSEUDOS_BITMAP, and update LR_BITMAP (a BB live info
186	bitmap). */
187	static void
188	update_live_info (bitmap lr_bitmap)
189	{
190	unsigned int j;
191	bitmap_iterator bi;
192
193	bitmap_clear (&used_pseudos_bitmap);
194	EXECUTE_IF_AND_IN_BITMAP (&coalesced_pseudos_bitmap, lr_bitmap,
195	FIRST_PSEUDO_REGISTER, j, bi)
196	bitmap_set_bit (&used_pseudos_bitmap, first_coalesced_pseudo[j]);
197	if (! bitmap_empty_p (&used_pseudos_bitmap))
198	{
199	bitmap_and_compl_into (lr_bitmap, &coalesced_pseudos_bitmap);
200	bitmap_ior_into (lr_bitmap, &used_pseudos_bitmap);
201	}
202	}
203
638e746e	204	/* Return true if pseudo REGNO can be potentially coalesced. */
c6a6cdaa	205	static bool
638e746e	206	coalescable_pseudo_p (int regno)
c6a6cdaa	207	{
c6a6cdaa	208	lra_assert (regno >= FIRST_PSEUDO_REGISTER);
638e746e	209	return (/* We don't want to coalesce regnos with equivalences, at
c6a6cdaa	210	least without updating this info. */
638e746e	211	ira_reg_equiv[regno].constant == NULL_RTX
c6a6cdaa	212	&& ira_reg_equiv[regno].memory == NULL_RTX
	213	&& ira_reg_equiv[regno].invariant == NULL_RTX);
	214	}
	215
	216	/* The major function for aggressive pseudo coalescing of moves only
	217	if the both pseudos were spilled and not special reload pseudos. */
	218	bool
	219	lra_coalesce (void)
	220	{
	221	basic_block bb;
	222	rtx mv, set, insn, next, *sorted_moves;
638e746e	223	int i, mv_num, sregno, dregno;
c6a6cdaa	224	int coalesced_moves;
c6a6cdaa	225	int max_regno = max_reg_num ();
638e746e	226	bitmap_head involved_insns_bitmap;
c6a6cdaa	227
	228	timevar_push (TV_LRA_COALESCE);
	229
	230	if (lra_dump_file != NULL)
	231	fprintf (lra_dump_file,
	232	"\n******** Pseudos coalescing #%d: ********\n\n",
	233	++lra_coalesce_iter);
	234	first_coalesced_pseudo = XNEWVEC (int, max_regno);
	235	next_coalesced_pseudo = XNEWVEC (int, max_regno);
	236	for (i = 0; i < max_regno; i++)
	237	first_coalesced_pseudo[i] = next_coalesced_pseudo[i] = i;
	238	sorted_moves = XNEWVEC (rtx, get_max_uid ());
	239	mv_num = 0;
c6a6cdaa	240	/* Collect moves. */
c6a6cdaa	241	coalesced_moves = 0;
fc00614f	242	FOR_EACH_BB_FN (bb, cfun)
c6a6cdaa	243	{
	244	FOR_BB_INSNS_SAFE (bb, insn, next)
	245	if (INSN_P (insn)
	246	&& (set = single_set (insn)) != NULL_RTX
	247	&& REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))
	248	&& (sregno = REGNO (SET_SRC (set))) >= FIRST_PSEUDO_REGISTER
	249	&& (dregno = REGNO (SET_DEST (set))) >= FIRST_PSEUDO_REGISTER
	250	&& mem_move_p (sregno, dregno)
638e746e	251	&& coalescable_pseudo_p (sregno) && coalescable_pseudo_p (dregno)
c6a6cdaa	252	&& ! side_effects_p (set)
	253	&& !(lra_intersected_live_ranges_p
	254	(lra_reg_info[sregno].live_ranges,
	255	lra_reg_info[dregno].live_ranges)))
	256	sorted_moves[mv_num++] = insn;
	257	}
c6a6cdaa	258	qsort (sorted_moves, mv_num, sizeof (rtx), move_freq_compare_func);
	259	/* Coalesced copies, most frequently executed first. */
	260	bitmap_initialize (&coalesced_pseudos_bitmap, &reg_obstack);
	261	bitmap_initialize (&involved_insns_bitmap, &reg_obstack);
	262	for (i = 0; i < mv_num; i++)
	263	{
	264	mv = sorted_moves[i];
	265	set = single_set (mv);
	266	lra_assert (set != NULL && REG_P (SET_SRC (set))
	267	&& REG_P (SET_DEST (set)));
	268	sregno = REGNO (SET_SRC (set));
	269	dregno = REGNO (SET_DEST (set));
	270	if (first_coalesced_pseudo[sregno] == first_coalesced_pseudo[dregno])
	271	{
	272	coalesced_moves++;
	273	if (lra_dump_file != NULL)
	274	fprintf
	275	(lra_dump_file, " Coalescing move %i:r%d-r%d (freq=%d)\n",
	276	INSN_UID (mv), sregno, dregno,
	277	BLOCK_FOR_INSN (mv)->frequency);
	278	/* We updated involved_insns_bitmap when doing the merge. */
	279	}
	280	else if (!(lra_intersected_live_ranges_p
	281	(lra_reg_info[first_coalesced_pseudo[sregno]].live_ranges,
	282	lra_reg_info[first_coalesced_pseudo[dregno]].live_ranges)))
	283	{
	284	coalesced_moves++;
	285	if (lra_dump_file != NULL)
	286	fprintf
	287	(lra_dump_file,
	288	" Coalescing move %i:r%d(%d)-r%d(%d) (freq=%d)\n",
	289	INSN_UID (mv), sregno, ORIGINAL_REGNO (SET_SRC (set)),
	290	dregno, ORIGINAL_REGNO (SET_DEST (set)),
	291	BLOCK_FOR_INSN (mv)->frequency);
	292	bitmap_ior_into (&involved_insns_bitmap,
	293	&lra_reg_info[sregno].insn_bitmap);
	294	bitmap_ior_into (&involved_insns_bitmap,
	295	&lra_reg_info[dregno].insn_bitmap);
	296	merge_pseudos (sregno, dregno);
	297	}
	298	}
	299	bitmap_initialize (&used_pseudos_bitmap, &reg_obstack);
fc00614f	300	FOR_EACH_BB_FN (bb, cfun)
c6a6cdaa	301	{
	302	update_live_info (df_get_live_in (bb));
	303	update_live_info (df_get_live_out (bb));
	304	FOR_BB_INSNS_SAFE (bb, insn, next)
	305	if (INSN_P (insn)
	306	&& bitmap_bit_p (&involved_insns_bitmap, INSN_UID (insn)))
	307	{
	308	if (! substitute (&insn))
	309	continue;
	310	lra_update_insn_regno_info (insn);
	311	if ((set = single_set (insn)) != NULL_RTX && set_noop_p (set))
	312	{
	313	/* Coalesced move. */
	314	if (lra_dump_file != NULL)
	315	fprintf (lra_dump_file, " Removing move %i (freq=%d)\n",
	316	INSN_UID (insn), BLOCK_FOR_INSN (insn)->frequency);
	317	lra_set_insn_deleted (insn);
	318	}
	319	}
	320	}
	321	bitmap_clear (&used_pseudos_bitmap);
	322	bitmap_clear (&involved_insns_bitmap);
	323	bitmap_clear (&coalesced_pseudos_bitmap);
	324	if (lra_dump_file != NULL && coalesced_moves != 0)
	325	fprintf (lra_dump_file, "Coalesced Moves = %d\n", coalesced_moves);
	326	free (sorted_moves);
	327	free (next_coalesced_pseudo);
	328	free (first_coalesced_pseudo);
	329	timevar_pop (TV_LRA_COALESCE);
	330	return coalesced_moves != 0;
	331	}