/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007
+ 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 (greedy) algorithm constructs traces in several rounds.
The construction starts from "seeds". The seed for the first round
#include "expr.h"
#include "params.h"
#include "toplev.h"
+#include "tree-pass.h"
+
+#ifndef HAVE_conditional_execution
+#define HAVE_conditional_execution 0
+#endif
/* 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
#define N_ROUNDS 5
/* Stubs in case we don't have a return insn.
- We have to check at runtime too, not only compiletime. */
+ We have to check at runtime too, not only compiletime. */
#ifndef HAVE_return
#define HAVE_return 0
static bool copy_bb_p (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 void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
int *,
int *);
static void add_labels_and_missing_jumps (edge *, int);
there_exists_another_round = round < number_of_rounds - 1;
- block_not_hot_enough = (bb->frequency < exec_th
+ block_not_hot_enough = (bb->frequency < exec_th
|| bb->count < count_th
|| probably_never_executed_bb_p (bb));
if (there_exists_another_round
&& block_not_hot_enough)
return true;
- else
+ else
return false;
}
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->rbi->next)
+ for (bb = traces[i].first; bb != traces[i].last; bb = bb->aux)
fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
}
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR
- && e->dest->rbi->visited != trace_n
+ && e->dest->il.rtl->visited != trace_n
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX))
{
if (is_preferred)
{
/* The best edge is preferred. */
- if (!e->dest->rbi->visited
+ if (!e->dest->il.rtl->visited
|| bbd[e->dest->index].start_of_trace >= 0)
{
/* The current edge E is also preferred. */
}
else
{
- if (!e->dest->rbi->visited
+ if (!e->dest->il.rtl->visited
|| bbd[e->dest->index].start_of_trace >= 0)
{
/* The current edge E is preferred. */
}
}
}
- bb = bb->rbi->next;
+ bb = bb->aux;
}
while (bb != back_edge->dest);
the trace. */
if (back_edge->dest == trace->first)
{
- trace->first = best_bb->rbi->next;
+ trace->first = best_bb->aux;
}
else
{
basic_block prev_bb;
for (prev_bb = trace->first;
- prev_bb->rbi->next != back_edge->dest;
- prev_bb = prev_bb->rbi->next)
+ prev_bb->aux != back_edge->dest;
+ prev_bb = prev_bb->aux)
;
- prev_bb->rbi->next = best_bb->rbi->next;
+ prev_bb->aux = best_bb->aux;
/* Try to get rid of uncond jump to cond jump. */
if (single_succ_p (prev_bb))
/* Duplicate HEADER if it is a small block containing cond jump
in the end. */
if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
- && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
+ && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
NULL_RTX))
copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
}
/* We have not found suitable loop tail so do no rotation. */
best_bb = back_edge->src;
}
- best_bb->rbi->next = NULL;
+ best_bb->aux = NULL;
return best_bb;
}
static void
mark_bb_visited (basic_block bb, int trace)
{
- bb->rbi->visited = trace;
+ bb->il.rtl->visited = trace;
if (bbd[bb->index].heap)
{
fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
fprintf (dump_file, "Getting bb %d\n", bb->index);
/* If the BB's frequency is too low send BB to the next round. When
- partitioning hot/cold blocks into separate sections, make sure all
- the cold blocks (and ONLY the cold blocks) go into the (extra) final
- round. */
+ partitioning hot/cold blocks into separate sections, make sure all
+ the cold blocks (and ONLY the cold blocks) go into the (extra) final
+ round. */
- if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
+ if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
count_th))
{
int key = bb_to_key (bb);
fprintf (dump_file, "Basic block %d was visited in trace %d\n",
bb->index, *n_traces - 1);
- ends_in_call = block_ends_with_call_p (bb);
+ ends_in_call = block_ends_with_call_p (bb);
/* Select the successor that will be placed after BB. */
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest == EXIT_BLOCK_PTR)
continue;
- if (e->dest->rbi->visited
- && e->dest->rbi->visited != *n_traces)
+ if (e->dest->il.rtl->visited
+ && e->dest->il.rtl->visited != *n_traces)
continue;
if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
continue;
prob = e->probability;
- freq = EDGE_FREQUENCY (e);
+ freq = e->dest->frequency;
/* The only sensible preference for a call instruction is the
fallthru edge. Don't bother selecting anything else. */
/* Edge that cannot be fallthru or improbable or infrequent
successor (i.e. it is unsuitable successor). */
if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
- || prob < branch_th || freq < exec_th || e->count < count_th)
+ || prob < branch_th || EDGE_FREQUENCY (e) < exec_th
+ || e->count < count_th)
continue;
/* If partitioning hot/cold basic blocks, don't consider edges
{
if (e == best_edge
|| e->dest == EXIT_BLOCK_PTR
- || e->dest->rbi->visited)
+ || e->dest->il.rtl->visited)
continue;
key = bb_to_key (e->dest);
the cold blocks (and only the cold blocks) all get
pushed to the last round of trace collection. */
- if (push_to_next_round_p (e->dest, round,
+ if (push_to_next_round_p (e->dest, round,
number_of_rounds,
exec_th, count_th))
which_heap = new_heap;
if (best_edge) /* Suitable successor was found. */
{
- if (best_edge->dest->rbi->visited == *n_traces)
+ if (best_edge->dest->il.rtl->visited == *n_traces)
{
/* We do nothing with one basic block loops. */
if (best_edge->dest != bb)
"Rotating loop %d - %d\n",
best_edge->dest->index, bb->index);
}
- bb->rbi->next = best_edge->dest;
- bbd[best_edge->dest->index].in_trace =
- (*n_traces) - 1;
+ bb->aux = best_edge->dest;
+ bbd[best_edge->dest->index].in_trace =
+ (*n_traces) - 1;
bb = rotate_loop (best_edge, trace, *n_traces);
}
}
if (e != best_edge
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
- && !e->dest->rbi->visited
+ && !e->dest->il.rtl->visited
&& single_pred_p (e->dest)
&& !(e->flags & EDGE_CROSSING)
&& single_succ_p (e->dest)
break;
}
- bb->rbi->next = best_edge->dest;
+ bb->aux = best_edge->dest;
bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
bb = best_edge->dest;
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest == EXIT_BLOCK_PTR
- || e->dest->rbi->visited)
+ || e->dest->il.rtl->visited)
continue;
if (bbd[e->dest->index].heap)
{
basic_block new_bb;
- new_bb = duplicate_block (old_bb, e);
+ new_bb = duplicate_block (old_bb, e, bb);
BB_COPY_PARTITION (new_bb, old_bb);
gcc_assert (e->dest == new_bb);
- gcc_assert (!e->dest->rbi->visited);
+ gcc_assert (!e->dest->il.rtl->visited);
if (dump_file)
fprintf (dump_file,
"Duplicated bb %d (created bb %d)\n",
old_bb->index, new_bb->index);
- new_bb->rbi->visited = trace;
- new_bb->rbi->next = bb->rbi->next;
- bb->rbi->next = new_bb;
+ new_bb->il.rtl->visited = trace;
+ new_bb->aux = bb->aux;
+ bb->aux = new_bb;
if (new_bb->index >= array_size || last_basic_block > array_size)
{
non-crossing edges over crossing edges. */
if (!is_better_edge
- && flag_reorder_blocks_and_partition
- && cur_best_edge
+ && flag_reorder_blocks_and_partition
+ && cur_best_edge
&& (cur_best_edge->flags & EDGE_CROSSING)
&& !(e->flags & EDGE_CROSSING))
is_better_edge = true;
else
count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
- connected = xcalloc (n_traces, sizeof (bool));
+ connected = XCNEWVEC (bool, n_traces);
last_trace = -1;
current_pass = 1;
current_partition = BB_PARTITION (traces[0].first);
if (flag_reorder_blocks_and_partition)
for (i = 0; i < n_traces && !two_passes; i++)
- if (BB_PARTITION (traces[0].first)
+ if (BB_PARTITION (traces[0].first)
!= BB_PARTITION (traces[i].first))
two_passes = true;
else
current_partition = BB_HOT_PARTITION;
}
-
+
if (connected[t])
continue;
- if (two_passes
+ if (two_passes
&& BB_PARTITION (traces[t].first) != current_partition)
continue;
}
if (best)
{
- best->src->rbi->next = best->dest;
+ best->src->aux = best->dest;
t2 = bbd[best->src->index].end_of_trace;
connected[t2] = true;
}
if (last_trace >= 0)
- traces[last_trace].last->rbi->next = traces[t2].first;
+ traces[last_trace].last->aux = traces[t2].first;
last_trace = t;
/* Find the successor traces. */
best->src->index, best->dest->index);
}
t = bbd[best->dest->index].start_of_trace;
- traces[last_trace].last->rbi->next = traces[t].first;
+ traces[last_trace].last->aux = traces[t].first;
connected[t] = true;
last_trace = t;
}
if (next_bb && next_bb != EXIT_BLOCK_PTR)
{
t = bbd[next_bb->index].start_of_trace;
- traces[last_trace].last->rbi->next = traces[t].first;
+ traces[last_trace].last->aux = traces[t].first;
connected[t] = true;
last_trace = t;
}
basic_block bb;
fprintf (dump_file, "Final order:\n");
- for (bb = traces[0].first; bb; bb = bb->rbi->next)
+ for (bb = traces[0].first; bb; bb = bb->aux)
fprintf (dump_file, "%d ", bb->index);
fprintf (dump_file, "\n");
fflush (dump_file);
return false;
if (code_may_grow && maybe_hot_bb_p (bb))
- max_size *= 8;
+ max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
- size += get_attr_length (insn);
+ size += get_attr_min_length (insn);
}
if (size <= max_size)
label = emit_label_before (gen_label_rtx (), get_insns ());
jump = emit_jump_insn (gen_jump (label));
- length = get_attr_length (jump);
+ length = get_attr_min_length (jump);
delete_insn (jump);
delete_insn (label);
cache locality). */
static void
-find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
- int *n_crossing_edges,
+find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
+ int *n_crossing_edges,
int *max_idx)
{
basic_block bb;
edge_iterator ei;
/* Mark which partition (hot/cold) each basic block belongs in. */
-
+
FOR_EACH_BB (bb)
{
if (probably_never_executed_bb_p (bb))
Convert any fall-through crossing edges (for blocks that do not contain
a jump) to unconditional jumps. */
-static void
+static void
add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
{
int i;
rtx label;
rtx barrier;
rtx new_jump;
-
- for (i=0; i < n_crossing_edges; i++)
+
+ for (i=0; i < n_crossing_edges; i++)
{
- if (crossing_edges[i])
- {
- src = crossing_edges[i]->src;
- dest = crossing_edges[i]->dest;
-
- /* Make sure dest has a label. */
-
- if (dest && (dest != EXIT_BLOCK_PTR))
- {
+ if (crossing_edges[i])
+ {
+ src = crossing_edges[i]->src;
+ dest = crossing_edges[i]->dest;
+
+ /* Make sure dest has a label. */
+
+ if (dest && (dest != EXIT_BLOCK_PTR))
+ {
label = block_label (dest);
-
- /* Make sure source block ends with a jump. */
-
- if (src && (src != ENTRY_BLOCK_PTR))
- {
+
+ /* Make sure source block ends with a jump. */
+
+ if (src && (src != ENTRY_BLOCK_PTR))
+ {
if (!JUMP_P (BB_END (src)))
- /* bb just falls through. */
- {
- /* make sure there's only one successor */
+ /* bb just falls through. */
+ {
+ /* make sure there's only one successor */
gcc_assert (single_succ_p (src));
-
+
/* Find label in dest block. */
label = block_label (dest);
-
- new_jump = emit_jump_insn_after (gen_jump (label),
+
+ new_jump = emit_jump_insn_after (gen_jump (label),
BB_END (src));
barrier = emit_barrier_after (new_jump);
JUMP_LABEL (new_jump) = label;
LABEL_NUSES (label) += 1;
- src->rbi->footer = unlink_insn_chain (barrier, barrier);
+ src->il.rtl->footer = unlink_insn_chain (barrier, barrier);
/* Mark edge as non-fallthru. */
crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
- } /* end: 'if (GET_CODE ... ' */
- } /* end: 'if (src && src->index...' */
- } /* end: 'if (dest && dest->index...' */
- } /* end: 'if (crossing_edges[i]...' */
+ } /* end: 'if (GET_CODE ... ' */
+ } /* end: 'if (src && src->index...' */
+ } /* end: 'if (dest && dest->index...' */
+ } /* end: 'if (crossing_edges[i]...' */
} /* end for loop */
}
unconditional jump (crossing edge) to the original fall through
destination. */
-static void
+static void
fix_up_fall_thru_edges (void)
{
basic_block cur_bb;
rtx old_jump;
rtx fall_thru_label;
rtx barrier;
-
+
FOR_EACH_BB (cur_bb)
{
fall_thru = NULL;
succ1 = NULL;
if (EDGE_COUNT (cur_bb->succs) > 1)
- succ2 = EDGE_SUCC (cur_bb, 1);
+ succ2 = EDGE_SUCC (cur_bb, 1);
else
- succ2 = NULL;
-
+ succ2 = NULL;
+
/* Find the fall-through edge. */
-
- if (succ1
- && (succ1->flags & EDGE_FALLTHRU))
- {
- fall_thru = succ1;
- cond_jump = succ2;
- }
- else if (succ2
- && (succ2->flags & EDGE_FALLTHRU))
- {
- fall_thru = succ2;
- cond_jump = succ1;
- }
-
+
+ if (succ1
+ && (succ1->flags & EDGE_FALLTHRU))
+ {
+ fall_thru = succ1;
+ cond_jump = succ2;
+ }
+ else if (succ2
+ && (succ2->flags & EDGE_FALLTHRU))
+ {
+ fall_thru = succ2;
+ cond_jump = succ1;
+ }
+
if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
- {
- /* Check to see if the fall-thru edge is a crossing edge. */
-
+ {
+ /* Check to see if the fall-thru edge is a crossing edge. */
+
if (fall_thru->flags & EDGE_CROSSING)
- {
+ {
/* The fall_thru edge crosses; now check the cond jump edge, if
- it exists. */
-
- cond_jump_crosses = true;
- invert_worked = 0;
+ it exists. */
+
+ cond_jump_crosses = true;
+ invert_worked = 0;
old_jump = BB_END (cur_bb);
-
- /* Find the jump instruction, if there is one. */
-
- if (cond_jump)
- {
+
+ /* Find the jump instruction, if there is one. */
+
+ if (cond_jump)
+ {
if (!(cond_jump->flags & EDGE_CROSSING))
- cond_jump_crosses = false;
-
- /* We know the fall-thru edge crosses; if the cond
- jump edge does NOT cross, and its destination is the
+ cond_jump_crosses = false;
+
+ /* We know the fall-thru edge crosses; if the cond
+ jump edge does NOT cross, and its destination is the
next block in the bb order, invert the jump
- (i.e. fix it so the fall thru does not cross and
- the cond jump does). */
-
+ (i.e. fix it so the fall thru does not cross and
+ the cond jump does). */
+
if (!cond_jump_crosses
- && cur_bb->rbi->next == cond_jump->dest)
- {
- /* Find label in fall_thru block. We've already added
- any missing labels, so there must be one. */
-
- fall_thru_label = block_label (fall_thru->dest);
-
- if (old_jump && fall_thru_label)
- invert_worked = invert_jump (old_jump,
- fall_thru_label,0);
- if (invert_worked)
- {
- fall_thru->flags &= ~EDGE_FALLTHRU;
- cond_jump->flags |= EDGE_FALLTHRU;
- update_br_prob_note (cur_bb);
- e = fall_thru;
- fall_thru = cond_jump;
- cond_jump = e;
+ && cur_bb->aux == cond_jump->dest)
+ {
+ /* Find label in fall_thru block. We've already added
+ any missing labels, so there must be one. */
+
+ fall_thru_label = block_label (fall_thru->dest);
+
+ if (old_jump && fall_thru_label)
+ invert_worked = invert_jump (old_jump,
+ fall_thru_label,0);
+ if (invert_worked)
+ {
+ fall_thru->flags &= ~EDGE_FALLTHRU;
+ cond_jump->flags |= EDGE_FALLTHRU;
+ update_br_prob_note (cur_bb);
+ e = fall_thru;
+ fall_thru = cond_jump;
+ cond_jump = e;
cond_jump->flags |= EDGE_CROSSING;
fall_thru->flags &= ~EDGE_CROSSING;
- }
- }
- }
-
- if (cond_jump_crosses || !invert_worked)
- {
- /* This is the case where both edges out of the basic
- block are crossing edges. Here we will fix up the
+ }
+ }
+ }
+
+ if (cond_jump_crosses || !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. */
-
- new_bb = force_nonfallthru (fall_thru);
-
- if (new_bb)
- {
- new_bb->rbi->next = cur_bb->rbi->next;
- cur_bb->rbi->next = new_bb;
-
- /* Make sure new fall-through bb is in same
+
+ new_bb = force_nonfallthru (fall_thru);
+
+ if (new_bb)
+ {
+ new_bb->aux = cur_bb->aux;
+ cur_bb->aux = new_bb;
+
+ /* Make sure new fall-through bb is in same
partition as bb it's falling through from. */
BB_COPY_PARTITION (new_bb, cur_bb);
single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
- }
-
- /* Add barrier after new jump */
-
- if (new_bb)
- {
- barrier = emit_barrier_after (BB_END (new_bb));
- new_bb->rbi->footer = unlink_insn_chain (barrier,
- barrier);
- }
- else
- {
- barrier = emit_barrier_after (BB_END (cur_bb));
- cur_bb->rbi->footer = unlink_insn_chain (barrier,
- barrier);
- }
- }
- }
- }
+ }
+
+ /* Add barrier after new jump */
+
+ if (new_bb)
+ {
+ barrier = emit_barrier_after (BB_END (new_bb));
+ new_bb->il.rtl->footer = unlink_insn_chain (barrier,
+ barrier);
+ }
+ else
+ {
+ barrier = emit_barrier_after (BB_END (cur_bb));
+ cur_bb->il.rtl->footer = unlink_insn_chain (barrier,
+ barrier);
+ }
+ }
+ }
+ }
}
}
contain unconditional jumps to the same destination). */
static basic_block
-find_jump_block (basic_block jump_dest)
-{
- basic_block source_bb = NULL;
+find_jump_block (basic_block jump_dest)
+{
+ basic_block source_bb = NULL;
edge e;
rtx insn;
edge_iterator ei;
if (e->flags & EDGE_CROSSING)
{
basic_block src = e->src;
-
+
/* Check each predecessor to see if it has a label, and contains
only one executable instruction, which is an unconditional jump.
If so, we can use it. */
-
+
if (LABEL_P (BB_HEAD (src)))
- for (insn = BB_HEAD (src);
+ for (insn = BB_HEAD (src);
!INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
insn = NEXT_INSN (insn))
{
break;
}
}
-
+
if (source_bb)
break;
}
rtx barrier;
last_bb = EXIT_BLOCK_PTR->prev_bb;
-
+
FOR_EACH_BB (cur_bb)
{
crossing_edge = NULL;
succ1 = EDGE_SUCC (cur_bb, 0);
else
succ1 = NULL;
-
+
if (EDGE_COUNT (cur_bb->succs) > 1)
succ2 = EDGE_SUCC (cur_bb, 1);
else
succ2 = NULL;
-
+
/* We already took care of fall-through edges, so only one successor
can be a crossing edge. */
-
+
if (succ1 && (succ1->flags & EDGE_CROSSING))
crossing_edge = succ1;
else if (succ2 && (succ2->flags & EDGE_CROSSING))
- crossing_edge = succ2;
-
- if (crossing_edge)
- {
+ crossing_edge = succ2;
+
+ if (crossing_edge)
+ {
old_jump = BB_END (cur_bb);
-
+
/* Check to make sure the jump instruction is a
conditional jump. */
-
+
set_src = NULL_RTX;
if (any_condjump_p (old_jump))
old_label = XEXP (set_src, 2);
else if (GET_CODE (XEXP (set_src, 2)) == PC)
old_label = XEXP (set_src, 1);
-
+
/* Check to see if new bb for jumping to that dest has
already been created; if so, use it; if not, create
a new one. */
new_bb = find_jump_block (crossing_edge->dest);
-
+
if (new_bb)
new_label = block_label (new_bb);
else
{
/* Create new basic block to be dest for
conditional jump. */
-
+
new_bb = create_basic_block (NULL, NULL, last_bb);
- new_bb->rbi->next = last_bb->rbi->next;
- last_bb->rbi->next = new_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 ();
emit_label_before (new_label, BB_HEAD (new_bb));
BB_HEAD (new_bb) = new_label;
-
+
if (GET_CODE (old_label) == LABEL_REF)
{
old_label = JUMP_LABEL (old_jump);
- new_jump = emit_jump_insn_after (gen_jump
- (old_label),
+ new_jump = emit_jump_insn_after (gen_jump
+ (old_label),
BB_END (new_bb));
}
else
{
gcc_assert (HAVE_return
&& GET_CODE (old_label) == RETURN);
- new_jump = emit_jump_insn_after (gen_return (),
+ new_jump = emit_jump_insn_after (gen_return (),
BB_END (new_bb));
}
-
+
barrier = emit_barrier_after (new_jump);
JUMP_LABEL (new_jump) = old_label;
- new_bb->rbi->footer = unlink_insn_chain (barrier,
+ new_bb->il.rtl->footer = unlink_insn_chain (barrier,
barrier);
-
+
/* Make sure new bb is in same partition as source
of conditional branch. */
BB_COPY_PARTITION (new_bb, cur_bb);
}
-
+
/* Make old jump branch to new bb. */
-
+
redirect_jump (old_jump, new_label, 0);
-
+
/* Remove crossing_edge as predecessor of 'dest'. */
-
+
dest = crossing_edge->dest;
-
+
redirect_edge_succ (crossing_edge, new_bb);
-
+
/* Make a new edge from new_bb to old dest; new edge
will be a successor for new_bb and a predecessor
for 'dest'. */
-
+
if (EDGE_COUNT (new_bb->succs) == 0)
new_edge = make_edge (new_bb, dest, 0);
else
new_edge = EDGE_SUCC (new_bb, 0);
-
+
crossing_edge->flags &= ~EDGE_CROSSING;
new_edge->flags |= EDGE_CROSSING;
}
- }
+ }
}
}
succ = EDGE_SUCC (cur_bb, 0);
/* Check to see if bb ends in a crossing (unconditional) jump. At
- this point, no crossing jumps should be conditional. */
+ this point, no crossing jumps should be conditional. */
if (JUMP_P (last_insn)
&& (succ->flags & EDGE_CROSSING))
/* We have found a "crossing" unconditional branch. Now
we must convert it to an indirect jump. First create
reference of label, as target for jump. */
-
+
label = JUMP_LABEL (last_insn);
label_addr = gen_rtx_LABEL_REF (Pmode, label);
LABEL_NUSES (label) += 1;
-
+
/* Get a register to use for the indirect jump. */
-
+
new_reg = gen_reg_rtx (Pmode);
-
+
/* Generate indirect the jump sequence. */
-
+
start_sequence ();
emit_move_insn (new_reg, label_addr);
emit_indirect_jump (new_reg);
indirect_jump_sequence = get_insns ();
end_sequence ();
-
+
/* Make sure every instruction in the new jump sequence has
its basic block set to be cur_bb. */
-
+
for (cur_insn = indirect_jump_sequence; cur_insn;
cur_insn = NEXT_INSN (cur_insn))
{
- BLOCK_FOR_INSN (cur_insn) = cur_bb;
+ if (!BARRIER_P (cur_insn))
+ BLOCK_FOR_INSN (cur_insn) = cur_bb;
if (JUMP_P (cur_insn))
jump_insn = cur_insn;
}
-
+
/* Insert the new (indirect) jump sequence immediately before
the unconditional jump, then delete the unconditional jump. */
-
+
emit_insn_before (indirect_jump_sequence, last_insn);
delete_insn (last_insn);
-
+
/* Make BB_END for cur_bb be the jump instruction (NOT the
barrier instruction at the end of the sequence...). */
-
+
BB_END (cur_bb) = jump_insn;
}
}
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
+ REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
+ NULL_RTX,
+ REG_NOTES (BB_END
(e->src)));
}
sections are converted to indirect jumps.
The code for fixing up fall_thru edges that cross between hot and
- cold basic blocks does so by creating new basic blocks containing
- unconditional branches to the appropriate label in the "other"
+ cold basic blocks does so by creating new basic blocks containing
+ unconditional branches to the appropriate label in the "other"
section. The new basic block is then put in the same (hot or cold)
section as the original conditional branch, and the fall_thru edge
is modified to fall into the new basic block instead. By adding
this level of indirection we end up with only unconditional branches
- crossing between hot and cold sections.
-
+ crossing between hot and cold sections.
+
Conditional branches are dealt with by adding a level of indirection.
- A new basic block is added in the same (hot/cold) section as the
+ A new basic block is added in the same (hot/cold) section as the
conditional branch, and the conditional branch is retargeted to the
new basic block. The new basic block contains an unconditional branch
to the original target of the conditional branch (in the other section).
Unconditional branches are dealt with by converting them into
indirect jumps. */
-static void
-fix_edges_for_rarely_executed_code (edge *crossing_edges,
+static void
+fix_edges_for_rarely_executed_code (edge *crossing_edges,
int n_crossing_edges)
{
/* Make sure the source of any crossing edge ends in a jump and the
destination of any crossing edge has a label. */
-
+
add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
-
+
/* Convert all crossing fall_thru edges to non-crossing fall
thrus to unconditional jumps (that jump to the original fall
thru dest). */
-
+
fix_up_fall_thru_edges ();
-
+
/* If the architecture does not have conditional branches that can
span all of memory, convert crossing conditional branches into
crossing unconditional branches. */
-
+
if (!HAS_LONG_COND_BRANCH)
fix_crossing_conditional_branches ();
-
+
/* If the architecture does not have unconditional branches that
can span all of memory, convert crossing unconditional branches
into indirect jumps. Since adding an indirect jump also adds
a new register usage, update the register usage information as
well. */
-
+
if (!HAS_LONG_UNCOND_BRANCH)
{
fix_crossing_unconditional_branches ();
- reg_scan (get_insns(), max_reg_num ());
+ reg_scan (get_insns (), max_reg_num ());
}
-
+
add_reg_crossing_jump_notes ();
}
int err = 0;
bool switched_sections = false;
int current_partition = 0;
-
+
FOR_EACH_BB (bb)
{
if (!current_partition)
{
if (switched_sections)
{
- error ("Multiple hot/cold transitions found (bb %i)",
+ error ("multiple hot/cold transitions found (bb %i)",
bb->index);
err = 1;
}
}
}
}
-
+
gcc_assert(!err);
}
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 <= 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;
- timevar_push (TV_REORDER_BLOCKS);
-
- cfg_layout_initialize (flags);
-
set_edge_can_fallthru_flag ();
mark_dfs_back_edges ();
/* We need to know some information for each basic block. */
array_size = GET_ARRAY_SIZE (last_basic_block);
- bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
+ bbd = XNEWVEC (bbro_basic_block_data, array_size);
for (i = 0; i < array_size; i++)
{
bbd[i].start_of_trace = -1;
bbd[i].node = NULL;
}
- traces = xmalloc (n_basic_blocks * sizeof (struct trace));
+ traces = XNEWVEC (struct trace, n_basic_blocks);
n_traces = 0;
find_traces (&n_traces, traces);
connect_traces (n_traces, traces);
FREE (traces);
FREE (bbd);
+ relink_block_chain (/*stay_in_cfglayout_mode=*/true);
+
if (dump_file)
- dump_flow_info (dump_file);
+ dump_flow_info (dump_file, dump_flags);
- cfg_layout_finalize ();
if (flag_reorder_blocks_and_partition)
verify_hot_cold_block_grouping ();
-
- timevar_pop (TV_REORDER_BLOCKS);
}
/* Determine which partition the first basic block in the function
encountering this note will make the compiler switch between the
hot and cold text sections. */
-void
+static void
insert_section_boundary_note (void)
{
basic_block bb;
rtx new_note;
int first_partition = 0;
-
+
if (flag_reorder_blocks_and_partition)
FOR_EACH_BB (bb)
{
which can seriously pessimize code with many computed jumps in the source
code, such as interpreters. See e.g. PR15242. */
-void
+static bool
+gate_duplicate_computed_gotos (void)
+{
+ if (targetm.cannot_modify_jumps_p ())
+ return false;
+ return (optimize > 0 && flag_expensive_optimizations && !optimize_size);
+}
+
+
+static unsigned int
duplicate_computed_gotos (void)
{
basic_block bb, new_bb;
bitmap candidates;
int max_size;
- if (n_basic_blocks <= 1)
- return;
-
- if (targetm.cannot_modify_jumps_p ())
- return;
-
- timevar_push (TV_REORDER_BLOCKS);
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
+ return 0;
cfg_layout_initialize (0);
/* Build the reorder chain for the original order of blocks. */
if (bb->next_bb != EXIT_BLOCK_PTR)
- bb->rbi->next = bb->next_bb;
+ bb->aux = bb->next_bb;
/* Obviously the block has to end in a computed jump. */
if (!computed_jump_p (BB_END (bb)))
FOR_BB_INSNS (bb, insn)
if (INSN_P (insn))
{
- size += get_attr_length (insn);
+ size += get_attr_min_length (insn);
if (size > max_size)
break;
}
/* Duplicate computed gotos. */
FOR_EACH_BB (bb)
{
- if (bb->rbi->visited)
+ if (bb->il.rtl->visited)
continue;
- bb->rbi->visited = 1;
+ bb->il.rtl->visited = 1;
/* BB must have one outgoing edge. That edge must not lead to
- the exit block or the next block.
+ the exit block or the next block.
The destination must have more than one predecessor. */
if (!single_succ_p (bb)
|| single_succ (bb) == EXIT_BLOCK_PTR
if (!bitmap_bit_p (candidates, single_succ (bb)->index))
continue;
- new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb));
- new_bb->rbi->next = bb->rbi->next;
- bb->rbi->next = new_bb;
- new_bb->rbi->visited = 1;
+ new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
+ new_bb->aux = bb->aux;
+ bb->aux = new_bb;
+ new_bb->il.rtl->visited = 1;
}
done:
cfg_layout_finalize ();
BITMAP_FREE (candidates);
-
- timevar_pop (TV_REORDER_BLOCKS);
+ return 0;
}
+struct tree_opt_pass pass_duplicate_computed_gotos =
+{
+ "compgotos", /* name */
+ gate_duplicate_computed_gotos, /* gate */
+ duplicate_computed_gotos, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_REORDER_BLOCKS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+
/* This function is the main 'entrance' for the optimization that
partitions hot and cold basic blocks into separate sections of the
.o file (to improve performance and cache locality). Ideally it
(through registers) requires that this optimization be performed
before register allocation. */
-void
+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;
-
- if (n_basic_blocks <= 1)
+
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
-
- crossing_edges = xcalloc (max_edges, sizeof (edge));
+
+ crossing_edges = XCNEWVEC (edge, max_edges);
cfg_layout_initialize (0);
-
+
FOR_EACH_BB (cur_bb)
- if (cur_bb->index >= 0
- && cur_bb->next_bb->index >= 0)
- cur_bb->rbi->next = cur_bb->next_bb;
-
- find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
- &n_crossing_edges,
+ 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,
+ &n_crossing_edges,
&max_edges);
if (n_crossing_edges > 0)
fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
-
+
free (crossing_edges);
- cfg_layout_finalize();
+ cfg_layout_finalize ();
+}
+\f
+static bool
+gate_handle_reorder_blocks (void)
+{
+ if (targetm.cannot_modify_jumps_p ())
+ return false;
+ return (optimize > 0);
+}
+
+
+/* Reorder basic blocks. */
+static unsigned int
+rest_of_handle_reorder_blocks (void)
+{
+ 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);
+ cfg_layout_initialize (CLEANUP_EXPENSIVE | liveness_flags);
+
+ if (flag_sched2_use_traces && flag_schedule_insns_after_reload)
+ {
+ timevar_push (TV_TRACER);
+ tracer ();
+ timevar_pop (TV_TRACER);
+ }
+
+ if (flag_reorder_blocks || flag_reorder_blocks_and_partition)
+ reorder_basic_blocks ();
+ if (flag_reorder_blocks || flag_reorder_blocks_and_partition
+ || (flag_sched2_use_traces && flag_schedule_insns_after_reload))
+ 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 (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 =
+{
+ "bbro", /* name */
+ gate_handle_reorder_blocks, /* gate */
+ rest_of_handle_reorder_blocks, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_REORDER_BLOCKS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'B' /* letter */
+};
+
+static bool
+gate_handle_partition_blocks (void)
+{
+ /* The optimization to partition hot/cold basic blocks into separate
+ sections of the .o file does not work well with linkonce or with
+ user defined section attributes. Don't call it if either case
+ arises. */
+
+ return (flag_reorder_blocks_and_partition
+ && !DECL_ONE_ONLY (current_function_decl)
+ && !user_defined_section_attribute);
+}
+
+/* Partition hot and cold basic blocks. */
+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 =
+{
+ "bbpart", /* name */
+ gate_handle_partition_blocks, /* gate */
+ rest_of_handle_partition_blocks, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_REORDER_BLOCKS, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 0 /* letter */
+};
+
+
OSDN Git Service
