/* 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 "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
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
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 (EDGE_COUNT (prev_bb->succs) == 1)
{
- basic_block header = prev_bb->succ->dest;
+ basic_block header = EDGE_SUCC (prev_bb, 0)->dest;
/* Duplicate HEADER if it is a small block containing cond jump
in the end. */
&& !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
NULL_RTX))
{
- copy_bb (header, prev_bb->succ, prev_bb, trace_n);
+ copy_bb (header, EDGE_SUCC (prev_bb, 0), prev_bb, trace_n);
}
}
}
struct trace *trace;
edge best_edge, e;
fibheapkey_t key;
+ edge_iterator ei;
bb = fibheap_extract_min (*heap);
bbd[bb->index].heap = NULL;
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)
{
gcc_assert (!(e->flags & EDGE_FAKE));
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 (i.e. it is unsuitable successor). */
if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
/* 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
{
/* 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 (EDGE_COUNT (bb->succs) == 1
+ && copy_bb_p (best_edge->dest, !optimize_size))
{
bb = copy_bb (best_edge->dest, best_edge, bb,
*n_traces);
*/
- 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
+ && EDGE_COUNT (e->dest->preds) == 1
&& !(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
+ && 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
&& 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
{
best_edge = e;
/* 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)
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))
/* 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;
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;
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;
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);
bool has_hot_blocks = false;
edge e;
int i;
+ edge_iterator ei;
/* Mark which partition (hot/cold) each basic block belongs in. */
the hot partition (if there is one). */
if (has_hot_blocks)
- for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
+ FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
if (e->dest->index >= 0)
{
BB_SET_PARTITION (e->dest, BB_HOT_PARTITION);
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
/* bb just falls through. */
{
/* make sure there's only one successor */
- gcc_assert (src->succ && !src->succ->succ_next);
+ gcc_assert (EDGE_COUNT (src->succs) == 1);
/* Find label in dest block. */
label = block_label (dest);
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;
+ EDGE_SUCC (new_bb, 0)->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,
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;
+ 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. */
{
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,
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 ();
timevar_pop (TV_REORDER_BLOCKS);
}
+/* 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);
+
+ /* Build the reorder chain for the original order of blocks.
+ Look for a computed jump while we are at it. */
+ FOR_EACH_BB (bb)
+ {
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ bb->rbi->next = 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;
+
+ FOR_BB_INSNS (bb, insn)
+ {
+ if (INSN_P (insn))
+ {
+ /* If the insn isn't copyable, don't duplicate
+ the block. */
+ if (targetm.cannot_copy_insn_p
+ && targetm.cannot_copy_insn_p (insn))
+ {
+ size = max_size + 1;
+ break;
+ }
+ size += get_attr_length (insn);
+ }
+ if (size > max_size)
+ break;
+ }
+
+ if (size <= max_size)
+ 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 (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)
+ continue;
+
+ /* The successor block has to be a duplication candidate. */
+ if (!bitmap_bit_p (candidates, EDGE_SUCC(bb,0)->dest->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;
+ }
+
+done:
+ cfg_layout_finalize ();
+
+ BITMAP_FREE (candidates);
+
+ timevar_pop (TV_REORDER_BLOCKS);
+}
+
/* 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
OSDN Git Service
