[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, 2005, 2006, 2007
   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 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 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"
#include "tree-pass.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->il.rtl->visited || bb->aux)

/* Return true if we should ignore the basic block for purposes of tracing.  */
static bool
ignore_bb_p (basic_block bb)
{
  if (bb->index < NUM_FIXED_BLOCKS)
    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 = XCNEWVEC (fibnode_t, last_basic_block);
  basic_block *trace = XNEWVEC (basic_block, n_basic_blocks);
  int *counts = XNEWVEC (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;
	      basic_block old = bb2;

	      e = find_edge (bb, bb2);

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

	      /* 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->aux = bb2;
	  bb2->il.rtl->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 = single_succ (ENTRY_BLOCK_PTR);
  basic_block bb = end->next_bb;

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

      FOR_EACH_EDGE (e, ei, end->succs)
	if (e->dest != EXIT_BLOCK_PTR
	    && e->dest != single_succ (ENTRY_BLOCK_PTR)
	    && !e->dest->il.rtl->visited
	    && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
	  best = e;

      if (best)
	{
	  end->aux = best->dest;
	  best->dest->il.rtl->visited = 1;
	}
      else
	for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
	  {
	    if (!bb->il.rtl->visited)
	      {
		end->aux = bb;
		bb->il.rtl->visited = 1;
		break;
	      }
	  }
    }
}

/* Main entry point to this file.  */

void
tracer (void)
{
  gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);

  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
    return;

  mark_dfs_back_edges ();
  if (dump_file)
    dump_flow_info (dump_file, dump_flags);
  tail_duplicate ();
  layout_superblocks ();
  relink_block_chain (/*stay_in_cfglayout_mode=*/true);
  
  if (dump_file)
    dump_flow_info (dump_file, dump_flags);

  /* Merge basic blocks in duplicated traces.  */
  cleanup_cfg (0);
}
\f
static bool
gate_handle_tracer (void)
{
  return (optimize > 0 && flag_tracer);
}

/* Run tracer.  */
static unsigned int
rest_of_handle_tracer (void)
{
  if (dump_file)
    dump_flow_info (dump_file, dump_flags);
  tracer ();
  return 0;
}

struct tree_opt_pass pass_tracer =
{
  "tracer",                             /* name */
  gate_handle_tracer,                   /* gate */
  rest_of_handle_tracer,                /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_TRACER,                            /* tv_id */
  0,                                    /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  0,                                    /* todo_flags_start */
  TODO_dump_func,                       /* todo_flags_finish */
  'T'                                   /* letter */
};
Commit	Line	Data
fa99ab3d	1	/* The tracer pass for the GNU compiler.
fa99ab3d	2	Contributed by Jan Hubicka, SuSE Labs.
3072d30e	3	Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
3072d30e	4	Free Software Foundation, Inc.
fa99ab3d	5
	6	This file is part of GCC.
	7
	8	GCC is free software; you can redistribute it and/or modify it
	9	under the terms of the GNU General Public License as published by
8c4c00c1	10	the Free Software Foundation; either version 3, or (at your option)
fa99ab3d	11	any later version.
	12
	13	GCC is distributed in the hope that it will be useful, but WITHOUT
	14	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
	15	or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
	16	License for more details.
	17
	18	You should have received a copy of the GNU General Public License
8c4c00c1	19	along with GCC; see the file COPYING3. If not see
8c4c00c1	20	<http://www.gnu.org/licenses/>. */
fa99ab3d	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"
805e22b2	38	#include "coretypes.h"
805e22b2	39	#include "tm.h"
fa99ab3d	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"
e7f8f0eb	48	#include "timevar.h"
fa99ab3d	49	#include "params.h"
44359ced	50	#include "coverage.h"
77fce4cd	51	#include "tree-pass.h"
fa99ab3d	52
60b8c5b3	53	static int count_insns (basic_block);
	54	static bool ignore_bb_p (basic_block);
	55	static bool better_p (edge, edge);
	56	static edge find_best_successor (basic_block);
	57	static edge find_best_predecessor (basic_block);
	58	static int find_trace (basic_block, basic_block *);
	59	static void tail_duplicate (void);
	60	static void layout_superblocks (void);
fa99ab3d	61
	62	/* Minimal outgoing edge probability considered for superblock formation. */
	63	static int probability_cutoff;
	64	static int branch_ratio_cutoff;
	65
	66	/* Return true if BB has been seen - it is connected to some trace
	67	already. */
	68
bc5f266a	69	#define seen(bb) (bb->il.rtl->visited \|\| bb->aux)
fa99ab3d	70
7299020b	71	/* Return true if we should ignore the basic block for purposes of tracing. */
fa99ab3d	72	static bool
60b8c5b3	73	ignore_bb_p (basic_block bb)
fa99ab3d	74	{
4d2e5d52	75	if (bb->index < NUM_FIXED_BLOCKS)
fa99ab3d	76	return true;
	77	if (!maybe_hot_bb_p (bb))
	78	return true;
	79	return false;
	80	}
	81
	82	/* Return number of instructions in the block. */
	83
	84	static int
60b8c5b3	85	count_insns (basic_block bb)
fa99ab3d	86	{
	87	rtx insn;
	88	int n = 0;
	89
5496dbfc	90	for (insn = BB_HEAD (bb);
	91	insn != NEXT_INSN (BB_END (bb));
	92	insn = NEXT_INSN (insn))
fa99ab3d	93	if (active_insn_p (insn))
	94	n++;
	95	return n;
	96	}
	97
	98	/* Return true if E1 is more frequent than E2. */
	99	static bool
60b8c5b3	100	better_p (edge e1, edge e2)
fa99ab3d	101	{
	102	if (e1->count != e2->count)
	103	return e1->count > e2->count;
	104	if (e1->src->frequency * e1->probability !=
	105	e2->src->frequency * e2->probability)
	106	return (e1->src->frequency * e1->probability
	107	> e2->src->frequency * e2->probability);
	108	/* This is needed to avoid changes in the decision after
	109	CFG is modified. */
	110	if (e1->src != e2->src)
	111	return e1->src->index > e2->src->index;
	112	return e1->dest->index > e2->dest->index;
	113	}
	114
	115	/* Return most frequent successor of basic block BB. */
	116
	117	static edge
60b8c5b3	118	find_best_successor (basic_block bb)
fa99ab3d	119	{
	120	edge e;
	121	edge best = NULL;
cd665a06	122	edge_iterator ei;
fa99ab3d	123
cd665a06	124	FOR_EACH_EDGE (e, ei, bb->succs)
fa99ab3d	125	if (!best \|\| better_p (e, best))
	126	best = e;
	127	if (!best \|\| ignore_bb_p (best->dest))
	128	return NULL;
	129	if (best->probability <= probability_cutoff)
	130	return NULL;
	131	return best;
	132	}
	133
	134	/* Return most frequent predecessor of basic block BB. */
	135
	136	static edge
60b8c5b3	137	find_best_predecessor (basic_block bb)
fa99ab3d	138	{
	139	edge e;
	140	edge best = NULL;
cd665a06	141	edge_iterator ei;
fa99ab3d	142
cd665a06	143	FOR_EACH_EDGE (e, ei, bb->preds)
fa99ab3d	144	if (!best \|\| better_p (e, best))
	145	best = e;
	146	if (!best \|\| ignore_bb_p (best->src))
	147	return NULL;
	148	if (EDGE_FREQUENCY (best) * REG_BR_PROB_BASE
	149	< bb->frequency * branch_ratio_cutoff)
	150	return NULL;
	151	return best;
	152	}
	153
	154	/* Find the trace using bb and record it in the TRACE array.
	155	Return number of basic blocks recorded. */
	156
	157	static int
60b8c5b3	158	find_trace (basic_block bb, basic_block *trace)
fa99ab3d	159	{
	160	int i = 0;
	161	edge e;
	162
450d042a	163	if (dump_file)
450d042a	164	fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
fa99ab3d	165
	166	while ((e = find_best_predecessor (bb)) != NULL)
	167	{
	168	basic_block bb2 = e->src;
	169	if (seen (bb2) \|\| (e->flags & (EDGE_DFS_BACK \| EDGE_COMPLEX))
	170	\|\| find_best_successor (bb2) != e)
	171	break;
450d042a	172	if (dump_file)
450d042a	173	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
fa99ab3d	174	bb = bb2;
fa99ab3d	175	}
450d042a	176	if (dump_file)
450d042a	177	fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
fa99ab3d	178	trace[i++] = bb;
	179
	180	/* Follow the trace in forward direction. */
	181	while ((e = find_best_successor (bb)) != NULL)
	182	{
	183	bb = e->dest;
	184	if (seen (bb) \|\| (e->flags & (EDGE_DFS_BACK \| EDGE_COMPLEX))
	185	\|\| find_best_predecessor (bb) != e)
	186	break;
450d042a	187	if (dump_file)
450d042a	188	fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
fa99ab3d	189	trace[i++] = bb;
fa99ab3d	190	}
450d042a	191	if (dump_file)
450d042a	192	fprintf (dump_file, "\n");
fa99ab3d	193	return i;
	194	}
	195
	196	/* Look for basic blocks in frequency order, construct traces and tail duplicate
	197	if profitable. */
	198
	199	static void
60b8c5b3	200	tail_duplicate (void)
fa99ab3d	201	{
4c36ffe6	202	fibnode_t *blocks = XCNEWVEC (fibnode_t, last_basic_block);
	203	basic_block *trace = XNEWVEC (basic_block, n_basic_blocks);
	204	int *counts = XNEWVEC (int, last_basic_block);
fa99ab3d	205	int ninsns = 0, nduplicated = 0;
	206	gcov_type weighted_insns = 0, traced_insns = 0;
	207	fibheap_t heap = fibheap_new ();
	208	gcov_type cover_insns;
	209	int max_dup_insns;
	210	basic_block bb;
	211
ab6a34f2	212	if (profile_info && flag_branch_probabilities)
fa99ab3d	213	probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
	214	else
	215	probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
	216	probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
	217
	218	branch_ratio_cutoff =
	219	(REG_BR_PROB_BASE / 100 * PARAM_VALUE (TRACER_MIN_BRANCH_RATIO));
	220
	221	FOR_EACH_BB (bb)
	222	{
	223	int n = count_insns (bb);
	224	if (!ignore_bb_p (bb))
	225	blocks[bb->index] = fibheap_insert (heap, -bb->frequency,
	226	bb);
	227
	228	counts [bb->index] = n;
	229	ninsns += n;
	230	weighted_insns += n * bb->frequency;
	231	}
	232
ab6a34f2	233	if (profile_info && flag_branch_probabilities)
fa99ab3d	234	cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
	235	else
	236	cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
	237	cover_insns = (weighted_insns * cover_insns + 50) / 100;
	238	max_dup_insns = (ninsns * PARAM_VALUE (TRACER_MAX_CODE_GROWTH) + 50) / 100;
	239
	240	while (traced_insns < cover_insns && nduplicated < max_dup_insns
	241	&& !fibheap_empty (heap))
	242	{
	243	basic_block bb = fibheap_extract_min (heap);
	244	int n, pos;
	245
	246	if (!bb)
	247	break;
	248
	249	blocks[bb->index] = NULL;
	250
	251	if (ignore_bb_p (bb))
	252	continue;
8c0963c4	253	gcc_assert (!seen (bb));
fa99ab3d	254
	255	n = find_trace (bb, trace);
	256
	257	bb = trace[0];
	258	traced_insns += bb->frequency * counts [bb->index];
	259	if (blocks[bb->index])
	260	{
	261	fibheap_delete_node (heap, blocks[bb->index]);
	262	blocks[bb->index] = NULL;
	263	}
	264
	265	for (pos = 1; pos < n; pos++)
	266	{
	267	basic_block bb2 = trace[pos];
	268
	269	if (blocks[bb2->index])
	270	{
	271	fibheap_delete_node (heap, blocks[bb2->index]);
	272	blocks[bb2->index] = NULL;
	273	}
	274	traced_insns += bb2->frequency * counts [bb2->index];
cd665a06	275	if (EDGE_COUNT (bb2->preds) > 1
4ee9c684	276	&& can_duplicate_block_p (bb2))
fa99ab3d	277	{
cd665a06	278	edge e;
fa99ab3d	279	basic_block old = bb2;
fa99ab3d	280
c6356c17	281	e = find_edge (bb, bb2);
cd665a06	282
fa99ab3d	283	nduplicated += counts [bb2->index];
c4d867e0	284	bb2 = duplicate_block (bb2, e, bb);
fa99ab3d	285
fa99ab3d	286	/* Reconsider the original copy of block we've duplicated.
de132707	287	Removing the most common predecessor may make it to be
fa99ab3d	288	head. */
	289	blocks[old->index] =
	290	fibheap_insert (heap, -old->frequency, old);
	291
450d042a	292	if (dump_file)
450d042a	293	fprintf (dump_file, "Duplicated %i as %i [%i]\n",
fa99ab3d	294	old->index, bb2->index, bb2->frequency);
fa99ab3d	295	}
bc5f266a	296	bb->aux = bb2;
bc5f266a	297	bb2->il.rtl->visited = 1;
fa99ab3d	298	bb = bb2;
	299	/* In case the trace became infrequent, stop duplicating. */
	300	if (ignore_bb_p (bb))
	301	break;
	302	}
450d042a	303	if (dump_file)
450d042a	304	fprintf (dump_file, " covered now %.1f\n\n",
fa99ab3d	305	traced_insns * 100.0 / weighted_insns);
fa99ab3d	306	}
450d042a	307	if (dump_file)
450d042a	308	fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
fa99ab3d	309	nduplicated * 100 / ninsns);
	310
	311	free (blocks);
	312	free (trace);
	313	free (counts);
	314	fibheap_delete (heap);
	315	}
	316
917bbcab	317	/* Connect the superblocks into linear sequence. At the moment we attempt to keep
fa99ab3d	318	the original order as much as possible, but the algorithm may be made smarter
	319	later if needed. BB reordering pass should void most of the benefits of such
	320	change though. */
	321
	322	static void
60b8c5b3	323	layout_superblocks (void)
fa99ab3d	324	{
ea091dfd	325	basic_block end = single_succ (ENTRY_BLOCK_PTR);
ea091dfd	326	basic_block bb = end->next_bb;
fa99ab3d	327
	328	while (bb != EXIT_BLOCK_PTR)
	329	{
cd665a06	330	edge_iterator ei;
fa99ab3d	331	edge e, best = NULL;
bc5f266a	332	while (end->aux)
bc5f266a	333	end = end->aux;
fa99ab3d	334
cd665a06	335	FOR_EACH_EDGE (e, ei, end->succs)
fa99ab3d	336	if (e->dest != EXIT_BLOCK_PTR
ea091dfd	337	&& e->dest != single_succ (ENTRY_BLOCK_PTR)
bc5f266a	338	&& !e->dest->il.rtl->visited
fa99ab3d	339	&& (!best \|\| EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
	340	best = e;
	341
	342	if (best)
	343	{
bc5f266a	344	end->aux = best->dest;
bc5f266a	345	best->dest->il.rtl->visited = 1;
fa99ab3d	346	}
fa99ab3d	347	else
ea0041f4	348	for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
fa99ab3d	349	{
bc5f266a	350	if (!bb->il.rtl->visited)
fa99ab3d	351	{
bc5f266a	352	end->aux = bb;
bc5f266a	353	bb->il.rtl->visited = 1;
fa99ab3d	354	break;
	355	}
	356	}
	357	}
	358	}
	359
207c7ab2	360	/* Main entry point to this file. */
fa99ab3d	361
fa99ab3d	362	void
207c7ab2	363	tracer (void)
fa99ab3d	364	{
207c7ab2	365	gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
207c7ab2	366
4d2e5d52	367	if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
fa99ab3d	368	return;
e7f8f0eb	369
fa99ab3d	370	mark_dfs_back_edges ();
450d042a	371	if (dump_file)
562d71e8	372	dump_flow_info (dump_file, dump_flags);
fa99ab3d	373	tail_duplicate ();
fa99ab3d	374	layout_superblocks ();
207c7ab2	375	relink_block_chain (/stay_in_cfglayout_mode=/true);
207c7ab2	376
450d042a	377	if (dump_file)
562d71e8	378	dump_flow_info (dump_file, dump_flags);
e7f8f0eb	379
fa99ab3d	380	/* Merge basic blocks in duplicated traces. */
3072d30e	381	cleanup_cfg (0);
77fce4cd	382	}
	383	\f
	384	static bool
	385	gate_handle_tracer (void)
	386	{
	387	return (optimize > 0 && flag_tracer);
	388	}
e7f8f0eb	389
77fce4cd	390	/* Run tracer. */
2a1990e9	391	static unsigned int
77fce4cd	392	rest_of_handle_tracer (void)
	393	{
	394	if (dump_file)
562d71e8	395	dump_flow_info (dump_file, dump_flags);
207c7ab2	396	tracer ();
2a1990e9	397	return 0;
fa99ab3d	398	}
77fce4cd	399
	400	struct tree_opt_pass pass_tracer =
	401	{
	402	"tracer", /* name */
	403	gate_handle_tracer, /* gate */
	404	rest_of_handle_tracer, /* execute */
	405	NULL, /* sub */
	406	NULL, /* next */
	407	0, /* static_pass_number */
	408	TV_TRACER, /* tv_id */
	409	0, /* properties_required */
	410	0, /* properties_provided */
	411	0, /* properties_destroyed */
	412	0, /* todo_flags_start */
	413	TODO_dump_func, /* todo_flags_finish */
	414	'T' /* letter */
	415	};
	416