#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "regs.h"
#include "flags.h"
#include "timevar.h"
#include "output.h"
#include "cfglayout.h"
#include "fibheap.h"
#include "target.h"
#include "function.h"
#include "tm_p.h"
#include "obstack.h"
#include "expr.h"
#include "params.h"
#include "toplev.h"
#include "tree-pass.h"
#ifndef ENABLE_LLVM
#ifndef HAVE_conditional_execution
#define HAVE_conditional_execution 0
#endif
#define N_ROUNDS 5
#ifndef HAVE_return
#define HAVE_return 0
#define gen_return() NULL_RTX
#endif
static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
#define DUPLICATION_THRESHOLD 100
static int uncond_jump_length;
typedef struct bbro_basic_block_data_def
{
int start_of_trace;
int end_of_trace;
int in_trace;
fibheap_t heap;
fibnode_t node;
} bbro_basic_block_data;
static int array_size;
static bbro_basic_block_data *bbd;
#define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
#define FREE(P) (gcc_assert (P), free (P), P = 0)
struct trace
{
basic_block first, last;
int round;
int length;
};
static int max_entry_frequency;
static gcov_type max_entry_count;
static void find_traces (int *, struct trace *);
static basic_block rotate_loop (edge, struct trace *, int);
static void mark_bb_visited (basic_block, int);
static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
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 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 find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
int *,
int *);
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
push_to_next_round_p (basic_block bb, int round, int number_of_rounds,
int exec_th, gcov_type count_th)
{
bool there_exists_another_round;
bool block_not_hot_enough;
there_exists_another_round = round < number_of_rounds - 1;
block_not_hot_enough = (bb->frequency < exec_th
|| bb->count < count_th
|| probably_never_executed_bb_p (bb));
if (there_exists_another_round
&& block_not_hot_enough)
return true;
else
return false;
}
static void
find_traces (int *n_traces, struct trace *traces)
{
int i;
int number_of_rounds;
edge e;
edge_iterator ei;
fibheap_t heap;
number_of_rounds = N_ROUNDS - 1;
heap = fibheap_new ();
max_entry_frequency = 0;
max_entry_count = 0;
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),
e->dest);
if (e->dest->frequency > max_entry_frequency)
max_entry_frequency = e->dest->frequency;
if (e->dest->count > max_entry_count)
max_entry_count = e->dest->count;
}
for (i = 0; i < number_of_rounds; i++)
{
gcov_type count_threshold;
if (dump_file)
fprintf (dump_file, "STC - round %d\n", i + 1);
if (max_entry_count < INT_MAX / 1000)
count_threshold = max_entry_count * exec_threshold[i] / 1000;
else
count_threshold = max_entry_count / 1000 * exec_threshold[i];
find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
max_entry_frequency * exec_threshold[i] / 1000,
count_threshold, traces, n_traces, i, &heap,
number_of_rounds);
}
fibheap_delete (heap);
if (dump_file)
{
for (i = 0; i < *n_traces; i++)
{
basic_block bb;
fprintf (dump_file, "Trace %d (round %d): ", i + 1,
traces[i].round + 1);
for (bb = traces[i].first; bb != traces[i].last; bb = bb->aux)
fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
}
fflush (dump_file);
}
}
static basic_block
rotate_loop (edge back_edge, struct trace *trace, int trace_n)
{
basic_block bb;
basic_block best_bb = NULL;
edge best_edge = NULL;
int best_freq = -1;
gcov_type best_count = -1;
bool is_preferred = false;
bb = back_edge->dest;
do
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->dest != EXIT_BLOCK_PTR
&& e->dest->il.rtl->visited != trace_n
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX))
{
if (is_preferred)
{
if (!e->dest->il.rtl->visited
|| bbd[e->dest->index].start_of_trace >= 0)
{
int freq = EDGE_FREQUENCY (e);
if (freq > best_freq || e->count > best_count)
{
best_freq = freq;
best_count = e->count;
best_edge = e;
best_bb = bb;
}
}
}
else
{
if (!e->dest->il.rtl->visited
|| bbd[e->dest->index].start_of_trace >= 0)
{
is_preferred = true;
best_freq = EDGE_FREQUENCY (e);
best_count = e->count;
best_edge = e;
best_bb = bb;
}
else
{
int freq = EDGE_FREQUENCY (e);
if (!best_edge || freq > best_freq || e->count > best_count)
{
best_freq = freq;
best_count = e->count;
best_edge = e;
best_bb = bb;
}
}
}
}
bb = bb->aux;
}
while (bb != back_edge->dest);
if (best_bb)
{
if (back_edge->dest == trace->first)
{
trace->first = best_bb->aux;
}
else
{
basic_block prev_bb;
for (prev_bb = trace->first;
prev_bb->aux != back_edge->dest;
prev_bb = prev_bb->aux)
;
prev_bb->aux = best_bb->aux;
if (single_succ_p (prev_bb))
{
basic_block header = single_succ (prev_bb);
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, single_succ_edge (prev_bb), prev_bb, trace_n);
}
}
}
else
{
best_bb = back_edge->src;
}
best_bb->aux = NULL;
return best_bb;
}
static void
mark_bb_visited (basic_block bb, int trace)
{
bb->il.rtl->visited = trace;
if (bbd[bb->index].heap)
{
fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
bbd[bb->index].heap = NULL;
bbd[bb->index].node = NULL;
}
}
static void
find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
struct trace *traces, int *n_traces, int round,
fibheap_t *heap, int number_of_rounds)
{
fibheap_t new_heap = fibheap_new ();
while (!fibheap_empty (*heap))
{
basic_block bb;
struct trace *trace;
edge best_edge, e;
fibheapkey_t key;
edge_iterator ei;
bb = fibheap_extract_min (*heap);
bbd[bb->index].heap = NULL;
bbd[bb->index].node = NULL;
if (dump_file)
fprintf (dump_file, "Getting bb %d\n", bb->index);
if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
count_th))
{
int key = bb_to_key (bb);
bbd[bb->index].heap = new_heap;
bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
if (dump_file)
fprintf (dump_file,
" Possible start point of next round: %d (key: %d)\n",
bb->index, key);
continue;
}
trace = traces + *n_traces;
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;
int best_prob = INT_MIN / 2;
int best_freq = INT_MIN / 2;
best_edge = NULL;
mark_bb_visited (bb, *n_traces);
trace->length++;
if (dump_file)
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);
FOR_EACH_EDGE (e, ei, bb->succs)
{
gcc_assert (!(e->flags & EDGE_FAKE));
if (e->dest == EXIT_BLOCK_PTR)
continue;
if (e->dest->il.rtl->visited
&& e->dest->il.rtl->visited != *n_traces)
continue;
if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
continue;
prob = e->probability;
freq = e->dest->frequency;
if (ends_in_call)
{
if (e->flags & EDGE_CAN_FALLTHRU)
{
best_edge = e;
best_prob = prob;
best_freq = freq;
}
continue;
}
if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
|| prob < branch_th || EDGE_FREQUENCY (e) < exec_th
|| e->count < count_th)
continue;
if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
best_edge))
{
best_edge = e;
best_prob = prob;
best_freq = freq;
}
}
if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
&& copy_bb_p (best_edge->dest, 0))
best_edge = NULL;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e == best_edge
|| e->dest == EXIT_BLOCK_PTR
|| e->dest->il.rtl->visited)
continue;
key = bb_to_key (e->dest);
if (bbd[e->dest->index].heap)
{
if (key != bbd[e->dest->index].node->key)
{
if (dump_file)
{
fprintf (dump_file,
"Changing key for bb %d from %ld to %ld.\n",
e->dest->index,
(long) bbd[e->dest->index].node->key,
key);
}
fibheap_replace_key (bbd[e->dest->index].heap,
bbd[e->dest->index].node, key);
}
}
else
{
fibheap_t which_heap = *heap;
prob = e->probability;
freq = EDGE_FREQUENCY (e);
if (!(e->flags & EDGE_CAN_FALLTHRU)
|| (e->flags & EDGE_COMPLEX)
|| prob < branch_th || freq < exec_th
|| e->count < count_th)
{
if (push_to_next_round_p (e->dest, round,
number_of_rounds,
exec_th, count_th))
which_heap = new_heap;
}
bbd[e->dest->index].heap = which_heap;
bbd[e->dest->index].node = fibheap_insert (which_heap,
key, e->dest);
if (dump_file)
{
fprintf (dump_file,
" Possible start of %s round: %d (key: %ld)\n",
(which_heap == new_heap) ? "next" : "this",
e->dest->index, (long) key);
}
}
}
if (best_edge)
{
if (best_edge->dest->il.rtl->visited == *n_traces)
{
if (best_edge->dest != bb)
{
if (EDGE_FREQUENCY (best_edge)
> 4 * best_edge->dest->frequency / 5)
{
if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
{
if (dump_file)
{
fprintf (dump_file,
"Rotating loop %d - %d\n",
best_edge->dest->index, bb->index);
}
bb->aux = best_edge->dest;
bbd[best_edge->dest->index].in_trace =
(*n_traces) - 1;
bb = rotate_loop (best_edge, trace, *n_traces);
}
}
else
{
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++;
}
}
}
break;
}
else
{
FOR_EACH_EDGE (e, ei, bb->succs)
if (e != best_edge
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
&& !e->dest->il.rtl->visited
&& single_pred_p (e->dest)
&& !(e->flags & EDGE_CROSSING)
&& 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;
if (dump_file)
fprintf (dump_file, "Selecting BB %d\n",
best_edge->dest->index);
break;
}
bb->aux = best_edge->dest;
bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
bb = best_edge->dest;
}
}
}
while (best_edge);
trace->last = bb;
bbd[trace->first->index].start_of_trace = *n_traces - 1;
bbd[trace->last->index].end_of_trace = *n_traces - 1;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest == EXIT_BLOCK_PTR
|| e->dest->il.rtl->visited)
continue;
if (bbd[e->dest->index].heap)
{
key = bb_to_key (e->dest);
if (key != bbd[e->dest->index].node->key)
{
if (dump_file)
{
fprintf (dump_file,
"Changing key for bb %d from %ld to %ld.\n",
e->dest->index,
(long) bbd[e->dest->index].node->key, key);
}
fibheap_replace_key (bbd[e->dest->index].heap,
bbd[e->dest->index].node,
key);
}
}
}
}
fibheap_delete (*heap);
*heap = new_heap;
}
static basic_block
copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
{
basic_block new_bb;
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->il.rtl->visited);
if (dump_file)
fprintf (dump_file,
"Duplicated bb %d (created bb %d)\n",
old_bb->index, new_bb->index);
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)
{
int i;
int new_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));
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;
}
array_size = new_size;
if (dump_file)
{
fprintf (dump_file,
"Growing the dynamic array to %d elements.\n",
array_size);
}
}
bbd[new_bb->index].in_trace = trace;
return new_bb;
}
static fibheapkey_t
bb_to_key (basic_block bb)
{
edge e;
edge_iterator ei;
int priority = 0;
if (BB_PARTITION (bb) == BB_COLD_PARTITION
|| probably_never_executed_bb_p (bb))
return BB_FREQ_MAX;
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))
{
int edge_freq = EDGE_FREQUENCY (e);
if (edge_freq > priority)
priority = edge_freq;
}
}
if (priority)
return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
return -bb->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)
{
bool is_better_edge;
int diff_prob = best_prob / 10;
int diff_freq = best_freq / 10;
if (prob > best_prob + diff_prob)
is_better_edge = true;
else if (prob < best_prob - diff_prob)
is_better_edge = false;
else if (freq < best_freq - diff_freq)
is_better_edge = true;
else if (freq > best_freq + diff_freq)
is_better_edge = false;
else if (e->dest->prev_bb == bb)
is_better_edge = true;
else
is_better_edge = false;
if (!is_better_edge
&& flag_reorder_blocks_and_partition
&& cur_best_edge
&& (cur_best_edge->flags & EDGE_CROSSING)
&& !(e->flags & EDGE_CROSSING))
is_better_edge = true;
return is_better_edge;
}
static void
connect_traces (int n_traces, struct trace *traces)
{
int i;
bool *connected;
bool two_passes;
int last_trace;
int current_pass;
int current_partition;
int freq_threshold;
gcov_type count_threshold;
freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
if (max_entry_count < INT_MAX / 1000)
count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
else
count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
connected = XCNEWVEC (bool, n_traces);
last_trace = -1;
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 && !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 (i >= n_traces)
{
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;
for (t2 = t; t2 > 0;)
{
edge_iterator ei;
best = NULL;
best_len = 0;
FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
{
int si = e->src->index;
if (e->src != ENTRY_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(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
&& traces[bbd[si].end_of_trace].length > best_len)))
{
best = e;
best_len = traces[bbd[si].end_of_trace].length;
}
}
if (best)
{
best->src->aux = best->dest;
t2 = bbd[best->src->index].end_of_trace;
connected[t2] = true;
if (dump_file)
{
fprintf (dump_file, "Connection: %d %d\n",
best->src->index, best->dest->index);
}
}
else
break;
}
if (last_trace >= 0)
traces[last_trace].last->aux = traces[t2].first;
last_trace = t;
while (1)
{
edge_iterator ei;
best = NULL;
best_len = 0;
FOR_EACH_EDGE (e, ei, traces[t].last->succs)
{
int di = e->dest->index;
if (e->dest != EXIT_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(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
&& traces[bbd[di].start_of_trace].length > best_len)))
{
best = e;
best_len = traces[bbd[di].start_of_trace].length;
}
}
if (best)
{
if (dump_file)
{
fprintf (dump_file, "Connection: %d %d\n",
best->src->index, best->dest->index);
}
t = bbd[best->dest->index].start_of_trace;
traces[last_trace].last->aux = traces[t].first;
connected[t] = true;
last_trace = t;
}
else
{
edge e2;
basic_block next_bb = NULL;
bool try_copy = false;
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;
if (bbd[e->dest->index].start_of_trace >= 0
&& traces[bbd[e->dest->index].start_of_trace].length
== 1)
{
best = e;
try_copy = true;
continue;
}
FOR_EACH_EDGE (e2, ei, e->dest->succs)
{
int di = e2->dest->index;
if (e2->dest == EXIT_BLOCK_PTR
|| ((e2->flags & EDGE_CAN_FALLTHRU)
&& !(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
|| e2->probability > best2->probability
|| (e2->probability == best2->probability
&& traces[bbd[di].start_of_trace].length
> best2_len))))
{
best = e;
best2 = e2;
if (e2->dest != EXIT_BLOCK_PTR)
best2_len = traces[bbd[di].start_of_trace].length;
else
best2_len = INT_MAX;
next_bb = e2->dest;
try_copy = true;
}
}
}
if (flag_reorder_blocks_and_partition)
try_copy = false;
if (try_copy
&& copy_bb_p (best->dest,
!optimize_size
&& EDGE_FREQUENCY (best) >= freq_threshold
&& best->count >= count_threshold))
{
basic_block new_bb;
if (dump_file)
{
fprintf (dump_file, "Connection: %d %d ",
traces[t].last->index, best->dest->index);
if (!next_bb)
fputc ('\n', dump_file);
else if (next_bb == EXIT_BLOCK_PTR)
fprintf (dump_file, "exit\n");
else
fprintf (dump_file, "%d\n", next_bb->index);
}
new_bb = copy_bb (best->dest, best, traces[t].last, t);
traces[t].last = new_bb;
if (next_bb && next_bb != EXIT_BLOCK_PTR)
{
t = bbd[next_bb->index].start_of_trace;
traces[last_trace].last->aux = traces[t].first;
connected[t] = true;
last_trace = t;
}
else
break;
}
else
break;
}
}
}
if (dump_file)
{
basic_block bb;
fprintf (dump_file, "Final order:\n");
for (bb = traces[0].first; bb; bb = bb->aux)
fprintf (dump_file, "%d ", bb->index);
fprintf (dump_file, "\n");
fflush (dump_file);
}
FREE (connected);
}
static bool
copy_bb_p (basic_block bb, int code_may_grow)
{
int size = 0;
int max_size = uncond_jump_length;
rtx insn;
if (!bb->frequency)
return false;
if (EDGE_COUNT (bb->preds) < 2)
return false;
if (!can_duplicate_block_p (bb))
return false;
if (EDGE_COUNT (bb->succs) > 8)
return false;
if (code_may_grow && maybe_hot_bb_p (bb))
max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
size += get_attr_min_length (insn);
}
if (size <= max_size)
return true;
if (dump_file)
{
fprintf (dump_file,
"Block %d can't be copied because its size = %d.\n",
bb->index, size);
}
return false;
}
static int
get_uncond_jump_length (void)
{
rtx label, jump;
int length;
label = emit_label_before (gen_label_rtx (), get_insns ());
jump = emit_jump_insn (gen_jump (label));
length = get_attr_min_length (jump);
delete_insn (jump);
delete_insn (label);
return length;
}
static void
find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
int *n_crossing_edges,
int *max_idx)
{
basic_block bb;
bool has_hot_blocks = false;
edge e;
int i;
edge_iterator ei;
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;
}
}
i = 0;
FOR_EACH_BB (bb)
FOR_EACH_EDGE (e, ei, bb->succs)
{
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;
}
*n_crossing_edges = i;
}
static void
add_labels_and_missing_jumps (edge *crossing_edges, int n_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++)
{
if (crossing_edges[i])
{
src = crossing_edges[i]->src;
dest = crossing_edges[i]->dest;
if (dest && (dest != EXIT_BLOCK_PTR))
{
label = block_label (dest);
if (src && (src != ENTRY_BLOCK_PTR))
{
if (!JUMP_P (BB_END (src)))
{
gcc_assert (single_succ_p (src));
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->il.rtl->footer = unlink_insn_chain (barrier, barrier);
crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
}
}
}
}
}
}
static void
fix_up_fall_thru_edges (void)
{
basic_block cur_bb;
basic_block new_bb;
edge succ1;
edge succ2;
edge fall_thru;
edge cond_jump = NULL;
edge e;
bool cond_jump_crosses;
int invert_worked;
rtx old_jump;
rtx fall_thru_label;
rtx barrier;
FOR_EACH_BB (cur_bb)
{
fall_thru = NULL;
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;
if (succ1
&& (succ1->flags & EDGE_FALLTHRU))
{
fall_thru = succ1;
cond_jump = succ2;
}
else if (succ2
&& (succ2->flags & EDGE_FALLTHRU))
{
fall_thru = succ2;
cond_jump = succ1;
}
if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
{
if (fall_thru->flags & EDGE_CROSSING)
{
cond_jump_crosses = true;
invert_worked = 0;
old_jump = BB_END (cur_bb);
if (cond_jump)
{
if (!(cond_jump->flags & EDGE_CROSSING))
cond_jump_crosses = false;
if (!cond_jump_crosses
&& cur_bb->aux == cond_jump->dest)
{
fall_thru_label = block_label (fall_thru->dest);
if (old_jump && fall_thru_label)
invert_worked = invert_jump (old_jump,
fall_thru_label,0);
if (invert_worked)
{
fall_thru->flags &= ~EDGE_FALLTHRU;
cond_jump->flags |= EDGE_FALLTHRU;
update_br_prob_note (cur_bb);
e = fall_thru;
fall_thru = cond_jump;
cond_jump = e;
cond_jump->flags |= EDGE_CROSSING;
fall_thru->flags &= ~EDGE_CROSSING;
}
}
}
if (cond_jump_crosses || !invert_worked)
{
new_bb = force_nonfallthru (fall_thru);
if (new_bb)
{
new_bb->aux = cur_bb->aux;
cur_bb->aux = new_bb;
BB_COPY_PARTITION (new_bb, cur_bb);
single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
}
if (new_bb)
{
barrier = emit_barrier_after (BB_END (new_bb));
new_bb->il.rtl->footer = unlink_insn_chain (barrier,
barrier);
}
else
{
barrier = emit_barrier_after (BB_END (cur_bb));
cur_bb->il.rtl->footer = unlink_insn_chain (barrier,
barrier);
}
}
}
}
}
}
static basic_block
find_jump_block (basic_block jump_dest)
{
basic_block source_bb = NULL;
edge e;
rtx insn;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, jump_dest->preds)
if (e->flags & EDGE_CROSSING)
{
basic_block src = e->src;
if (LABEL_P (BB_HEAD (src)))
for (insn = BB_HEAD (src);
!INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
insn = NEXT_INSN (insn))
{
if (INSN_P (insn)
&& insn == BB_END (src)
&& JUMP_P (insn)
&& !any_condjump_p (insn))
{
source_bb = src;
break;
}
}
if (source_bb)
break;
}
return source_bb;
}
static void
fix_crossing_conditional_branches (void)
{
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;
edge new_edge;
rtx old_jump;
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;
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;
if (succ1 && (succ1->flags & EDGE_CROSSING))
crossing_edge = succ1;
else if (succ2 && (succ2->flags & EDGE_CROSSING))
crossing_edge = succ2;
if (crossing_edge)
{
old_jump = BB_END (cur_bb);
set_src = NULL_RTX;
if (any_condjump_p (old_jump))
{
if (GET_CODE (PATTERN (old_jump)) == SET)
set_src = SET_SRC (PATTERN (old_jump));
else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
{
set_src = XVECEXP (PATTERN (old_jump), 0,0);
if (GET_CODE (set_src) == SET)
set_src = SET_SRC (set_src);
else
set_src = NULL_RTX;
}
}
if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
{
if (GET_CODE (XEXP (set_src, 1)) == PC)
old_label = XEXP (set_src, 2);
else if (GET_CODE (XEXP (set_src, 2)) == PC)
old_label = XEXP (set_src, 1);
new_bb = find_jump_block (crossing_edge->dest);
if (new_bb)
new_label = block_label (new_bb);
else
{
new_bb = create_basic_block (NULL, NULL, last_bb);
new_bb->aux = last_bb->aux;
last_bb->aux = new_bb;
prev_bb = last_bb;
last_bb = new_bb;
new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
prev_bb->il.rtl->global_live_at_end);
COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
prev_bb->il.rtl->global_live_at_end);
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);
JUMP_LABEL (new_jump) = old_label;
new_bb->il.rtl->footer = unlink_insn_chain (barrier,
barrier);
BB_COPY_PARTITION (new_bb, cur_bb);
}
redirect_jump (old_jump, new_label, 0);
dest = crossing_edge->dest;
redirect_edge_succ (crossing_edge, new_bb);
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;
}
}
}
}
static void
fix_crossing_unconditional_branches (void)
{
basic_block cur_bb;
rtx last_insn;
rtx label;
rtx label_addr;
rtx indirect_jump_sequence;
rtx jump_insn = NULL_RTX;
rtx new_reg;
rtx cur_insn;
edge succ;
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);
if (JUMP_P (last_insn)
&& (succ->flags & EDGE_CROSSING))
{
rtx label2, table;
gcc_assert (!any_condjump_p (last_insn));
if (!computed_jump_p (last_insn)
&& !tablejump_p (last_insn, &label2, &table))
{
label = JUMP_LABEL (last_insn);
label_addr = gen_rtx_LABEL_REF (Pmode, label);
LABEL_NUSES (label) += 1;
new_reg = gen_reg_rtx (Pmode);
start_sequence ();
emit_move_insn (new_reg, label_addr);
emit_indirect_jump (new_reg);
indirect_jump_sequence = get_insns ();
end_sequence ();
for (cur_insn = indirect_jump_sequence; cur_insn;
cur_insn = NEXT_INSN (cur_insn))
{
if (!BARRIER_P (cur_insn))
BLOCK_FOR_INSN (cur_insn) = cur_bb;
if (JUMP_P (cur_insn))
jump_insn = cur_insn;
}
emit_insn_before (indirect_jump_sequence, last_insn);
delete_insn (last_insn);
BB_END (cur_bb) = jump_insn;
}
}
}
}
static void
add_reg_crossing_jump_notes (void)
{
basic_block bb;
edge e;
edge_iterator ei;
FOR_EACH_BB (bb)
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)));
}
static void
fix_edges_for_rarely_executed_code (edge *crossing_edges,
int n_crossing_edges)
{
add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
fix_up_fall_thru_edges ();
if (!HAS_LONG_COND_BRANCH)
fix_crossing_conditional_branches ();
if (!HAS_LONG_UNCOND_BRANCH)
{
fix_crossing_unconditional_branches ();
reg_scan (get_insns(), max_reg_num ());
}
add_reg_crossing_jump_notes ();
}
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);
}
}
}
gcc_assert(!err);
}
void
reorder_basic_blocks (unsigned int flags)
{
int n_traces;
int i;
struct trace *traces;
if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
if (targetm.cannot_modify_jumps_p ())
return;
cfg_layout_initialize (flags);
set_edge_can_fallthru_flag ();
mark_dfs_back_edges ();
if (uncond_jump_length == 0)
uncond_jump_length = get_uncond_jump_length ();
array_size = GET_ARRAY_SIZE (last_basic_block);
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 = XNEWVEC (struct trace, n_basic_blocks);
n_traces = 0;
find_traces (&n_traces, traces);
connect_traces (n_traces, traces);
FREE (traces);
FREE (bbd);
if (dump_file)
dump_flow_info (dump_file, dump_flags);
cfg_layout_finalize ();
if (flag_reorder_blocks_and_partition)
verify_hot_cold_block_grouping ();
}
static void
insert_section_boundary_note (void)
{
basic_block bb;
rtx new_note;
int first_partition = 0;
if (flag_reorder_blocks_and_partition)
FOR_EACH_BB (bb)
{
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;
}
}
}
#endif
static bool
gate_duplicate_computed_gotos (void)
{
return (optimize > 0 && flag_expensive_optimizations && !optimize_size);
}
static unsigned int
duplicate_computed_gotos (void)
{
#ifndef ENABLE_LLVM
basic_block bb, new_bb;
bitmap candidates;
int max_size;
if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return 0;
if (targetm.cannot_modify_jumps_p ())
return 0;
cfg_layout_initialize (0);
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);
FOR_EACH_BB (bb)
{
rtx insn;
edge e;
edge_iterator ei;
int size, all_flags;
if (bb->next_bb != EXIT_BLOCK_PTR)
bb->aux = bb->next_bb;
if (!computed_jump_p (BB_END (bb)))
continue;
if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
|| !can_duplicate_block_p (bb))
continue;
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;
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);
}
if (bitmap_empty_p (candidates))
goto done;
FOR_EACH_BB (bb)
{
if (bb->il.rtl->visited)
continue;
bb->il.rtl->visited = 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;
if (!bitmap_bit_p (candidates, single_succ (bb)->index))
continue;
new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
new_bb->aux = bb->aux;
bb->aux = new_bb;
new_bb->il.rtl->visited = 1;
}
done:
cfg_layout_finalize ();
BITMAP_FREE (candidates);
#endif
return 0;
}
struct tree_opt_pass pass_duplicate_computed_gotos =
{
"compgotos",
gate_duplicate_computed_gotos,
duplicate_computed_gotos,
NULL,
NULL,
0,
TV_REORDER_BLOCKS,
0,
0,
0,
0,
TODO_dump_func,
0
};
#ifndef ENABLE_LLVM
static void
partition_hot_cold_basic_blocks (void)
{
basic_block cur_bb;
edge *crossing_edges;
int n_crossing_edges;
int max_edges = 2 * last_basic_block;
if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
return;
crossing_edges = XCNEWVEC (edge, max_edges);
cfg_layout_initialize (0);
FOR_EACH_BB (cur_bb)
if (cur_bb->index >= NUM_FIXED_BLOCKS
&& cur_bb->next_bb->index >= NUM_FIXED_BLOCKS)
cur_bb->aux = cur_bb->next_bb;
find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
&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();
}
#endif
static bool
gate_handle_reorder_blocks (void)
{
return (optimize > 0);
}
static unsigned int
rest_of_handle_reorder_blocks (void)
{
#ifndef ENABLE_LLVM
bool changed;
unsigned int liveness_flags;
liveness_flags = (!HAVE_conditional_execution ? CLEANUP_UPDATE_LIFE : 0);
changed = cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags);
if (flag_sched2_use_traces && flag_schedule_insns_after_reload)
{
timevar_push (TV_TRACER);
tracer (liveness_flags);
timevar_pop (TV_TRACER);
}
if (flag_reorder_blocks || flag_reorder_blocks_and_partition)
reorder_basic_blocks (liveness_flags);
if (flag_reorder_blocks || flag_reorder_blocks_and_partition
|| (flag_sched2_use_traces && flag_schedule_insns_after_reload))
changed |= cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags);
if (changed && HAVE_conditional_execution)
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
PROP_DEATH_NOTES);
insert_section_boundary_note ();
#endif
return 0;
}
struct tree_opt_pass pass_reorder_blocks =
{
"bbro",
gate_handle_reorder_blocks,
rest_of_handle_reorder_blocks,
NULL,
NULL,
0,
TV_REORDER_BLOCKS,
0,
0,
0,
0,
TODO_dump_func,
'B'
};
static bool
gate_handle_partition_blocks (void)
{
return (flag_reorder_blocks_and_partition
&& !DECL_ONE_ONLY (current_function_decl)
&& !user_defined_section_attribute);
}
static unsigned int
rest_of_handle_partition_blocks (void)
{
#ifndef ENABLE_LLVM
no_new_pseudos = 0;
partition_hot_cold_basic_blocks ();
allocate_reg_life_data ();
update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
PROP_LOG_LINKS | PROP_REG_INFO | PROP_DEATH_NOTES);
no_new_pseudos = 1;
#endif
return 0;
}
struct tree_opt_pass pass_partition_blocks =
{
"bbpart",
gate_handle_partition_blocks,
rest_of_handle_partition_blocks,
NULL,
NULL,
0,
TV_REORDER_BLOCKS,
0,
0,
0,
0,
TODO_dump_func,
0
};