[gcc.git] / gcc / tracer.c

/* The tracer pass for the GNU compiler.
   Contributed by Jan Hubicka, SuSE Labs.
   Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.

   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 2, 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 COPYING.  If not, write to the Free
   Software Foundation, 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.  */

/* This pass performs the tail duplication needed for superblock formation.
   For more information see:

     Design and Analysis of Profile-Based Optimization in Compaq's
     Compilation Tools for Alpha; Journal of Instruction-Level
     Parallelism 3 (2000) 1-25

   Unlike Compaq's implementation we don't do the loop peeling as most
   probably a better job can be done by a special pass and we don't
   need to worry too much about the code size implications as the tail
   duplicates are crossjumped again if optimizations are not
   performed.  */


#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "cfglayout.h"
#include "fibheap.h"
#include "flags.h"
#include "timevar.h"
#include "params.h"
#include "coverage.h"

static int count_insns (basic_block);
static bool ignore_bb_p (basic_block);
static bool better_p (edge, edge);
static edge find_best_successor (basic_block);
static edge find_best_predecessor (basic_block);
static int find_trace (basic_block, basic_block *);
static void tail_duplicate (void);
static void layout_superblocks (void);

/* Minimal outgoing edge probability considered for superblock formation.  */
static int probability_cutoff;
static int branch_ratio_cutoff;

/* Return true if BB has been seen - it is connected to some trace
   already.  */

#define seen(bb) (bb->rbi->visited || bb->rbi->next)

/* Return true if we should ignore the basic block for purposes of tracing.  */
static bool
ignore_bb_p (basic_block bb)
{
  if (bb->index < 0)
    return true;
  if (!maybe_hot_bb_p (bb))
    return true;
  return false;
}

/* Return number of instructions in the block.  */

static int
count_insns (basic_block bb)
{
  rtx insn;
  int n = 0;

  for (insn = BB_HEAD (bb);
       insn != NEXT_INSN (BB_END (bb));
       insn = NEXT_INSN (insn))
    if (active_insn_p (insn))
      n++;
  return n;
}

/* Return true if E1 is more frequent than E2.  */
static bool
better_p (edge e1, edge e2)
{
  if (e1->count != e2->count)
    return e1->count > e2->count;
  if (e1->src->frequency * e1->probability !=
      e2->src->frequency * e2->probability)
    return (e1->src->frequency * e1->probability
	    > e2->src->frequency * e2->probability);
  /* This is needed to avoid changes in the decision after
     CFG is modified.  */
  if (e1->src != e2->src)
    return e1->src->index > e2->src->index;
  return e1->dest->index > e2->dest->index;
}

/* Return most frequent successor of basic block BB.  */

static edge
find_best_successor (basic_block bb)
{
  edge e;
  edge best = NULL;

  for (e = bb->succ; e; e = e->succ_next)
    if (!best || better_p (e, best))
      best = e;
  if (!best || ignore_bb_p (best->dest))
    return NULL;
  if (best->probability <= probability_cutoff)
    return NULL;
  return best;
}

/* Return most frequent predecessor of basic block BB.  */

static edge
find_best_predecessor (basic_block bb)
{
  edge e;
  edge best = NULL;

  for (e = bb->pred; e; e = e->pred_next)
    if (!best || better_p (e, best))
      best = e;
  if (!best || ignore_bb_p (best->src))
    return NULL;
  if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
      < bb->frequency * branch_ratio_cutoff)
    return NULL;
  return best;
}

/* Find the trace using bb and record it in the TRACE array.
   Return number of basic blocks recorded.  */

static int
find_trace (basic_block bb, basic_block *trace)
{
  int i = 0;
  edge e;

  if (dump_file)
    fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);

  while ((e = find_best_predecessor (bb)) != NULL)
    {
      basic_block bb2 = e->src;
      if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
	  || find_best_successor (bb2) != e)
	break;
      if (dump_file)
	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
      bb = bb2;
    }
  if (dump_file)
    fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
  trace[i++] = bb;

  /* Follow the trace in forward direction.  */
  while ((e = find_best_successor (bb)) != NULL)
    {
      bb = e->dest;
      if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
	  || find_best_predecessor (bb) != e)
	break;
      if (dump_file)
	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
      trace[i++] = bb;
    }
  if (dump_file)
    fprintf (dump_file, "\n");
  return i;
}

/* Look for basic blocks in frequency order, construct traces and tail duplicate
   if profitable.  */

static void
tail_duplicate (void)
{
  fibnode_t *blocks = xcalloc (last_basic_block, sizeof (fibnode_t));
  basic_block *trace = xmalloc (sizeof (basic_block) * n_basic_blocks);
  int *counts = xmalloc (sizeof (int) * last_basic_block);
  int ninsns = 0, nduplicated = 0;
  gcov_type weighted_insns = 0, traced_insns = 0;
  fibheap_t heap = fibheap_new ();
  gcov_type cover_insns;
  int max_dup_insns;
  basic_block bb;

  if (profile_info && flag_branch_probabilities)
    probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
  else
    probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
  probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;

  branch_ratio_cutoff =
    (REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));

  FOR_EACH_BB (bb)
    {
      int n = count_insns (bb);
      if (!ignore_bb_p (bb))
	blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
					    bb);

      counts [bb->index] = n;
      ninsns += n;
      weighted_insns += n * bb->frequency;
    }

  if (profile_info && flag_branch_probabilities)
    cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
  else
    cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
  cover_insns = (weighted_insns * cover_insns + 50) / 100;
  max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;

  while (traced_insns < cover_insns && nduplicated < max_dup_insns
         && !fibheap_empty (heap))
    {
      basic_block bb = fibheap_extract_min (heap);
      int n, pos;

      if (!bb)
	break;

      blocks[bb->index] = NULL;

      if (ignore_bb_p (bb))
	continue;
      if (seen (bb))
	abort ();

      n = find_trace (bb, trace);

      bb = trace[0];
      traced_insns += bb->frequency * counts [bb->index];
      if (blocks[bb->index])
	{
	  fibheap_delete_node (heap, blocks[bb->index]);
	  blocks[bb->index] = NULL;
	}

      for (pos = 1; pos < n; pos++)
	{
	  basic_block bb2 = trace[pos];

	  if (blocks[bb2->index])
	    {
	      fibheap_delete_node (heap, blocks[bb2->index]);
	      blocks[bb2->index] = NULL;
	    }
	  traced_insns += bb2->frequency * counts [bb2->index];
	  if (bb2->pred && bb2->pred->pred_next
	      && can_duplicate_block_p (bb2))
	    {
	      edge e = bb2->pred;
	      basic_block old = bb2;

	      while (e->src != bb)
		e = e->pred_next;
	      nduplicated += counts [bb2->index];
	      bb2 = duplicate_block (bb2, e);

	      /* Reconsider the original copy of block we've duplicated.
	         Removing the most common predecessor may make it to be
	         head.  */
	      blocks[old->index] =
		fibheap_insert (heap, -old->frequency, old);

	      if (dump_file)
		fprintf (dump_file, "Duplicated %i as %i [%i]\n",
			 old->index, bb2->index, bb2->frequency);
	    }
	  bb->rbi->next = bb2;
	  bb2->rbi->visited = 1;
	  bb = bb2;
	  /* In case the trace became infrequent, stop duplicating.  */
	  if (ignore_bb_p (bb))
	    break;
	}
      if (dump_file)
	fprintf (dump_file, " covered now %.1f\n\n",
		 traced_insns * 100.0 / weighted_insns);
    }
  if (dump_file)
    fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
	     nduplicated * 100 / ninsns);

  free (blocks);
  free (trace);
  free (counts);
  fibheap_delete (heap);
}

/* Connect the superblocks into linear sequence.  At the moment we attempt to keep
   the original order as much as possible, but the algorithm may be made smarter
   later if needed.  BB reordering pass should void most of the benefits of such
   change though.  */

static void
layout_superblocks (void)
{
  basic_block end = ENTRY_BLOCK_PTR->succ->dest;
  basic_block bb = ENTRY_BLOCK_PTR->succ->dest->next_bb;

  while (bb != EXIT_BLOCK_PTR)
    {
      edge e, best = NULL;
      while (end->rbi->next)
	end = end->rbi->next;

      for (e = end->succ; e; e = e->succ_next)
	if (e->dest != EXIT_BLOCK_PTR
	    && e->dest != ENTRY_BLOCK_PTR->succ->dest
	    && !e->dest->rbi->visited
	    && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
	  best = e;

      if (best)
	{
	  end->rbi->next = best->dest;
	  best->dest->rbi->visited = 1;
	}
      else
	for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
	  {
	    if (!bb->rbi->visited)
	      {
		end->rbi->next = bb;
		bb->rbi->visited = 1;
		break;
	      }
	  }
    }
}

/* Main entry point to this file.  */

void
tracer (void)
{
  if (n_basic_blocks <= 1)
    return;

  timevar_push (TV_TRACER);

  cfg_layout_initialize ();
  mark_dfs_back_edges ();
  if (dump_file)
    dump_flow_info (dump_file);
  tail_duplicate ();
  layout_superblocks ();
  if (dump_file)
    dump_flow_info (dump_file);
  cfg_layout_finalize ();

  /* Merge basic blocks in duplicated traces.  */
  cleanup_cfg (CLEANUP_EXPENSIVE);

  timevar_pop (TV_TRACER);
}
Commit	Line	Data
5c856b23 JH	1	/* The tracer pass for the GNU compiler.
5c856b23 JH	2	Contributed by Jan Hubicka, SuSE Labs.
88462c42	3	Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5c856b23 JH	4
	5	This file is part of GCC.
	6
	7	GCC is free software; you can redistribute it and/or modify it
	8	under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 2, or (at your option)
	10	any later version.
	11
	12	GCC is distributed in the hope that it will be useful, but WITHOUT
	13	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	14	or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
	15	License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with GCC; see the file COPYING. If not, write to the Free
	19	Software Foundation, 59 Temple Place - Suite 330, Boston, MA
	20	02111-1307, USA. */
	21
	22	/* This pass performs the tail duplication needed for superblock formation.
	23	For more information see:
	24
	25	Design and Analysis of Profile-Based Optimization in Compaq's
	26	Compilation Tools for Alpha; Journal of Instruction-Level
	27	Parallelism 3 (2000) 1-25
	28
	29	Unlike Compaq's implementation we don't do the loop peeling as most
	30	probably a better job can be done by a special pass and we don't
	31	need to worry too much about the code size implications as the tail
	32	duplicates are crossjumped again if optimizations are not
	33	performed. */
	34
	35
	36	#include "config.h"
	37	#include "system.h"
4977bab6 ZW	38	#include "coretypes.h"
4977bab6 ZW	39	#include "tm.h"
5c856b23 JH	40	#include "tree.h"
	41	#include "rtl.h"
	42	#include "hard-reg-set.h"
	43	#include "basic-block.h"
	44	#include "output.h"
	45	#include "cfglayout.h"
	46	#include "fibheap.h"
	47	#include "flags.h"
38700cee	48	#include "timevar.h"
5c856b23	49	#include "params.h"
ca29da43	50	#include "coverage.h"
5c856b23	51
46c5ad27 AJ	52	static int count_insns (basic_block);
	53	static bool ignore_bb_p (basic_block);
	54	static bool better_p (edge, edge);
	55	static edge find_best_successor (basic_block);
	56	static edge find_best_predecessor (basic_block);
	57	static int find_trace (basic_block, basic_block *);
	58	static void tail_duplicate (void);
	59	static void layout_superblocks (void);
5c856b23 JH	60
	61	/* Minimal outgoing edge probability considered for superblock formation. */
	62	static int probability_cutoff;
	63	static int branch_ratio_cutoff;
	64
	65	/* Return true if BB has been seen - it is connected to some trace
	66	already. */
	67
bc35512f	68	#define seen(bb) (bb->rbi->visited \|\| bb->rbi->next)
5c856b23	69
4b7e68e7	70	/* Return true if we should ignore the basic block for purposes of tracing. */
5c856b23	71	static bool
46c5ad27	72	ignore_bb_p (basic_block bb)
5c856b23 JH	73	{
	74	if (bb->index < 0)
	75	return true;
	76	if (!maybe_hot_bb_p (bb))
	77	return true;
	78	return false;
	79	}
	80
	81	/* Return number of instructions in the block. */
	82
	83	static int
46c5ad27	84	count_insns (basic_block bb)
5c856b23 JH	85	{
	86	rtx insn;
	87	int n = 0;
	88
a813c111 SB	89	for (insn = BB_HEAD (bb);
	90	insn != NEXT_INSN (BB_END (bb));
	91	insn = NEXT_INSN (insn))
5c856b23 JH	92	if (active_insn_p (insn))
	93	n++;
	94	return n;
	95	}
	96
	97	/* Return true if E1 is more frequent than E2. */
	98	static bool
46c5ad27	99	better_p (edge e1, edge e2)
5c856b23 JH	100	{
	101	if (e1->count != e2->count)
	102	return e1->count > e2->count;
	103	if (e1->src->frequency * e1->probability !=
	104	e2->src->frequency * e2->probability)
	105	return (e1->src->frequency * e1->probability
	106	> e2->src->frequency * e2->probability);
	107	/* This is needed to avoid changes in the decision after
	108	CFG is modified. */
	109	if (e1->src != e2->src)
	110	return e1->src->index > e2->src->index;
	111	return e1->dest->index > e2->dest->index;
	112	}
	113
	114	/* Return most frequent successor of basic block BB. */
	115
	116	static edge
46c5ad27	117	find_best_successor (basic_block bb)
5c856b23 JH	118	{
	119	edge e;
	120	edge best = NULL;
	121
	122	for (e = bb->succ; e; e = e->succ_next)
	123	if (!best \|\| better_p (e, best))
	124	best = e;
	125	if (!best \|\| ignore_bb_p (best->dest))
	126	return NULL;
	127	if (best->probability <= probability_cutoff)
	128	return NULL;
	129	return best;
	130	}
	131
	132	/* Return most frequent predecessor of basic block BB. */
	133
	134	static edge
46c5ad27	135	find_best_predecessor (basic_block bb)
5c856b23 JH	136	{
	137	edge e;
	138	edge best = NULL;
	139
	140	for (e = bb->pred; e; e = e->pred_next)
	141	if (!best \|\| better_p (e, best))
	142	best = e;
	143	if (!best \|\| ignore_bb_p (best->src))
	144	return NULL;
	145	if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
	146	< bb->frequency * branch_ratio_cutoff)
	147	return NULL;
	148	return best;
	149	}
	150
	151	/* Find the trace using bb and record it in the TRACE array.
	152	Return number of basic blocks recorded. */
	153
	154	static int
46c5ad27	155	find_trace (basic_block bb, basic_block *trace)
5c856b23 JH	156	{
	157	int i = 0;
	158	edge e;
	159
c263766c RH	160	if (dump_file)
c263766c RH	161	fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
5c856b23 JH	162
	163	while ((e = find_best_predecessor (bb)) != NULL)
	164	{
	165	basic_block bb2 = e->src;
	166	if (seen (bb2) \|\| (e->flags & (EDGE_DFS_BACK \| EDGE_COMPLEX))
	167	\|\| find_best_successor (bb2) != e)
	168	break;
c263766c RH	169	if (dump_file)
c263766c RH	170	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
5c856b23 JH	171	bb = bb2;
5c856b23 JH	172	}
c263766c RH	173	if (dump_file)
c263766c RH	174	fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
5c856b23 JH	175	trace[i++] = bb;
	176
	177	/* Follow the trace in forward direction. */
	178	while ((e = find_best_successor (bb)) != NULL)
	179	{
	180	bb = e->dest;
	181	if (seen (bb) \|\| (e->flags & (EDGE_DFS_BACK \| EDGE_COMPLEX))
	182	\|\| find_best_predecessor (bb) != e)
	183	break;
c263766c RH	184	if (dump_file)
c263766c RH	185	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
5c856b23 JH	186	trace[i++] = bb;
5c856b23 JH	187	}
c263766c RH	188	if (dump_file)
c263766c RH	189	fprintf (dump_file, "\n");
5c856b23 JH	190	return i;
	191	}
	192
	193	/* Look for basic blocks in frequency order, construct traces and tail duplicate
	194	if profitable. */
	195
	196	static void
46c5ad27	197	tail_duplicate (void)
5c856b23 JH	198	{
	199	fibnode_t *blocks = xcalloc (last_basic_block, sizeof (fibnode_t));
	200	basic_block trace = xmalloc (sizeof (basic_block) n_basic_blocks);
	201	int counts = xmalloc (sizeof (int) last_basic_block);
	202	int ninsns = 0, nduplicated = 0;
	203	gcov_type weighted_insns = 0, traced_insns = 0;
	204	fibheap_t heap = fibheap_new ();
	205	gcov_type cover_insns;
	206	int max_dup_insns;
	207	basic_block bb;
	208
cdb23767	209	if (profile_info && flag_branch_probabilities)
5c856b23 JH	210	probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
	211	else
	212	probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
	213	probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
	214
	215	branch_ratio_cutoff =
	216	(REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
	217
	218	FOR_EACH_BB (bb)
	219	{
	220	int n = count_insns (bb);
	221	if (!ignore_bb_p (bb))
	222	blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
	223	bb);
	224
	225	counts [bb->index] = n;
	226	ninsns += n;
	227	weighted_insns += n * bb->frequency;
	228	}
	229
cdb23767	230	if (profile_info && flag_branch_probabilities)
5c856b23 JH	231	cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
	232	else
	233	cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
	234	cover_insns = (weighted_insns * cover_insns + 50) / 100;
	235	max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
	236
	237	while (traced_insns < cover_insns && nduplicated < max_dup_insns
	238	&& !fibheap_empty (heap))
	239	{
	240	basic_block bb = fibheap_extract_min (heap);
	241	int n, pos;
	242
	243	if (!bb)
	244	break;
	245
	246	blocks[bb->index] = NULL;
	247
	248	if (ignore_bb_p (bb))
	249	continue;
	250	if (seen (bb))
	251	abort ();
	252
	253	n = find_trace (bb, trace);
	254
	255	bb = trace[0];
	256	traced_insns += bb->frequency * counts [bb->index];
	257	if (blocks[bb->index])
	258	{
	259	fibheap_delete_node (heap, blocks[bb->index]);
	260	blocks[bb->index] = NULL;
	261	}
	262
	263	for (pos = 1; pos < n; pos++)
	264	{
	265	basic_block bb2 = trace[pos];
	266
	267	if (blocks[bb2->index])
	268	{
	269	fibheap_delete_node (heap, blocks[bb2->index]);
	270	blocks[bb2->index] = NULL;
	271	}
	272	traced_insns += bb2->frequency * counts [bb2->index];
	273	if (bb2->pred && bb2->pred->pred_next
6de9cd9a	274	&& can_duplicate_block_p (bb2))
5c856b23 JH	275	{
	276	edge e = bb2->pred;
	277	basic_block old = bb2;
	278
	279	while (e->src != bb)
	280	e = e->pred_next;
	281	nduplicated += counts [bb2->index];
6de9cd9a	282	bb2 = duplicate_block (bb2, e);
5c856b23 JH	283
5c856b23 JH	284	/* Reconsider the original copy of block we've duplicated.
14b493d6	285	Removing the most common predecessor may make it to be
5c856b23 JH	286	head. */
	287	blocks[old->index] =
	288	fibheap_insert (heap, -old->frequency, old);
	289
c263766c RH	290	if (dump_file)
c263766c RH	291	fprintf (dump_file, "Duplicated %i as %i [%i]\n",
5c856b23 JH	292	old->index, bb2->index, bb2->frequency);
5c856b23 JH	293	}
bc35512f JH	294	bb->rbi->next = bb2;
bc35512f JH	295	bb2->rbi->visited = 1;
5c856b23 JH	296	bb = bb2;
	297	/* In case the trace became infrequent, stop duplicating. */
	298	if (ignore_bb_p (bb))
	299	break;
	300	}
c263766c RH	301	if (dump_file)
c263766c RH	302	fprintf (dump_file, " covered now %.1f\n\n",
5c856b23 JH	303	traced_insns * 100.0 / weighted_insns);
5c856b23 JH	304	}
c263766c RH	305	if (dump_file)
c263766c RH	306	fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
5c856b23 JH	307	nduplicated * 100 / ninsns);
	308
	309	free (blocks);
	310	free (trace);
	311	free (counts);
	312	fibheap_delete (heap);
	313	}
	314
4d6922ee	315	/* Connect the superblocks into linear sequence. At the moment we attempt to keep
5c856b23 JH	316	the original order as much as possible, but the algorithm may be made smarter
	317	later if needed. BB reordering pass should void most of the benefits of such
	318	change though. */
	319
	320	static void
46c5ad27	321	layout_superblocks (void)
5c856b23 JH	322	{
	323	basic_block end = ENTRY_BLOCK_PTR->succ->dest;
	324	basic_block bb = ENTRY_BLOCK_PTR->succ->dest->next_bb;
	325
	326	while (bb != EXIT_BLOCK_PTR)
	327	{
	328	edge e, best = NULL;
bc35512f JH	329	while (end->rbi->next)
bc35512f JH	330	end = end->rbi->next;
5c856b23 JH	331
	332	for (e = end->succ; e; e = e->succ_next)
	333	if (e->dest != EXIT_BLOCK_PTR
	334	&& e->dest != ENTRY_BLOCK_PTR->succ->dest
bc35512f	335	&& !e->dest->rbi->visited
5c856b23 JH	336	&& (!best \|\| EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
	337	best = e;
	338
	339	if (best)
	340	{
bc35512f JH	341	end->rbi->next = best->dest;
bc35512f JH	342	best->dest->rbi->visited = 1;
5c856b23 JH	343	}
5c856b23 JH	344	else
6a87d634	345	for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
5c856b23	346	{
bc35512f	347	if (!bb->rbi->visited)
5c856b23	348	{
bc35512f JH	349	end->rbi->next = bb;
bc35512f JH	350	bb->rbi->visited = 1;
5c856b23 JH	351	break;
	352	}
	353	}
	354	}
	355	}
	356
	357	/* Main entry point to this file. */
	358
	359	void
46c5ad27	360	tracer (void)
5c856b23 JH	361	{
	362	if (n_basic_blocks <= 1)
	363	return;
38700cee SB	364
	365	timevar_push (TV_TRACER);
	366
bc35512f	367	cfg_layout_initialize ();
5c856b23	368	mark_dfs_back_edges ();
c263766c RH	369	if (dump_file)
c263766c RH	370	dump_flow_info (dump_file);
5c856b23 JH	371	tail_duplicate ();
5c856b23 JH	372	layout_superblocks ();
c263766c RH	373	if (dump_file)
c263766c RH	374	dump_flow_info (dump_file);
5c856b23	375	cfg_layout_finalize ();
38700cee	376
5c856b23 JH	377	/* Merge basic blocks in duplicated traces. */
5c856b23 JH	378	cleanup_cfg (CLEANUP_EXPENSIVE);
38700cee SB	379
38700cee SB	380	timevar_pop (TV_TRACER);
5c856b23	381	}