/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007
+ Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008
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)
+ 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
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, 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with GCC; see the file COPYING3. If not see
+ <http://www.gnu.org/licenses/>. */
/* This (greedy) algorithm constructs traces in several rounds.
The construction starts from "seeds". The seed for the first round
#include "params.h"
#include "toplev.h"
#include "tree-pass.h"
-
-#ifndef HAVE_conditional_execution
-#define HAVE_conditional_execution 0
-#endif
+#include "df.h"
/* The number of rounds. In most cases there will only be 4 rounds, but
when partitioning hot and cold basic blocks into separate sections of
int, fibheap_t *, int);
static basic_block copy_bb (basic_block, edge, basic_block, int);
static fibheapkey_t bb_to_key (basic_block);
-static bool better_edge_p (basic_block, edge, int, int, int, int, edge);
+static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge);
static void connect_traces (int, struct trace *);
-static bool copy_bb_p (basic_block, int);
+static bool copy_bb_p (const_basic_block, int);
static int get_uncond_jump_length (void);
-static bool push_to_next_round_p (basic_block, int, int, int, gcov_type);
-static void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
+static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
+static void find_rarely_executed_basic_blocks_and_crossing_edges (edge **,
int *,
int *);
static void add_labels_and_missing_jumps (edge *, int);
current round of trace collection. */
static bool
-push_to_next_round_p (basic_block bb, int round, int number_of_rounds,
+push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
int exec_th, gcov_type count_th)
{
bool there_exists_another_round;
basic_block bb;
fprintf (dump_file, "Trace %d (round %d): ", i + 1,
traces[i].round + 1);
- for (bb = traces[i].first; bb != traces[i].last; bb = bb->aux)
+ for (bb = traces[i].first; bb != traces[i].last; bb = (basic_block) bb->aux)
fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
}
}
}
}
- bb = bb->aux;
+ bb = (basic_block) bb->aux;
}
while (bb != back_edge->dest);
the trace. */
if (back_edge->dest == trace->first)
{
- trace->first = best_bb->aux;
+ trace->first = (basic_block) best_bb->aux;
}
else
{
for (prev_bb = trace->first;
prev_bb->aux != back_edge->dest;
- prev_bb = prev_bb->aux)
+ prev_bb = (basic_block) prev_bb->aux)
;
prev_bb->aux = best_bb->aux;
fibheapkey_t key;
edge_iterator ei;
- bb = fibheap_extract_min (*heap);
+ bb = (basic_block) fibheap_extract_min (*heap);
bbd[bb->index].heap = NULL;
bbd[bb->index].node = NULL;
/* The loop has less than 4 iterations. */
if (single_succ_p (bb)
- && copy_bb_p (best_edge->dest, !optimize_size))
+ && copy_bb_p (best_edge->dest,
+ optimize_edge_for_speed_p (best_edge)))
{
bb = copy_bb (best_edge->dest, best_edge, bb,
*n_traces);
new_size = MAX (last_basic_block, new_bb->index + 1);
new_size = GET_ARRAY_SIZE (new_size);
- bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
+ bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
for (i = array_size; i < new_size; i++)
{
bbd[i].start_of_trace = -1;
BEST_PROB; similarly for frequency. */
static bool
-better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
- int best_freq, edge cur_best_edge)
+better_edge_p (const_basic_block bb, const_edge e, int prob, int freq, int best_prob,
+ int best_freq, const_edge cur_best_edge)
{
bool is_better_edge;
edge is traversed frequently enough. */
if (try_copy
&& copy_bb_p (best->dest,
- !optimize_size
+ optimize_edge_for_speed_p (best)
&& EDGE_FREQUENCY (best) >= freq_threshold
&& best->count >= count_threshold))
{
basic_block bb;
fprintf (dump_file, "Final order:\n");
- for (bb = traces[0].first; bb; bb = bb->aux)
+ for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
fprintf (dump_file, "%d ", bb->index);
fprintf (dump_file, "\n");
fflush (dump_file);
when code size is allowed to grow by duplication. */
static bool
-copy_bb_p (basic_block bb, int code_may_grow)
+copy_bb_p (const_basic_block bb, int code_may_grow)
{
int size = 0;
int max_size = uncond_jump_length;
if (EDGE_COUNT (bb->succs) > 8)
return false;
- if (code_may_grow && maybe_hot_bb_p (bb))
+ if (code_may_grow && optimize_bb_for_speed_p (bb))
max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
FOR_BB_INSNS (bb, insn)
cache locality). */
static void
-find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
+find_rarely_executed_basic_blocks_and_crossing_edges (edge **crossing_edges,
int *n_crossing_edges,
int *max_idx)
{
basic_block bb;
- bool has_hot_blocks = false;
edge e;
int i;
edge_iterator ei;
if (probably_never_executed_bb_p (bb))
BB_SET_PARTITION (bb, BB_COLD_PARTITION);
else
- {
- BB_SET_PARTITION (bb, BB_HOT_PARTITION);
- has_hot_blocks = true;
- }
+ BB_SET_PARTITION (bb, BB_HOT_PARTITION);
}
/* Mark every edge that crosses between sections. */
if (i == *max_idx)
{
*max_idx *= 2;
- crossing_edges = xrealloc (crossing_edges,
- (*max_idx) * sizeof (edge));
+ *crossing_edges = XRESIZEVEC (edge, *crossing_edges, *max_idx);
}
- crossing_edges[i++] = e;
+ (*crossing_edges)[i++] = e;
}
else
e->flags &= ~EDGE_CROSSING;
{
label = block_label (dest);
- /* Make sure source block ends with a jump. */
+ /* Make sure source block ends with a jump. If the
+ source block does not end with a jump it might end
+ with a call_insn; this case will be handled in
+ fix_up_fall_thru_edges function. */
if (src && (src != ENTRY_BLOCK_PTR))
{
- if (!JUMP_P (BB_END (src)))
+ if (!JUMP_P (BB_END (src)) && !block_ends_with_call_p (src))
/* bb just falls through. */
{
/* make sure there's only one successor */
}
/* Find any bb's where the fall-through edge is a crossing edge (note that
- these bb's must also contain a conditional jump; we've already
- dealt with fall-through edges for blocks that didn't have a
- conditional jump in the call to add_labels_and_missing_jumps).
- Convert the fall-through edge to non-crossing edge by inserting a
- new bb to fall-through into. The new bb will contain an
- unconditional jump (crossing edge) to the original fall through
- destination. */
+ these bb's must also contain a conditional jump or end with a call
+ instruction; we've already dealt with fall-through edges for blocks
+ that didn't have a conditional jump or didn't end with call instruction
+ in the call to add_labels_and_missing_jumps). Convert the fall-through
+ edge to non-crossing edge by inserting a new bb to fall-through into.
+ The new bb will contain an unconditional jump (crossing edge) to the
+ original fall through destination. */
static void
fix_up_fall_thru_edges (void)
fall_thru = succ2;
cond_jump = succ1;
}
+ else if (!fall_thru && succ1 && block_ends_with_call_p (cur_bb))
+ {
+ edge e;
+ edge_iterator ei;
+
+ /* Find EDGE_CAN_FALLTHRU edge. */
+ FOR_EACH_EDGE (e, ei, cur_bb->succs)
+ if (e->flags & EDGE_CAN_FALLTHRU)
+ {
+ fall_thru = e;
+ break;
+ }
+ }
if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
{
fall_thru_label = block_label (fall_thru->dest);
- if (old_jump && fall_thru_label)
+ if (old_jump && JUMP_P (old_jump) && fall_thru_label)
invert_worked = invert_jump (old_jump,
fall_thru_label,0);
if (invert_worked)
/* This is the case where both edges out of the basic
block are crossing edges. Here we will fix up the
fall through edge. The jump edge will be taken care
- of later. */
-
+ of later. The EDGE_CROSSING flag of fall_thru edge
+ is unset before the call to force_nonfallthru
+ function because if a new basic-block is created
+ this edge remains in the current section boundary
+ while the edge between new_bb and the fall_thru->dest
+ becomes EDGE_CROSSING. */
+
+ fall_thru->flags &= ~EDGE_CROSSING;
new_bb = force_nonfallthru (fall_thru);
if (new_bb)
BB_COPY_PARTITION (new_bb, cur_bb);
single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
}
+ else
+ {
+ /* If a new basic-block was not created; restore
+ the EDGE_CROSSING flag. */
+ fall_thru->flags |= EDGE_CROSSING;
+ }
/* Add barrier after new jump */
}
}
-/* This function checks the destination blockof a "crossing jump" to
+/* This function checks the destination block of a "crossing jump" to
see if it has any crossing predecessors that begin with a code label
and end with an unconditional jump. If so, it returns that predecessor
block. (This is to avoid creating lots of new basic blocks that all
basic_block new_bb;
basic_block last_bb;
basic_block dest;
- basic_block prev_bb;
edge succ1;
edge succ2;
edge crossing_edge;
new_bb = create_basic_block (NULL, NULL, last_bb);
new_bb->aux = last_bb->aux;
last_bb->aux = new_bb;
- prev_bb = last_bb;
last_bb = new_bb;
-
- /* Update register liveness information. */
-
- new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
- new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
- prev_bb->il.rtl->global_live_at_end);
- COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
- prev_bb->il.rtl->global_live_at_end);
-
/* Put appropriate instructions in new bb. */
new_label = gen_label_rtx ();
FOR_EACH_EDGE (e, ei, bb->succs)
if ((e->flags & EDGE_CROSSING)
&& JUMP_P (BB_END (e->src)))
- REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
- NULL_RTX,
- REG_NOTES (BB_END
- (e->src)));
+ add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
}
/* Hot and cold basic blocks are partitioned and put in separate
well. */
if (!HAS_LONG_UNCOND_BRANCH)
- {
- fix_crossing_unconditional_branches ();
- reg_scan (get_insns (), max_reg_num ());
- }
+ fix_crossing_unconditional_branches ();
add_reg_crossing_jump_notes ();
}
the set of flags to pass to cfg_layout_initialize(). */
void
-reorder_basic_blocks (unsigned int flags)
+reorder_basic_blocks (void)
{
int n_traces;
int i;
struct trace *traces;
- if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
- return;
+ gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
- if (targetm.cannot_modify_jumps_p ())
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
- cfg_layout_initialize (flags);
-
set_edge_can_fallthru_flag ();
mark_dfs_back_edges ();
FREE (traces);
FREE (bbd);
+ relink_block_chain (/*stay_in_cfglayout_mode=*/true);
+
if (dump_file)
dump_flow_info (dump_file, dump_flags);
- cfg_layout_finalize ();
if (flag_reorder_blocks_and_partition)
verify_hot_cold_block_grouping ();
}
{
new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
BB_HEAD (bb));
+ /* ??? This kind of note always lives between basic blocks,
+ but add_insn_before will set BLOCK_FOR_INSN anyway. */
+ BLOCK_FOR_INSN (new_note) = NULL;
break;
}
}
static bool
gate_duplicate_computed_gotos (void)
{
- return (optimize > 0 && flag_expensive_optimizations && !optimize_size);
+ if (targetm.cannot_modify_jumps_p ())
+ return false;
+ return (optimize > 0 && flag_expensive_optimizations);
}
if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return 0;
- if (targetm.cannot_modify_jumps_p ())
- return 0;
-
cfg_layout_initialize (0);
/* We are estimating the length of uncond jump insn only once
|| single_pred_p (single_succ (bb)))
continue;
+ if (!optimize_bb_for_size_p (bb))
+ continue;
+
/* The successor block has to be a duplication candidate. */
if (!bitmap_bit_p (candidates, single_succ (bb)->index))
continue;
return 0;
}
-struct tree_opt_pass pass_duplicate_computed_gotos =
+struct rtl_opt_pass pass_duplicate_computed_gotos =
{
+ {
+ RTL_PASS,
"compgotos", /* name */
gate_duplicate_computed_gotos, /* gate */
duplicate_computed_gotos, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
- 0 /* letter */
+ TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
+ }
};
static void
partition_hot_cold_basic_blocks (void)
{
- basic_block cur_bb;
edge *crossing_edges;
int n_crossing_edges;
int max_edges = 2 * last_basic_block;
crossing_edges = XCNEWVEC (edge, max_edges);
- cfg_layout_initialize (0);
-
- FOR_EACH_BB (cur_bb)
- if (cur_bb->index >= NUM_FIXED_BLOCKS
- && cur_bb->next_bb->index >= NUM_FIXED_BLOCKS)
- cur_bb->aux = cur_bb->next_bb;
-
- find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
+ find_rarely_executed_basic_blocks_and_crossing_edges (&crossing_edges,
&n_crossing_edges,
&max_edges);
fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
free (crossing_edges);
-
- cfg_layout_finalize ();
}
\f
static bool
gate_handle_reorder_blocks (void)
{
+ if (targetm.cannot_modify_jumps_p ())
+ return false;
return (optimize > 0);
}
static unsigned int
rest_of_handle_reorder_blocks (void)
{
- bool changed;
- unsigned int liveness_flags;
+ basic_block bb;
/* Last attempt to optimize CFG, as scheduling, peepholing and insn
splitting possibly introduced more crossjumping opportunities. */
- liveness_flags = (!HAVE_conditional_execution ? CLEANUP_UPDATE_LIFE : 0);
- changed = cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags);
+ cfg_layout_initialize (CLEANUP_EXPENSIVE);
- if (flag_sched2_use_traces && flag_schedule_insns_after_reload)
+ if ((flag_reorder_blocks || flag_reorder_blocks_and_partition)
+ /* Don't reorder blocks when optimizing for size because extra jump insns may
+ be created; also barrier may create extra padding.
+
+ More correctly we should have a block reordering mode that tried to
+ minimize the combined size of all the jumps. This would more or less
+ automatically remove extra jumps, but would also try to use more short
+ jumps instead of long jumps. */
+ && optimize_function_for_speed_p (cfun))
{
- timevar_push (TV_TRACER);
- tracer (liveness_flags);
- timevar_pop (TV_TRACER);
+ reorder_basic_blocks ();
+ cleanup_cfg (CLEANUP_EXPENSIVE);
}
- if (flag_reorder_blocks || flag_reorder_blocks_and_partition)
- reorder_basic_blocks (liveness_flags);
- if (flag_reorder_blocks || flag_reorder_blocks_and_partition
- || (flag_sched2_use_traces && flag_schedule_insns_after_reload))
- changed |= cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags);
-
- /* On conditional execution targets we can not update the life cheaply, so
- we deffer the updating to after both cleanups. This may lose some cases
- but should not be terribly bad. */
- if (changed && HAVE_conditional_execution)
- update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
- PROP_DEATH_NOTES);
+ FOR_EACH_BB (bb)
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ bb->aux = bb->next_bb;
+ cfg_layout_finalize ();
/* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
insert_section_boundary_note ();
return 0;
}
-struct tree_opt_pass pass_reorder_blocks =
+struct rtl_opt_pass pass_reorder_blocks =
{
+ {
+ RTL_PASS,
"bbro", /* name */
gate_handle_reorder_blocks, /* gate */
rest_of_handle_reorder_blocks, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
- 'B' /* letter */
+ TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
+ }
};
static bool
static unsigned int
rest_of_handle_partition_blocks (void)
{
- no_new_pseudos = 0;
partition_hot_cold_basic_blocks ();
- allocate_reg_life_data ();
- update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
- PROP_LOG_LINKS | PROP_REG_INFO | PROP_DEATH_NOTES);
- no_new_pseudos = 1;
return 0;
}
-struct tree_opt_pass pass_partition_blocks =
+struct rtl_opt_pass pass_partition_blocks =
{
+ {
+ RTL_PASS,
"bbpart", /* name */
gate_handle_partition_blocks, /* gate */
rest_of_handle_partition_blocks, /* execute */
NULL, /* next */
0, /* static_pass_number */
TV_REORDER_BLOCKS, /* tv_id */
- 0, /* properties_required */
+ PROP_cfglayout, /* properties_required */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- TODO_dump_func, /* todo_flags_finish */
- 0 /* letter */
+ TODO_dump_func | TODO_verify_rtl_sharing/* todo_flags_finish */
+ }
};
-
-
OSDN Git Service
