/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000, 2002, 2003, 2004 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
-#include "basic-block.h"
+#include "regs.h"
#include "flags.h"
#include "timevar.h"
#include "output.h"
#include "tm_p.h"
#include "obstack.h"
#include "expr.h"
-#include "regs.h"
+#include "errors.h"
+#include "params.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
/* 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;
#define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
/* Free the memory and set the pointer to NULL. */
-#define FREE(P) \
- do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
+#define FREE(P) (gcc_assert (P), free (P), P = 0)
/* Structure for holding information about a trace. */
struct trace
};
/* 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 *);
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);
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
|| 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
return false;
int i;
int number_of_rounds;
edge e;
+ edge_iterator ei;
fibheap_t heap;
/* Add one extra round of trace collection when partitioning hot/cold
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 ();
max_entry_frequency = 0;
max_entry_count = 0;
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
{
bbd[e->dest->index].heap = heap;
bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
do
{
edge e;
- for (e = bb->succ; e; e = e->succ_next)
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR
&& e->dest->rbi->visited != trace_n
&& (e->flags & EDGE_CAN_FALLTHRU)
prev_bb->rbi->next = best_bb->rbi->next;
/* Try to get rid of uncond jump to cond jump. */
- if (prev_bb->succ && !prev_bb->succ->succ_next)
+ if (single_succ_p (prev_bb))
{
- basic_block header = prev_bb->succ->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,
NULL_RTX))
- {
- copy_bb (header, prev_bb->succ, prev_bb, trace_n);
- }
+ copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
}
}
}
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 ();
struct trace *trace;
edge best_edge, e;
fibheapkey_t key;
+ edge_iterator ei;
bb = fibheap_extract_min (*heap);
bbd[bb->index].heap = NULL;
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 (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
-#ifdef ENABLE_CHECKING
- if (e->flags & EDGE_FAKE)
- abort ();
-#endif
+ gcc_assert (!(e->flags & EDGE_FAKE));
if (e->dest == EXIT_BLOCK_PTR)
continue;
&& e->dest->rbi->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);
+ /* 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 (ie. it is unsuitable successor). */
+ 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)
continue;
/* If the best destination has multiple predecessors, and can be
duplicated cheaper than a jump, don't allow it to be added
to a trace. We'll duplicate it when connecting traces. */
- if (best_edge && best_edge->dest->pred->pred_next
+ if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
&& copy_bb_p (best_edge->dest, 0))
best_edge = NULL;
/* Add all non-selected successors to the heaps. */
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e == best_edge
|| e->dest == EXIT_BLOCK_PTR
best_edge->dest->index, bb->index);
}
bb->rbi->next = 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. */
- /* Check whether there is another edge from BB. */
- edge another_edge;
- for (another_edge = bb->succ;
- another_edge;
- another_edge = another_edge->succ_next)
- if (another_edge != best_edge)
- break;
-
- if (!another_edge && copy_bb_p (best_edge->dest,
- !optimize_size))
+ if (single_succ_p (bb)
+ && copy_bb_p (best_edge->dest, !optimize_size))
{
bb = copy_bb (best_edge->dest, best_edge, bb,
*n_traces);
+ trace->length++;
}
}
}
*/
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
if (e != best_edge
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
&& !e->dest->rbi->visited
- && !e->dest->pred->pred_next
+ && single_pred_p (e->dest)
&& !(e->flags & EDGE_CROSSING)
- && e->dest->succ
- && (e->dest->succ->flags & EDGE_CAN_FALLTHRU)
- && !(e->dest->succ->flags & EDGE_COMPLEX)
- && !e->dest->succ->succ_next
- && e->dest->succ->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;
}
bb->rbi->next = best_edge->dest;
+ bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
bb = best_edge->dest;
}
}
/* The trace is terminated so we have to recount the keys in heap
(some block can have a lower key because now one of its predecessors
is an end of the trace). */
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest == EXIT_BLOCK_PTR
|| e->dest->rbi->visited)
new_bb = duplicate_block (old_bb, e);
BB_COPY_PARTITION (new_bb, old_bb);
- if (e->dest != new_bb)
- abort ();
- if (e->dest->rbi->visited)
- abort ();
+ gcc_assert (e->dest == new_bb);
+ gcc_assert (!e->dest->rbi->visited);
+
if (dump_file)
fprintf (dump_file,
"Duplicated bb %d (created bb %d)\n",
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;
}
bb_to_key (basic_block bb)
{
edge e;
-
+ edge_iterator ei;
int priority = 0;
/* Do not start in probably never executed blocks. */
/* Prefer blocks whose predecessor is an end of some trace
or whose predecessor edge is EDGE_DFS_BACK. */
- for (e = bb->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, bb->preds)
{
if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
|| (e->flags & EDGE_DFS_BACK))
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;
connected = xcalloc (n_traces, sizeof (bool));
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;
+ if (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;
+ }
+ else
+ abort ();
}
-
+
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;)
{
+ edge_iterator ei;
best = NULL;
best_len = 0;
- for (e = traces[t2].first->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
{
int si = e->src->index;
&& !(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
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",
while (1)
{
/* Find the continuation of the chain. */
+ edge_iterator ei;
best = NULL;
best_len = 0;
- for (e = traces[t].last->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, traces[t].last->succs)
{
int di = e->dest->index;
&& !(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
t = bbd[best->dest->index].start_of_trace;
traces[last_trace].last->rbi->next = traces[t].first;
connected[t] = true;
- if (unconnected_hot_trace_count > 0)
- unconnected_hot_trace_count--;
last_trace = t;
}
else
basic_block next_bb = NULL;
bool try_copy = false;
- for (e = traces[t].last->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, traces[t].last->succs)
if (e->dest != EXIT_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
&& (!best || e->probability > best->probability))
{
+ edge_iterator ei;
edge best2 = NULL;
int best2_len = 0;
continue;
}
- for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
+ FOR_EACH_EDGE (e2, ei, e->dest->succs)
{
int di = e2->dest->index;
&& !(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
t = bbd[next_bb->index].start_of_trace;
traces[last_trace].last->rbi->next = traces[t].first;
connected[t] = true;
- if (unconnected_hot_trace_count > 0)
- unconnected_hot_trace_count--;
last_trace = t;
}
else
}
FREE (connected);
- FREE (cold_traces);
}
/* Return true when BB can and should be copied. CODE_MAY_GROW is true
int size = 0;
int max_size = uncond_jump_length;
rtx insn;
- int n_succ;
- edge e;
if (!bb->frequency)
return false;
- if (!bb->pred || !bb->pred->pred_next)
+ if (EDGE_COUNT (bb->preds) < 2)
return false;
if (!can_duplicate_block_p (bb))
return false;
/* Avoid duplicating blocks which have many successors (PR/13430). */
- n_succ = 0;
- for (e = bb->succ; e; e = e->succ_next)
- {
- n_succ++;
- if (n_succ > 8)
- return false;
- }
+ if (EDGE_COUNT (bb->succs) > 8)
+ return false;
if (code_may_grow && maybe_hot_bb_p (bb))
max_size *= 8;
- for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
- insn = NEXT_INSN (insn))
+ FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
size += get_attr_length (insn);
return length;
}
-static void
-add_unlikely_executed_notes (void)
-{
- basic_block bb;
-
- /* Add the UNLIKELY_EXECUTED_NOTES to each cold basic block. */
-
- FOR_EACH_BB (bb)
- if (BB_PARTITION (bb) == BB_COLD_PARTITION)
- mark_bb_for_unlikely_executed_section (bb);
-}
-
/* 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). */
bool has_hot_blocks = false;
edge e;
int i;
+ edge_iterator ei;
/* Mark which partition (hot/cold) each basic block belongs in. */
}
}
- /* 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 (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
- if (e->dest->index >= 0)
- {
- BB_SET_PARTITION (e->dest, BB_HOT_PARTITION);
- break;
- }
-
/* Mark every edge that crosses between sections. */
i = 0;
if (targetm.have_named_sections)
{
FOR_EACH_BB (bb)
- for (e = bb->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->src != ENTRY_BLOCK_PTR
&& e->dest != EXIT_BLOCK_PTR
*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. */
-
-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;
- }
-
- /* If basic block does not contain a NOTE_INSN_BASIC_BLOCK, there is
- a major problem. */
-
- if (!insert_insn)
- abort ();
-
- /* 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;
-}
-
/* 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. */
/* bb just falls through. */
{
/* make sure there's only one successor */
- if (src->succ && (src->succ->succ_next == NULL))
- {
- /* 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;
- }
- else
- {
- /* Basic block has two successors, but
- doesn't end in a jump; something is wrong
- here! */
- abort();
- }
+ gcc_assert (single_succ_p (src));
+
+ /* 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...' */
FOR_EACH_BB (cur_bb)
{
fall_thru = NULL;
- succ1 = cur_bb->succ;
- if (succ1)
- succ2 = succ1->succ_next;
+ if (EDGE_COUNT (cur_bb->succs) > 0)
+ 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;
partition as bb it's falling through from. */
BB_COPY_PARTITION (new_bb, cur_bb);
- new_bb->succ->flags |= EDGE_CROSSING;
+ single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
}
/* Add barrier after new jump */
basic_block source_bb = NULL;
edge e;
rtx insn;
+ edge_iterator ei;
- for (e = jump_dest->pred; e; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, jump_dest->preds)
if (e->flags & EDGE_CROSSING)
{
basic_block src = e->src;
FOR_EACH_BB (cur_bb)
{
crossing_edge = NULL;
- succ1 = cur_bb->succ;
- if (succ1)
- succ2 = succ1->succ_next;
+ if (EDGE_COUNT (cur_bb->succs) > 0)
+ 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;
+ succ2 = NULL;
/* We already took care of fall-through edges, so only one successor
can be a crossing edge. */
/* Update register liveness information. */
- new_bb->global_live_at_start =
- OBSTACK_ALLOC_REG_SET (&flow_obstack);
- new_bb->global_live_at_end =
- OBSTACK_ALLOC_REG_SET (&flow_obstack);
+ 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,
(old_label),
BB_END (new_bb));
}
- else if (HAVE_return
- && GET_CODE (old_label) == RETURN)
- new_jump = emit_jump_insn_after (gen_return (),
- BB_END (new_bb));
else
- abort ();
+ {
+ 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);
JUMP_LABEL (new_jump) = old_label;
will be a successor for new_bb and a predecessor
for 'dest'. */
- if (!new_bb->succ)
+ if (EDGE_COUNT (new_bb->succs) == 0)
new_edge = make_edge (new_bb, dest, 0);
else
- new_edge = new_bb->succ;
+ 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);
- succ = cur_bb->succ;
+
+ 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. */
{
rtx label2, table;
- if (any_condjump_p (last_insn))
- abort ();
+ gcc_assert (!any_condjump_p (last_insn));
/* Make sure the jump is not already an indirect or table jump. */
- else if (!computed_jump_p (last_insn)
- && !tablejump_p (last_insn, &label2, &table))
+ if (!computed_jump_p (last_insn)
+ && !tablejump_p (last_insn, &label2, &table))
{
/* We have found a "crossing" unconditional branch. Now
we must convert it to an indirect jump. First create
{
basic_block bb;
edge e;
+ edge_iterator ei;
FOR_EACH_BB (bb)
- for (e = bb->succ; e; e = e->succ_next)
+ 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,
(e->src)));
}
-/* 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.
-
+/* 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.
+
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"
if (!HAS_LONG_UNCOND_BRANCH)
{
fix_crossing_unconditional_branches ();
- reg_scan (get_insns(), max_reg_num (), 1);
+ reg_scan (get_insns(), max_reg_num ());
}
add_reg_crossing_jump_notes ();
}
}
+/* 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
+verify_hot_cold_block_grouping (void)
+{
+ basic_block bb;
+ int err = 0;
+ bool switched_sections = false;
+ int current_partition = 0;
+
+ FOR_EACH_BB (bb)
+ {
+ if (!current_partition)
+ current_partition = BB_PARTITION (bb);
+ if (BB_PARTITION (bb) != current_partition)
+ {
+ if (switched_sections)
+ {
+ error ("Multiple hot/cold transitions found (bb %i)",
+ bb->index);
+ err = 1;
+ }
+ else
+ {
+ switched_sections = true;
+ current_partition = BB_PARTITION (bb);
+ }
+ }
+ }
+
+ if (err)
+ internal_error ("verify_hot_cold_block_grouping failed");
+}
+
/* Reorder basic blocks. The main entry point to this file. FLAGS is
the set of flags to pass to cfg_layout_initialize(). */
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;
if (dump_file)
dump_flow_info (dump_file);
+ cfg_layout_finalize ();
+ verify_hot_cold_block_grouping ();
+
+ timevar_pop (TV_REORDER_BLOCKS);
+}
+
+/* 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. */
+
+void
+insert_section_boundary_note (void)
+{
+ basic_block bb;
+ rtx new_note;
+ int first_partition = 0;
+
if (flag_reorder_blocks_and_partition
&& targetm.have_named_sections)
- add_unlikely_executed_notes ();
+ 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));
+ break;
+ }
+ }
+}
+
+/* Duplicate the blocks containing computed gotos. This basically unfactors
+ computed gotos that were factored early on in the compilation process to
+ speed up edge based data flow. We used to not unfactoring them again,
+ which can seriously pessimize code with many computed jumps in the source
+ code, such as interpreters. See e.g. PR15242. */
+
+void
+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);
+ cfg_layout_initialize (0);
+
+ /* We are estimating the length of uncond jump insn only once
+ since the code for getting the insn length always returns
+ the minimal length now. */
+ if (uncond_jump_length == 0)
+ uncond_jump_length = get_uncond_jump_length ();
+
+ max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
+ candidates = BITMAP_ALLOC (NULL);
+
+ /* 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;
+
+ /* Obviously the block has to end in a computed jump. */
+ if (!computed_jump_p (BB_END (bb)))
+ continue;
+
+ /* 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;
+
+ /* Make sure that the block is small enough. */
+ size = 0;
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn))
+ {
+ size += get_attr_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. */
+ if (bitmap_empty_p (candidates))
+ goto done;
+
+ /* Duplicate computed gotos. */
+ FOR_EACH_BB (bb)
+ {
+ if (bb->rbi->visited)
+ continue;
+
+ bb->rbi->visited = 1;
+
+ /* BB must have one outgoing edge. That edge must not lead to
+ 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
+ || 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, 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;
+ }
+
+done:
cfg_layout_finalize ();
+ BITMAP_FREE (candidates);
+
timevar_pop (TV_REORDER_BLOCKS);
}
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
OSDN Git Service
