/* The tracer pass for the GNU compiler.
Contributed by Jan Hubicka, SuSE Labs.
- Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
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. */
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA. */
/* This pass performs the tail duplication needed for superblock formation.
For more information see:
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "cfglayout.h"
#include "fibheap.h"
#include "flags.h"
+#include "timevar.h"
#include "params.h"
-#include "profile.h"
-
-static int count_insns PARAMS ((basic_block));
-static bool ignore_bb_p PARAMS ((basic_block));
-static bool better_p PARAMS ((edge, edge));
-static edge find_best_successor PARAMS ((basic_block));
-static edge find_best_predecessor PARAMS ((basic_block));
-static int find_trace PARAMS ((basic_block, basic_block *));
-static void tail_duplicate PARAMS ((void));
-static void layout_superblocks PARAMS ((void));
-static bool ignore_bb_p PARAMS ((basic_block));
+#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;
/* Return true if BB has been seen - it is connected to some trace
already. */
-#define seen(bb) (RBI (bb)->visited || RBI (bb)->next)
+#define seen(bb) (bb->il.rtl->visited || bb->aux)
-/* Return true if we should ignore the basic block for purposes of tracing. */
+/* Return true if we should ignore the basic block for purposes of tracing. */
static bool
-ignore_bb_p (bb)
- basic_block bb;
+ignore_bb_p (basic_block bb)
{
- if (bb->index < 0)
+ if (bb->index < NUM_FIXED_BLOCKS)
return true;
if (!maybe_hot_bb_p (bb))
return true;
/* Return number of instructions in the block. */
static int
-count_insns (bb)
- basic_block bb;
+count_insns (basic_block bb)
{
rtx insn;
int n = 0;
- for (insn = bb->head; insn != NEXT_INSN (bb->end); insn = NEXT_INSN (insn))
+ 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 (e1, e2)
- edge e1, e2;
+better_p (edge e1, edge e2)
{
if (e1->count != e2->count)
return e1->count > e2->count;
/* Return most frequent successor of basic block BB. */
static edge
-find_best_successor (bb)
- basic_block bb;
+find_best_successor (basic_block bb)
{
edge e;
edge best = NULL;
+ edge_iterator ei;
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (!best || better_p (e, best))
best = e;
if (!best || ignore_bb_p (best->dest))
/* Return most frequent predecessor of basic block BB. */
static edge
-find_best_predecessor (bb)
- basic_block bb;
+find_best_predecessor (basic_block bb)
{
edge e;
edge best = NULL;
+ edge_iterator ei;
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
if (!best || better_p (e, best))
best = e;
if (!best || ignore_bb_p (best->src))
Return number of basic blocks recorded. */
static int
-find_trace (bb, trace)
- basic_block bb;
- basic_block *trace;
+find_trace (basic_block bb, basic_block *trace)
{
int i = 0;
edge e;
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
+ if (dump_file)
+ fprintf (dump_file, "Trace seed %i [%i]", bb->index, bb->frequency);
while ((e = find_best_predecessor (bb)) != NULL)
{
if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
|| find_best_successor (bb2) != e)
break;
- if (rtl_dump_file)
- fprintf (rtl_dump_file, ",%i [%i]", bb->index, bb->frequency);
+ if (dump_file)
+ fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
bb = bb2;
}
- if (rtl_dump_file)
- fprintf (rtl_dump_file, " forward %i [%i]", bb->index, bb->frequency);
+ if (dump_file)
+ fprintf (dump_file, " forward %i [%i]", bb->index, bb->frequency);
trace[i++] = bb;
/* Follow the trace in forward direction. */
if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
|| find_best_predecessor (bb) != e)
break;
- if (rtl_dump_file)
- fprintf (rtl_dump_file, ",%i [%i]", bb->index, bb->frequency);
+ if (dump_file)
+ fprintf (dump_file, ",%i [%i]", bb->index, bb->frequency);
trace[i++] = bb;
}
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "\n");
+ if (dump_file)
+ fprintf (dump_file, "\n");
return i;
}
if profitable. */
static void
-tail_duplicate ()
+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);
+ 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 ();
int max_dup_insns;
basic_block bb;
- if (profile_info.count_profiles_merged && flag_branch_probabilities)
+ if (profile_info && flag_branch_probabilities)
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
else
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
weighted_insns += n * bb->frequency;
}
- if (profile_info.count_profiles_merged && flag_branch_probabilities)
+ if (profile_info && flag_branch_probabilities)
cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE_FEEDBACK);
else
cover_insns = PARAM_VALUE (TRACER_DYNAMIC_COVERAGE);
if (ignore_bb_p (bb))
continue;
- if (seen (bb))
- abort ();
+ gcc_assert (!seen (bb));
n = find_trace (bb, trace);
blocks[bb2->index] = NULL;
}
traced_insns += bb2->frequency * counts [bb2->index];
- if (bb2->pred && bb2->pred->pred_next
- && cfg_layout_can_duplicate_bb_p (bb2))
+ if (EDGE_COUNT (bb2->preds) > 1
+ && can_duplicate_block_p (bb2))
{
- edge e = bb2->pred;
+ edge e;
basic_block old = bb2;
- while (e->src != bb)
- e = e->pred_next;
+ e = find_edge (bb, bb2);
+
nduplicated += counts [bb2->index];
- bb2 = cfg_layout_duplicate_bb (bb2, e);
+ bb2 = duplicate_block (bb2, e, bb);
/* Reconsider the original copy of block we've duplicated.
- Removing the most common predecesor may make it to be
+ Removing the most common predecessor may make it to be
head. */
blocks[old->index] =
fibheap_insert (heap, -old->frequency, old);
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Duplicated %i as %i [%i]\n",
+ if (dump_file)
+ fprintf (dump_file, "Duplicated %i as %i [%i]\n",
old->index, bb2->index, bb2->frequency);
}
- RBI (bb)->next = bb2;
- RBI (bb2)->visited = 1;
+ 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 (rtl_dump_file)
- fprintf (rtl_dump_file, " covered now %.1f\n\n",
+ if (dump_file)
+ fprintf (dump_file, " covered now %.1f\n\n",
traced_insns * 100.0 / weighted_insns);
}
- if (rtl_dump_file)
- fprintf (rtl_dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
+ if (dump_file)
+ fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated,
nduplicated * 100 / ninsns);
free (blocks);
fibheap_delete (heap);
}
-/* Connect the superblocks into linear seuqence. At the moment we attempt to keep
+/* 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 ()
+layout_superblocks (void)
{
- basic_block end = ENTRY_BLOCK_PTR->succ->dest;
- basic_block bb = ENTRY_BLOCK_PTR->succ->dest->next_bb;
+ 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 (RBI (end)->next)
- end = RBI (end)->next;
+ while (end->aux)
+ end = end->aux;
- for (e = end->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, end->succs)
if (e->dest != EXIT_BLOCK_PTR
- && e->dest != ENTRY_BLOCK_PTR->succ->dest
- && !RBI (e->dest)->visited
+ && e->dest != single_succ (ENTRY_BLOCK_PTR)
+ && !e->dest->il.rtl->visited
&& (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best)))
best = e;
if (best)
{
- RBI (end)->next = best->dest;
- RBI (best->dest)->visited = 1;
+ end->aux = best->dest;
+ best->dest->il.rtl->visited = 1;
}
else
- for (; bb != EXIT_BLOCK_PTR; bb=bb->next_bb)
+ for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb)
{
- if (!RBI (bb)->visited)
+ if (!bb->il.rtl->visited)
{
- RBI (end)->next = bb;
- RBI (bb)->visited = 1;
+ end->aux = bb;
+ bb->il.rtl->visited = 1;
break;
}
}
/* Main entry point to this file. */
void
-tracer ()
+tracer (void)
{
- if (n_basic_blocks <= 1)
+ gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
+
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
- cfg_layout_initialize ();
+
mark_dfs_back_edges ();
- if (rtl_dump_file)
- dump_flow_info (rtl_dump_file);
+ if (dump_file)
+ dump_flow_info (dump_file, dump_flags);
tail_duplicate ();
layout_superblocks ();
- if (rtl_dump_file)
- dump_flow_info (rtl_dump_file);
- cfg_layout_finalize ();
+ 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 (CLEANUP_EXPENSIVE);
}
+\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 ();
+ reg_scan (get_insns (), max_reg_num ());
+ 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 */
+};
+