/* 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, 2008, 2010, 2011,
+ 2012 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, 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, 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 "obstack.h"
#include "expr.h"
#include "params.h"
+#include "diagnostic-core.h"
+#include "toplev.h" /* user_defined_section_attribute */
+#include "tree-pass.h"
+#include "df.h"
+#include "bb-reorder.h"
+#include "except.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
#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
#endif
+struct target_bb_reorder default_target_bb_reorder;
+#if SWITCHABLE_TARGET
+struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
+#endif
+
+#define uncond_jump_length \
+ (this_target_bb_reorder->x_uncond_jump_length)
+
/* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
block the edge destination is not duplicated while connecting traces. */
#define DUPLICATION_THRESHOLD 100
-/* Length of unconditional jump instruction. */
-static int uncond_jump_length;
-
/* Structure to hold needed information for each basic block. */
typedef struct bbro_basic_block_data_def
{
/* Which trace is the bb end of (-1 means it is not an end of a trace). */
int end_of_trace;
+ /* Which trace is the bb in? */
+ int in_trace;
+
/* Which heap is BB in (if any)? */
fibheap_t heap;
};
/* Maximum frequency and count of one of the entry blocks. */
-int max_entry_frequency;
-gcov_type max_entry_count;
+static int max_entry_frequency;
+static gcov_type max_entry_count;
/* Local function prototypes. */
static void find_traces (int *, struct trace *);
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 int get_uncond_jump_length (void);
-static bool push_to_next_round_p (basic_block, int, int, int, gcov_type);
-static void add_unlikely_executed_notes (void);
-static void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
- int *,
- int *);
-static void mark_bb_for_unlikely_executed_section (basic_block);
-static void add_labels_and_missing_jumps (edge *, int);
-static void add_reg_crossing_jump_notes (void);
-static void fix_up_fall_thru_edges (void);
-static void fix_edges_for_rarely_executed_code (edge *, int);
-static void fix_crossing_conditional_branches (void);
-static void fix_crossing_unconditional_branches (void);
+static bool copy_bb_p (const_basic_block, int);
+static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
\f
/* Check to see if bb should be pushed into the next round of trace
collections or not. Reasons for pushing the block forward are 1).
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;
- bool cold_block;
bool block_not_hot_enough;
- bool next_round_is_last;
there_exists_another_round = round < number_of_rounds - 1;
- next_round_is_last = round + 1 == number_of_rounds - 1;
-
- cold_block = (flag_reorder_blocks_and_partition
- && BB_PARTITION (bb) == BB_COLD_PARTITION);
- 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 (flag_reorder_blocks_and_partition
- && next_round_is_last
- && BB_PARTITION (bb) != BB_COLD_PARTITION)
- return false;
- else if (there_exists_another_round
- && (cold_block || block_not_hot_enough))
+ if (there_exists_another_round
+ && block_not_hot_enough)
return true;
- else
+ else
return false;
}
cold blocks (and ONLY the cold blocks). */
number_of_rounds = N_ROUNDS - 1;
- if (flag_reorder_blocks_and_partition)
- number_of_rounds = N_ROUNDS;
/* Insert entry points of function into heap. */
heap = fibheap_new ();
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 = (basic_block) 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 = (basic_block) bb->aux;
}
while (bb != back_edge->dest);
the trace. */
if (back_edge->dest == trace->first)
{
- trace->first = best_bb->rbi->next;
+ trace->first = (basic_block) 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 = (basic_block) 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 (EDGE_COUNT (prev_bb->succs) == 1)
+ if (single_succ_p (prev_bb))
{
- basic_block header = EDGE_SUCC (prev_bb, 0)->dest;
+ basic_block header = single_succ (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, EDGE_SUCC (prev_bb, 0), prev_bb, trace_n);
- }
+ 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);
struct trace *traces, int *n_traces, int round,
fibheap_t *heap, int number_of_rounds)
{
- /* The following variable refers to the last round in which non-"cold"
- blocks may be collected into a trace. */
-
- int last_round = N_ROUNDS - 1;
-
/* Heap for discarded basic blocks which are possible starting points for
the next round. */
fibheap_t new_heap = fibheap_new ();
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;
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);
trace->first = bb;
trace->round = round;
trace->length = 0;
+ bbd[bb->index].in_trace = *n_traces;
(*n_traces)++;
do
{
int prob, freq;
+ bool ends_in_call;
/* The probability and frequency of the best edge. */
int best_prob = INT_MIN / 2;
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);
+
/* 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_COLD_PARTITION
- && round < last_round)
+ 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. */
+ if (ends_in_call)
+ {
+ if (e->flags & EDGE_CAN_FALLTHRU)
+ {
+ best_edge = e;
+ best_prob = prob;
+ best_freq = freq;
+ }
+ continue;
+ }
/* 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;
+ bb->aux = best_edge->dest;
+ bbd[best_edge->dest->index].in_trace =
+ (*n_traces) - 1;
bb = rotate_loop (best_edge, trace, *n_traces);
}
}
{
/* The loop has less than 4 iterations. */
- if (EDGE_COUNT (bb->succs) == 1
- && copy_bb_p (best_edge->dest, !optimize_size))
+ if (single_succ_p (bb)
+ && copy_bb_p (best_edge->dest,
+ optimize_edge_for_speed_p (best_edge)))
{
bb = copy_bb (best_edge->dest, best_edge, bb,
*n_traces);
+ trace->length++;
}
}
}
if (e != best_edge
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
- && !e->dest->rbi->visited
- && EDGE_COUNT (e->dest->preds) == 1
+ && !e->dest->il.rtl->visited
+ && single_pred_p (e->dest)
&& !(e->flags & EDGE_CROSSING)
- && EDGE_COUNT (e->dest->succs) == 1
- && (EDGE_SUCC (e->dest, 0)->flags & EDGE_CAN_FALLTHRU)
- && !(EDGE_SUCC (e->dest, 0)->flags & EDGE_COMPLEX)
- && EDGE_SUCC (e->dest, 0)->dest == best_edge->dest
+ && single_succ_p (e->dest)
+ && (single_succ_edge (e->dest)->flags
+ & EDGE_CAN_FALLTHRU)
+ && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
+ && single_succ (e->dest) == best_edge->dest
&& 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
{
best_edge = e;
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)
{
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;
+ bbd[i].in_trace = -1;
bbd[i].end_of_trace = -1;
bbd[i].heap = NULL;
bbd[i].node = NULL;
}
}
+ bbd[new_bb->index].in_trace = trace;
+
return new_bb;
}
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;
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;
connect_traces (int n_traces, struct trace *traces)
{
int i;
- int unconnected_hot_trace_count = 0;
- bool cold_connected = true;
bool *connected;
- bool *cold_traces;
+ bool two_passes;
int last_trace;
+ int current_pass;
+ int current_partition;
int freq_threshold;
gcov_type count_threshold;
else
count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
- connected = xcalloc (n_traces, sizeof (bool));
+ connected = XCNEWVEC (bool, n_traces);
last_trace = -1;
-
- /* If we are partitioning hot/cold basic blocks, mark the cold
- traces as already connected, to remove them from consideration
- for connection to the hot traces. After the hot traces have all
- been connected (determined by "unconnected_hot_trace_count"), we
- will go back and connect the cold traces. */
-
- cold_traces = xcalloc (n_traces, sizeof (bool));
+ current_pass = 1;
+ current_partition = BB_PARTITION (traces[0].first);
+ two_passes = false;
if (flag_reorder_blocks_and_partition)
- for (i = 0; i < n_traces; i++)
- {
- if (BB_PARTITION (traces[i].first) == BB_COLD_PARTITION)
- {
- connected[i] = true;
- cold_traces[i] = true;
- cold_connected = false;
- }
- else
- unconnected_hot_trace_count++;
- }
-
- for (i = 0; i < n_traces || !cold_connected ; i++)
+ for (i = 0; i < n_traces && !two_passes; i++)
+ if (BB_PARTITION (traces[0].first)
+ != BB_PARTITION (traces[i].first))
+ two_passes = true;
+
+ for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
{
int t = i;
int t2;
edge e, best;
int best_len;
- /* If we are partitioning hot/cold basic blocks, check to see
- if all the hot traces have been connected. If so, go back
- and mark the cold traces as unconnected so we can connect
- them up too. Re-set "i" to the first (unconnected) cold
- trace. Use flag "cold_connected" to make sure we don't do
- this step more than once. */
-
- if (flag_reorder_blocks_and_partition
- && (i >= n_traces || unconnected_hot_trace_count <= 0)
- && !cold_connected)
+ if (i >= n_traces)
{
- int j;
- int first_cold_trace = -1;
-
- for (j = 0; j < n_traces; j++)
- if (cold_traces[j])
- {
- connected[j] = false;
- if (first_cold_trace == -1)
- first_cold_trace = j;
- }
- i = t = first_cold_trace;
- cold_connected = true;
+ gcc_assert (two_passes && current_pass == 1);
+ i = 0;
+ t = i;
+ current_pass = 2;
+ if (current_partition == BB_HOT_PARTITION)
+ current_partition = BB_COLD_PARTITION;
+ else
+ current_partition = BB_HOT_PARTITION;
}
if (connected[t])
continue;
+ if (two_passes
+ && BB_PARTITION (traces[t].first) != current_partition)
+ continue;
+
connected[t] = true;
- if (unconnected_hot_trace_count > 0)
- unconnected_hot_trace_count--;
/* Find the predecessor traces. */
for (t2 = t; t2 > 0;)
&& !(e->flags & EDGE_COMPLEX)
&& bbd[si].end_of_trace >= 0
&& !connected[bbd[si].end_of_trace]
+ && (BB_PARTITION (e->src) == current_partition)
&& (!best
|| e->probability > best->probability
|| (e->probability == best->probability
}
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 (unconnected_hot_trace_count > 0)
- unconnected_hot_trace_count--;
-
if (dump_file)
{
fprintf (dump_file, "Connection: %d %d\n",
}
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. */
&& !(e->flags & EDGE_COMPLEX)
&& bbd[di].start_of_trace >= 0
&& !connected[bbd[di].start_of_trace]
+ && (BB_PARTITION (e->dest) == current_partition)
&& (!best
|| e->probability > best->probability
|| (e->probability == best->probability
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;
- if (unconnected_hot_trace_count > 0)
- unconnected_hot_trace_count--;
last_trace = t;
}
else
&& !(e2->flags & EDGE_COMPLEX)
&& bbd[di].start_of_trace >= 0
&& !connected[bbd[di].start_of_trace]
+ && (BB_PARTITION (e2->dest) == current_partition)
&& (EDGE_FREQUENCY (e2) >= freq_threshold)
&& (e2->count >= count_threshold)
&& (!best2
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))
{
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;
- if (unconnected_hot_trace_count > 0)
- unconnected_hot_trace_count--;
last_trace = t;
}
else
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 = (basic_block) bb->aux)
fprintf (dump_file, "%d ", bb->index);
fprintf (dump_file, "\n");
fflush (dump_file);
}
FREE (connected);
- FREE (cold_traces);
}
/* Return true when BB can and should be copied. CODE_MAY_GROW is true
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))
- max_size *= 8;
+ 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)
{
if (INSN_P (insn))
- size += get_attr_length (insn);
+ size += get_attr_min_length (insn);
}
if (size <= max_size)
/* Return the length of unconditional jump instruction. */
-static int
+int
get_uncond_jump_length (void)
{
rtx label, jump;
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);
return length;
}
+/* Emit a barrier into the footer of BB. */
+
static void
-add_unlikely_executed_notes (void)
+emit_barrier_after_bb (basic_block bb)
{
- basic_block bb;
+ rtx barrier = emit_barrier_after (BB_END (bb));
+ bb->il.rtl->footer = unlink_insn_chain (barrier, barrier);
+}
- /* Add the UNLIKELY_EXECUTED_NOTES to each cold basic block. */
+/* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
+ Duplicate the landing pad and split the edges so that no EH edge
+ crosses partitions. */
- FOR_EACH_BB (bb)
- if (BB_PARTITION (bb) == BB_COLD_PARTITION)
- mark_bb_for_unlikely_executed_section (bb);
+static void
+fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
+{
+ eh_landing_pad new_lp;
+ basic_block new_bb, last_bb, post_bb;
+ rtx new_label, jump, post_label;
+ unsigned new_partition;
+ edge_iterator ei;
+ edge e;
+
+ /* Generate the new landing-pad structure. */
+ new_lp = gen_eh_landing_pad (old_lp->region);
+ new_lp->post_landing_pad = old_lp->post_landing_pad;
+ new_lp->landing_pad = gen_label_rtx ();
+ LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
+
+ /* Put appropriate instructions in new bb. */
+ new_label = emit_label (new_lp->landing_pad);
+
+ expand_dw2_landing_pad_for_region (old_lp->region);
+
+ post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
+ post_bb = single_succ (post_bb);
+ post_label = block_label (post_bb);
+ jump = emit_jump_insn (gen_jump (post_label));
+ JUMP_LABEL (jump) = post_label;
+
+ /* Create new basic block to be dest for lp. */
+ last_bb = EXIT_BLOCK_PTR->prev_bb;
+ new_bb = create_basic_block (new_label, jump, last_bb);
+ new_bb->aux = last_bb->aux;
+ last_bb->aux = new_bb;
+
+ emit_barrier_after_bb (new_bb);
+
+ make_edge (new_bb, post_bb, 0);
+
+ /* Make sure new bb is in the other partition. */
+ new_partition = BB_PARTITION (old_bb);
+ new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
+ BB_SET_PARTITION (new_bb, new_partition);
+
+ /* Fix up the edges. */
+ for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
+ if (BB_PARTITION (e->src) == new_partition)
+ {
+ rtx insn = BB_END (e->src);
+ rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
+
+ gcc_assert (note != NULL);
+ gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
+ XEXP (note, 0) = GEN_INT (new_lp->index);
+
+ /* Adjust the edge to the new destination. */
+ redirect_edge_succ (e, new_bb);
+ }
+ else
+ ei_next (&ei);
}
/* Find the basic blocks that are rarely executed and need to be moved to
a separate section of the .o file (to cut down on paging and improve
- cache locality). */
+ cache locality). Return a vector of all edges that cross. */
-static void
-find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
- int *n_crossing_edges,
- int *max_idx)
+static VEC(edge, heap) *
+find_rarely_executed_basic_blocks_and_crossing_edges (void)
{
+ VEC(edge, heap) *crossing_edges = NULL;
basic_block bb;
- bool has_hot_blocks = false;
edge e;
- int i;
edge_iterator ei;
/* Mark which partition (hot/cold) each basic block belongs in. */
-
FOR_EACH_BB (bb)
{
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);
}
- /* Since all "hot" basic blocks will eventually be scheduled before all
- cold basic blocks, make *sure* the real function entry block is in
- the hot partition (if there is one). */
-
- if (has_hot_blocks)
- FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
- if (e->dest->index >= 0)
+ /* The format of .gcc_except_table does not allow landing pads to
+ be in a different partition as the throw. Fix this by either
+ moving or duplicating the landing pads. */
+ if (cfun->eh->lp_array)
+ {
+ unsigned i;
+ eh_landing_pad lp;
+
+ FOR_EACH_VEC_ELT (eh_landing_pad, cfun->eh->lp_array, i, lp)
{
- BB_SET_PARTITION (e->dest, BB_HOT_PARTITION);
- break;
+ bool all_same, all_diff;
+
+ if (lp == NULL
+ || lp->landing_pad == NULL_RTX
+ || !LABEL_P (lp->landing_pad))
+ continue;
+
+ all_same = all_diff = true;
+ bb = BLOCK_FOR_INSN (lp->landing_pad);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ gcc_assert (e->flags & EDGE_EH);
+ if (BB_PARTITION (bb) == BB_PARTITION (e->src))
+ all_diff = false;
+ else
+ all_same = false;
+ }
+
+ if (all_same)
+ ;
+ else if (all_diff)
+ {
+ int which = BB_PARTITION (bb);
+ which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
+ BB_SET_PARTITION (bb, which);
+ }
+ else
+ fix_up_crossing_landing_pad (lp, bb);
}
+ }
/* Mark every edge that crosses between sections. */
- i = 0;
- if (targetm.have_named_sections)
- {
- FOR_EACH_BB (bb)
- FOR_EACH_EDGE (e, ei, bb->succs)
+ FOR_EACH_BB (bb)
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ unsigned int flags = e->flags;
+
+ /* We should never have EDGE_CROSSING set yet. */
+ gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
+
+ if (e->src != ENTRY_BLOCK_PTR
+ && e->dest != EXIT_BLOCK_PTR
+ && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
{
- if (e->src != ENTRY_BLOCK_PTR
- && e->dest != EXIT_BLOCK_PTR
- && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
- {
- e->flags |= EDGE_CROSSING;
- if (i == *max_idx)
- {
- *max_idx *= 2;
- crossing_edges = xrealloc (crossing_edges,
- (*max_idx) * sizeof (edge));
- }
- crossing_edges[i++] = e;
- }
- else
- e->flags &= ~EDGE_CROSSING;
+ VEC_safe_push (edge, heap, crossing_edges, e);
+ flags |= EDGE_CROSSING;
}
- }
- *n_crossing_edges = i;
-}
-/* Add NOTE_INSN_UNLIKELY_EXECUTED_CODE to top of basic block. This note
- is later used to mark the basic block to be put in the
- unlikely-to-be-executed section of the .o file. */
+ /* Now that we've split eh edges as appropriate, allow landing pads
+ to be merged with the post-landing pads. */
+ flags &= ~EDGE_PRESERVE;
-static void
-mark_bb_for_unlikely_executed_section (basic_block bb)
-{
- rtx cur_insn;
- rtx insert_insn = NULL;
- rtx new_note;
-
- /* Insert new NOTE immediately after BASIC_BLOCK note. */
-
- for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
- cur_insn = NEXT_INSN (cur_insn))
- if (GET_CODE (cur_insn) == NOTE
- && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK)
- {
- insert_insn = cur_insn;
- break;
+ e->flags = flags;
}
-
- /* If basic block does not contain a NOTE_INSN_BASIC_BLOCK, there is
- a major problem. */
- gcc_assert (insert_insn);
-
- /* Insert note and assign basic block number to it. */
-
- new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
- insert_insn);
- NOTE_BASIC_BLOCK (new_note) = bb;
+
+ return crossing_edges;
}
/* If any destination of a crossing edge does not have a label, add label;
- Convert any fall-through crossing edges (for blocks that do not contain
- a jump) to unconditional jumps. */
+ Convert any easy fall-through crossing edges to unconditional jumps. */
-static void
-add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
+static void
+add_labels_and_missing_jumps (VEC(edge, heap) *crossing_edges)
{
- int i;
- basic_block src;
- basic_block dest;
- rtx label;
- rtx barrier;
- rtx new_jump;
-
- for (i=0; i < n_crossing_edges; i++)
+ size_t i;
+ edge e;
+
+ FOR_EACH_VEC_ELT (edge, crossing_edges, i, e)
{
- 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))
- {
- if (!JUMP_P (BB_END (src)))
- /* bb just falls through. */
- {
- /* make sure there's only one successor */
- gcc_assert (EDGE_COUNT (src->succs) == 1);
-
- /* Find label in dest block. */
- label = block_label (dest);
-
- 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);
- /* 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 for loop */
+ basic_block src = e->src;
+ basic_block dest = e->dest;
+ rtx label, new_jump;
+
+ if (dest == EXIT_BLOCK_PTR)
+ continue;
+
+ /* Make sure dest has a label. */
+ label = block_label (dest);
+
+ /* Nothing to do for non-fallthru edges. */
+ if (src == ENTRY_BLOCK_PTR)
+ continue;
+ if ((e->flags & EDGE_FALLTHRU) == 0)
+ continue;
+
+ /* If the block does not end with a control flow insn, then we
+ can trivially add a jump to the end to fixup the crossing.
+ Otherwise the jump will have to go in a new bb, which will
+ be handled by fix_up_fall_thru_edges function. */
+ if (control_flow_insn_p (BB_END (src)))
+ continue;
+
+ /* Make sure there's only one successor. */
+ gcc_assert (single_succ_p (src));
+
+ new_jump = emit_jump_insn_after (gen_jump (label), BB_END (src));
+ BB_END (src) = new_jump;
+ JUMP_LABEL (new_jump) = label;
+ LABEL_NUSES (label) += 1;
+
+ emit_barrier_after_bb (src);
+
+ /* Mark edge as non-fallthru. */
+ e->flags &= ~EDGE_FALLTHRU;
+ }
}
/* 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. */
-
-static void
+ 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)
{
basic_block cur_bb;
int invert_worked;
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;
+ }
+ else if (succ1
+ && (block_ends_with_call_p (cur_bb)
+ || can_throw_internal (BB_END (cur_bb))))
+ {
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, cur_bb->succs)
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ fall_thru = e;
+ break;
+ }
+ }
+
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 && JUMP_P (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
+ 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)
+ {
+ 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);
- EDGE_SUCC (new_bb, 0)->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);
- }
- }
- }
- }
+ 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 */
+ emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
+ }
+ }
+ }
}
}
-/* 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
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;
}
{
basic_block cur_bb;
basic_block new_bb;
- basic_block last_bb;
basic_block dest;
- basic_block prev_bb;
edge succ1;
edge succ2;
edge crossing_edge;
rtx set_src;
rtx old_label = NULL_RTX;
rtx new_label;
- rtx new_jump;
- 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
{
+ basic_block last_bb;
+ rtx new_jump;
+
/* 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;
- prev_bb = last_bb;
- last_bb = new_bb;
-
- /* Update register liveness information. */
-
- new_bb->global_live_at_start = ALLOC_REG_SET (®_obstack);
- new_bb->global_live_at_end = ALLOC_REG_SET (®_obstack);
- COPY_REG_SET (new_bb->global_live_at_end,
- prev_bb->global_live_at_end);
- COPY_REG_SET (new_bb->global_live_at_start,
- prev_bb->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),
- BB_END (new_bb));
- }
- else
- {
- gcc_assert (HAVE_return
- && GET_CODE (old_label) == RETURN);
- new_jump = emit_jump_insn_after (gen_return (),
- BB_END (new_bb));
- }
-
- barrier = emit_barrier_after (new_jump);
+ emit_label (new_label);
+
+ gcc_assert (GET_CODE (old_label) == LABEL_REF);
+ old_label = JUMP_LABEL (old_jump);
+ new_jump = emit_jump_insn (gen_jump (old_label));
JUMP_LABEL (new_jump) = old_label;
- new_bb->rbi->footer = unlink_insn_chain (barrier,
- barrier);
-
+
+ last_bb = EXIT_BLOCK_PTR->prev_bb;
+ new_bb = create_basic_block (new_label, new_jump, last_bb);
+ new_bb->aux = last_bb->aux;
+ last_bb->aux = new_bb;
+
+ emit_barrier_after_bb (new_bb);
+
/* 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;
}
- }
+ }
}
}
FOR_EACH_BB (cur_bb)
{
last_insn = BB_END (cur_bb);
+
+ if (EDGE_COUNT (cur_bb->succs) < 1)
+ continue;
+
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
- (e->src)));
+ add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
}
-/* Basic blocks containing NOTE_INSN_UNLIKELY_EXECUTED_CODE will be
- put in a separate section of the .o file, to reduce paging and
- improve cache performance (hopefully). This can result in bits of
- code from the same function being widely separated in the .o file.
- However this is not obvious to the current bb structure. Therefore
- we must take care to ensure that: 1). There are no fall_thru edges
- that cross between sections; 2). For those architectures which
- have "short" conditional branches, all conditional branches that
- attempt to cross between sections are converted to unconditional
- branches; and, 3). For those architectures which have "short"
- unconditional branches, all unconditional branches that attempt
- to cross between 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"
- 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.
-
- 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
- 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. */
+/* Verify, in the basic block chain, that there is at most one switch
+ between hot/cold partitions. This is modelled on
+ rtl_verify_flow_info_1, but it cannot go inside that function
+ because this condition will not be true until after
+ reorder_basic_blocks is called. */
-static void
-fix_edges_for_rarely_executed_code (edge *crossing_edges,
- int n_crossing_edges)
+static void
+verify_hot_cold_block_grouping (void)
{
- /* 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 ();
-
- /* Only do the parts necessary for writing separate sections if
- the target architecture has the ability to write separate sections
- (i.e. it has named sections). Otherwise, the hot/cold partitioning
- information will be used when reordering blocks to try to put all
- the hot blocks together, then all the cold blocks, but no actual
- section partitioning will be done. */
-
- if (targetm.have_named_sections)
+ basic_block bb;
+ int err = 0;
+ bool switched_sections = false;
+ int current_partition = 0;
+
+ FOR_EACH_BB (bb)
{
- /* 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)
+ if (!current_partition)
+ current_partition = BB_PARTITION (bb);
+ if (BB_PARTITION (bb) != current_partition)
{
- fix_crossing_unconditional_branches ();
- reg_scan (get_insns(), max_reg_num ());
+ if (switched_sections)
+ {
+ error ("multiple hot/cold transitions found (bb %i)",
+ bb->index);
+ err = 1;
+ }
+ else
+ {
+ switched_sections = true;
+ current_partition = BB_PARTITION (bb);
+ }
}
-
- add_reg_crossing_jump_notes ();
}
+
+ gcc_assert(!err);
}
/* Reorder basic blocks. The main entry point to this file. FLAGS is
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].in_trace = -1;
bbd[i].end_of_trace = -1;
bbd[i].heap = NULL;
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);
- if (flag_reorder_blocks_and_partition
- && targetm.have_named_sections)
- add_unlikely_executed_notes ();
+ if (flag_reorder_blocks_and_partition)
+ verify_hot_cold_block_grouping ();
+}
- cfg_layout_finalize ();
+/* Determine which partition the first basic block in the function
+ belongs to, then find the first basic block in the current function
+ that belongs to a different section, and insert a
+ NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
+ instruction stream. When writing out the assembly code,
+ encountering this note will make the compiler switch between the
+ hot and cold text sections. */
+
+static void
+insert_section_boundary_note (void)
+{
+ basic_block bb;
+ rtx new_note;
+ int first_partition = 0;
- timevar_pop (TV_REORDER_BLOCKS);
+ if (!flag_reorder_blocks_and_partition)
+ return;
+
+ FOR_EACH_BB (bb)
+ {
+ if (!first_partition)
+ first_partition = BB_PARTITION (bb);
+ if (BB_PARTITION (bb) != first_partition)
+ {
+ 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;
+ }
+ }
}
/* Duplicate the blocks containing computed gotos. This basically unfactors
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_function_for_size_p (cfun));
+}
+
+
+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);
uncond_jump_length = get_uncond_jump_length ();
max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
- candidates = BITMAP_XMALLOC ();
+ candidates = BITMAP_ALLOC (NULL);
- /* Build the reorder chain for the original order of blocks.
- Look for a computed jump while we are at it. */
+ /* Look for blocks that end in a computed jump, and see if such blocks
+ are suitable for unfactoring. If a block is a candidate for unfactoring,
+ mark it in the candidates. */
FOR_EACH_BB (bb)
{
+ rtx insn;
+ edge e;
+ edge_iterator ei;
+ int size, all_flags;
+
+ /* 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;
- /* If the block ends in a computed jump and it is small enough,
- make it a candidate for duplication. */
- if (computed_jump_p (BB_END (bb)))
- {
- rtx insn;
- int size = 0;
+ /* Obviously the block has to end in a computed jump. */
+ if (!computed_jump_p (BB_END (bb)))
+ continue;
- FOR_BB_INSNS (bb, insn)
- {
- if (INSN_P (insn))
- size += get_attr_length (insn);
- if (size > max_size)
- break;
- }
+ /* Only consider blocks that can be duplicated. */
+ if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
+ || !can_duplicate_block_p (bb))
+ continue;
- if (size <= max_size)
- bitmap_set_bit (candidates, bb->index);
- }
+ /* Make sure that the block is small enough. */
+ size = 0;
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn))
+ {
+ size += get_attr_min_length (insn);
+ if (size > max_size)
+ break;
+ }
+ if (size > max_size)
+ continue;
+
+ /* Final check: there must not be any incoming abnormal edges. */
+ all_flags = 0;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ all_flags |= e->flags;
+ if (all_flags & EDGE_COMPLEX)
+ continue;
+
+ bitmap_set_bit (candidates, bb->index);
}
/* Nothing to do if there is no computed jump here. */
/* 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 (EDGE_COUNT(bb->succs) != 1
- || EDGE_SUCC(bb,0)->dest == EXIT_BLOCK_PTR
- || EDGE_SUCC(bb,0)->dest == bb->next_bb
- || EDGE_COUNT(EDGE_SUCC(bb,0)->dest->preds) <= 1)
+ if (!single_succ_p (bb)
+ || single_succ (bb) == EXIT_BLOCK_PTR
+ || single_succ (bb) == bb->next_bb
+ || single_pred_p (single_succ (bb)))
continue;
/* The successor block has to be a duplication candidate. */
- if (!bitmap_bit_p (candidates, EDGE_SUCC(bb,0)->dest->index))
+ if (!bitmap_bit_p (candidates, single_succ (bb)->index))
continue;
- new_bb = duplicate_block (EDGE_SUCC(bb,0)->dest, EDGE_SUCC(bb,0));
- 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_XFREE (candidates);
-
- timevar_pop (TV_REORDER_BLOCKS);
+ BITMAP_FREE (candidates);
+ return 0;
}
+struct rtl_opt_pass pass_duplicate_computed_gotos =
+{
+ {
+ RTL_PASS,
+ "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_verify_rtl_sharing,/* todo_flags_finish */
+ }
+};
+
+
/* 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
function above).
This optimization checks the feedback information to determine
- which basic blocks are hot/cold and causes reorder_basic_blocks to
- add NOTE_INSN_UNLIKELY_EXECUTED_CODE to non-hot basic blocks. The
- presence or absence of this note is later used for writing out
- sections in the .o file. Because hot and cold sections can be
- arbitrarily large (within the bounds of memory), far beyond the
- size of a single function, it is necessary to fix up all edges that
- cross section boundaries, to make sure the instructions used can
- actually span the required distance. The fixes are described
- below.
+ which basic blocks are hot/cold, updates flags on the basic blocks
+ to indicate which section they belong in. This information is
+ later used for writing out sections in the .o file. Because hot
+ and cold sections can be arbitrarily large (within the bounds of
+ memory), far beyond the size of a single function, it is necessary
+ to fix up all edges that cross section boundaries, to make sure the
+ instructions used can actually span the required distance. The
+ fixes are described below.
Fall-through edges must be changed into jumps; it is not safe or
legal to fall through across a section boundary. Whenever a
if we could perform this optimization later in the compilation, but
unfortunately the fact that we may need to create indirect jumps
(through registers) requires that this optimization be performed
- before register allocation. */
+ before register allocation.
+
+ Hot and cold basic blocks are partitioned and put in separate
+ sections of the .o file, to reduce paging and improve cache
+ performance (hopefully). This can result in bits of code from the
+ same function being widely separated in the .o file. However this
+ is not obvious to the current bb structure. Therefore we must take
+ care to ensure that: 1). There are no fall_thru edges that cross
+ between sections; 2). For those architectures which have "short"
+ conditional branches, all conditional branches that attempt to
+ cross between sections are converted to unconditional branches;
+ and, 3). For those architectures which have "short" unconditional
+ branches, all unconditional branches that attempt to cross between
+ sections are converted to indirect jumps.
-void
+ 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"
+ 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.
+
+ 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
+ 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 unsigned
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)
- return;
-
- crossing_edges = xcalloc (max_edges, sizeof (edge));
+ VEC(edge, heap) *crossing_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,
- &max_edges);
-
- if (n_crossing_edges > 0)
- fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
-
- free (crossing_edges);
-
- cfg_layout_finalize();
+ if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
+ return 0;
+
+ df_set_flags (DF_DEFER_INSN_RESCAN);
+
+ crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
+ if (crossing_edges == NULL)
+ return 0;
+
+ /* 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);
+
+ /* 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 ();
+
+ add_reg_crossing_jump_notes ();
+
+ /* Clear bb->aux fields that the above routines were using. */
+ clear_aux_for_blocks ();
+
+ VEC_free (edge, heap, crossing_edges);
+
+ /* ??? FIXME: DF generates the bb info for a block immediately.
+ And by immediately, I mean *during* creation of the block.
+
+ #0 df_bb_refs_collect
+ #1 in df_bb_refs_record
+ #2 in create_basic_block_structure
+
+ Which means that the bb_has_eh_pred test in df_bb_refs_collect
+ will *always* fail, because no edges can have been added to the
+ block yet. Which of course means we don't add the right
+ artificial refs, which means we fail df_verify (much) later.
+
+ Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
+ that we also shouldn't grab data from the new blocks those new
+ insns are in either. In this way one can create the block, link
+ it up properly, and have everything Just Work later, when deferred
+ insns are processed.
+
+ In the meantime, we have no other option but to throw away all
+ of the DF data and recompute it all. */
+ if (cfun->eh->lp_array)
+ {
+ df_finish_pass (true);
+ df_scan_alloc (NULL);
+ df_scan_blocks ();
+ /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
+ data. We blindly generated all of them when creating the new
+ landing pad. Delete those assignments we don't use. */
+ df_set_flags (DF_LR_RUN_DCE);
+ df_analyze ();
+ }
+
+ return TODO_verify_flow | TODO_verify_rtl_sharing;
+}
+\f
+static bool
+gate_handle_reorder_blocks (void)
+{
+ if (targetm.cannot_modify_jumps_p ())
+ return false;
+ /* 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. */
+ if (!optimize_function_for_speed_p (cfun))
+ return false;
+ return (optimize > 0
+ && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
}
+
+
+/* Reorder basic blocks. */
+static unsigned int
+rest_of_handle_reorder_blocks (void)
+{
+ basic_block bb;
+
+ /* Last attempt to optimize CFG, as scheduling, peepholing and insn
+ splitting possibly introduced more crossjumping opportunities. */
+ cfg_layout_initialize (CLEANUP_EXPENSIVE);
+
+ reorder_basic_blocks ();
+ cleanup_cfg (CLEANUP_EXPENSIVE);
+
+ 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 rtl_opt_pass pass_reorder_blocks =
+{
+ {
+ RTL_PASS,
+ "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_verify_rtl_sharing, /* todo_flags_finish */
+ }
+};
+
+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
+ && optimize
+ /* See gate_handle_reorder_blocks. We should not partition if
+ we are going to omit the reordering. */
+ && optimize_function_for_speed_p (cfun)
+ && !DECL_ONE_ONLY (current_function_decl)
+ && !user_defined_section_attribute);
+}
+
+struct rtl_opt_pass pass_partition_blocks =
+{
+ {
+ RTL_PASS,
+ "bbpart", /* name */
+ gate_handle_partition_blocks, /* gate */
+ partition_hot_cold_basic_blocks, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_REORDER_BLOCKS, /* tv_id */
+ PROP_cfglayout, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+ }
+};
OSDN Git Service
