[thirdparty/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;
  edge_iterator ei;

  FOR_EACH_EDGE (e, ei, bb->succs)
    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;
  edge_iterator ei;

  FOR_EACH_EDGE (e, ei, bb->preds)
    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;
      gcc_assert (!seen (bb));

      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 (EDGE_COUNT (bb2->preds) > 1
	      && can_duplicate_block_p (bb2))
	    {
	      edge e;
	      edge_iterator ei;
	      basic_block old = bb2;

	      FOR_EACH_EDGE (e, ei, bb2->preds)
		if (e->src == bb)
		  break;

	      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 = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
  basic_block bb = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->next_bb;

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

      FOR_EACH_EDGE (e, ei, end->succs)
	if (e->dest != EXIT_BLOCK_PTR
	    && e->dest != EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->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.  FLAGS is the set of flags to pass
   to cfg_layout_initialize().  */

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

  timevar_push (TV_TRACER);

  cfg_layout_initialize (flags);
  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;
628f6a4e	121	edge_iterator ei;
5c856b23	122
628f6a4e	123	FOR_EACH_EDGE (e, ei, bb->succs)
5c856b23 JH	124	if (!best \|\| better_p (e, best))
	125	best = e;
	126	if (!best \|\| ignore_bb_p (best->dest))
	127	return NULL;
	128	if (best->probability <= probability_cutoff)
	129	return NULL;
	130	return best;
	131	}
	132
	133	/* Return most frequent predecessor of basic block BB. */
	134
	135	static edge
46c5ad27	136	find_best_predecessor (basic_block bb)
5c856b23 JH	137	{
	138	edge e;
	139	edge best = NULL;
628f6a4e	140	edge_iterator ei;
5c856b23	141
628f6a4e	142	FOR_EACH_EDGE (e, ei, bb->preds)
5c856b23 JH	143	if (!best \|\| better_p (e, best))
	144	best = e;
	145	if (!best \|\| ignore_bb_p (best->src))
	146	return NULL;
	147	if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
	148	< bb->frequency * branch_ratio_cutoff)
	149	return NULL;
	150	return best;
	151	}
	152
	153	/* Find the trace using bb and record it in the TRACE array.
	154	Return number of basic blocks recorded. */
	155
	156	static int
46c5ad27	157	find_trace (basic_block bb, basic_block *trace)
5c856b23 JH	158	{
	159	int i = 0;
	160	edge e;
	161
c263766c RH	162	if (dump_file)
c263766c RH	163	fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
5c856b23 JH	164
	165	while ((e = find_best_predecessor (bb)) != NULL)
	166	{
	167	basic_block bb2 = e->src;
	168	if (seen (bb2) \|\| (e->flags & (EDGE_DFS_BACK \| EDGE_COMPLEX))
	169	\|\| find_best_successor (bb2) != e)
	170	break;
c263766c RH	171	if (dump_file)
c263766c RH	172	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
5c856b23 JH	173	bb = bb2;
5c856b23 JH	174	}
c263766c RH	175	if (dump_file)
c263766c RH	176	fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
5c856b23 JH	177	trace[i++] = bb;
	178
	179	/* Follow the trace in forward direction. */
	180	while ((e = find_best_successor (bb)) != NULL)
	181	{
	182	bb = e->dest;
	183	if (seen (bb) \|\| (e->flags & (EDGE_DFS_BACK \| EDGE_COMPLEX))
	184	\|\| find_best_predecessor (bb) != e)
	185	break;
c263766c RH	186	if (dump_file)
c263766c RH	187	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
5c856b23 JH	188	trace[i++] = bb;
5c856b23 JH	189	}
c263766c RH	190	if (dump_file)
c263766c RH	191	fprintf (dump_file, "\n");
5c856b23 JH	192	return i;
	193	}
	194
	195	/* Look for basic blocks in frequency order, construct traces and tail duplicate
	196	if profitable. */
	197
	198	static void
46c5ad27	199	tail_duplicate (void)
5c856b23 JH	200	{
	201	fibnode_t *blocks = xcalloc (last_basic_block, sizeof (fibnode_t));
	202	basic_block trace = xmalloc (sizeof (basic_block) n_basic_blocks);
	203	int counts = xmalloc (sizeof (int) last_basic_block);
	204	int ninsns = 0, nduplicated = 0;
	205	gcov_type weighted_insns = 0, traced_insns = 0;
	206	fibheap_t heap = fibheap_new ();
	207	gcov_type cover_insns;
	208	int max_dup_insns;
	209	basic_block bb;
	210
cdb23767	211	if (profile_info && flag_branch_probabilities)
5c856b23 JH	212	probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
	213	else
	214	probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
	215	probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
	216
	217	branch_ratio_cutoff =
	218	(REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
	219
	220	FOR_EACH_BB (bb)
	221	{
	222	int n = count_insns (bb);
	223	if (!ignore_bb_p (bb))
	224	blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
	225	bb);
	226
	227	counts [bb->index] = n;
	228	ninsns += n;
	229	weighted_insns += n * bb->frequency;
	230	}
	231
cdb23767	232	if (profile_info && flag_branch_probabilities)
5c856b23 JH	233	cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
	234	else
	235	cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
	236	cover_insns = (weighted_insns * cover_insns + 50) / 100;
	237	max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
	238
	239	while (traced_insns < cover_insns && nduplicated < max_dup_insns
	240	&& !fibheap_empty (heap))
	241	{
	242	basic_block bb = fibheap_extract_min (heap);
	243	int n, pos;
	244
	245	if (!bb)
	246	break;
	247
	248	blocks[bb->index] = NULL;
	249
	250	if (ignore_bb_p (bb))
	251	continue;
1e128c5f	252	gcc_assert (!seen (bb));
5c856b23 JH	253
	254	n = find_trace (bb, trace);
	255
	256	bb = trace[0];
	257	traced_insns += bb->frequency * counts [bb->index];
	258	if (blocks[bb->index])
	259	{
	260	fibheap_delete_node (heap, blocks[bb->index]);
	261	blocks[bb->index] = NULL;
	262	}
	263
	264	for (pos = 1; pos < n; pos++)
	265	{
	266	basic_block bb2 = trace[pos];
	267
	268	if (blocks[bb2->index])
	269	{
	270	fibheap_delete_node (heap, blocks[bb2->index]);
	271	blocks[bb2->index] = NULL;
	272	}
	273	traced_insns += bb2->frequency * counts [bb2->index];
628f6a4e	274	if (EDGE_COUNT (bb2->preds) > 1
6de9cd9a	275	&& can_duplicate_block_p (bb2))
5c856b23	276	{
628f6a4e BE	277	edge e;
628f6a4e BE	278	edge_iterator ei;
5c856b23 JH	279	basic_block old = bb2;
5c856b23 JH	280
628f6a4e BE	281	FOR_EACH_EDGE (e, ei, bb2->preds)
	282	if (e->src == bb)
	283	break;
	284
5c856b23	285	nduplicated += counts [bb2->index];
6de9cd9a	286	bb2 = duplicate_block (bb2, e);
5c856b23 JH	287
5c856b23 JH	288	/* Reconsider the original copy of block we've duplicated.
14b493d6	289	Removing the most common predecessor may make it to be
5c856b23 JH	290	head. */
	291	blocks[old->index] =
	292	fibheap_insert (heap, -old->frequency, old);
	293
c263766c RH	294	if (dump_file)
c263766c RH	295	fprintf (dump_file, "Duplicated %i as %i [%i]\n",
5c856b23 JH	296	old->index, bb2->index, bb2->frequency);
5c856b23 JH	297	}
bc35512f JH	298	bb->rbi->next = bb2;
bc35512f JH	299	bb2->rbi->visited = 1;
5c856b23 JH	300	bb = bb2;
	301	/* In case the trace became infrequent, stop duplicating. */
	302	if (ignore_bb_p (bb))
	303	break;
	304	}
c263766c RH	305	if (dump_file)
c263766c RH	306	fprintf (dump_file, " covered now %.1f\n\n",
5c856b23 JH	307	traced_insns * 100.0 / weighted_insns);
5c856b23 JH	308	}
c263766c RH	309	if (dump_file)
c263766c RH	310	fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
5c856b23 JH	311	nduplicated * 100 / ninsns);
	312
	313	free (blocks);
	314	free (trace);
	315	free (counts);
	316	fibheap_delete (heap);
	317	}
	318
4d6922ee	319	/* Connect the superblocks into linear sequence. At the moment we attempt to keep
5c856b23 JH	320	the original order as much as possible, but the algorithm may be made smarter
	321	later if needed. BB reordering pass should void most of the benefits of such
	322	change though. */
	323
	324	static void
46c5ad27	325	layout_superblocks (void)
5c856b23	326	{
628f6a4e BE	327	basic_block end = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest;
628f6a4e BE	328	basic_block bb = EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest->next_bb;
5c856b23 JH	329
	330	while (bb != EXIT_BLOCK_PTR)
	331	{
628f6a4e	332	edge_iterator ei;
5c856b23	333	edge e, best = NULL;
bc35512f JH	334	while (end->rbi->next)
bc35512f JH	335	end = end->rbi->next;
5c856b23	336
628f6a4e	337	FOR_EACH_EDGE (e, ei, end->succs)
5c856b23	338	if (e->dest != EXIT_BLOCK_PTR
628f6a4e	339	&& e->dest != EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest
bc35512f	340	&& !e->dest->rbi->visited
5c856b23 JH	341	&& (!best \|\| EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
	342	best = e;
	343
	344	if (best)
	345	{
bc35512f JH	346	end->rbi->next = best->dest;
bc35512f JH	347	best->dest->rbi->visited = 1;
5c856b23 JH	348	}
5c856b23 JH	349	else
6a87d634	350	for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
5c856b23	351	{
bc35512f	352	if (!bb->rbi->visited)
5c856b23	353	{
bc35512f JH	354	end->rbi->next = bb;
bc35512f JH	355	bb->rbi->visited = 1;
5c856b23 JH	356	break;
	357	}
	358	}
	359	}
	360	}
	361
35b6b437 RS	362	/* Main entry point to this file. FLAGS is the set of flags to pass
35b6b437 RS	363	to cfg_layout_initialize(). */
5c856b23 JH	364
5c856b23 JH	365	void
35b6b437	366	tracer (unsigned int flags)
5c856b23 JH	367	{
	368	if (n_basic_blocks <= 1)
	369	return;
38700cee SB	370
	371	timevar_push (TV_TRACER);
	372
35b6b437	373	cfg_layout_initialize (flags);
5c856b23	374	mark_dfs_back_edges ();
c263766c RH	375	if (dump_file)
c263766c RH	376	dump_flow_info (dump_file);
5c856b23 JH	377	tail_duplicate ();
5c856b23 JH	378	layout_superblocks ();
c263766c RH	379	if (dump_file)
c263766c RH	380	dump_flow_info (dump_file);
5c856b23	381	cfg_layout_finalize ();
38700cee	382
5c856b23 JH	383	/* Merge basic blocks in duplicated traces. */
5c856b23 JH	384	cleanup_cfg (CLEANUP_EXPENSIVE);
38700cee SB	385
38700cee SB	386	timevar_pop (TV_TRACER);
5c856b23	387	}