/* Instruction scheduling pass.
Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
and currently maintained by, Jim Wilson (wilson@cygnus.com)
#include "toplev.h"
#include "recog.h"
#include "cfglayout.h"
+#include "params.h"
#include "sched-int.h"
#include "target.h"
\f
static int sched_n_insns;
/* Implementations of the sched_info functions for region scheduling. */
-static void init_ready_list PARAMS ((struct ready_list *));
-static int can_schedule_ready_p PARAMS ((rtx));
-static int new_ready PARAMS ((rtx));
-static int schedule_more_p PARAMS ((void));
-static const char *ebb_print_insn PARAMS ((rtx, int));
-static int rank PARAMS ((rtx, rtx));
-static int contributes_to_priority PARAMS ((rtx, rtx));
-static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
-static basic_block earliest_block_with_similiar_load PARAMS ((basic_block,
- rtx));
-static void add_deps_for_risky_insns PARAMS ((rtx, rtx));
-static basic_block schedule_ebb PARAMS ((rtx, rtx));
-static basic_block fix_basic_block_boundaries PARAMS ((basic_block, basic_block, rtx, rtx));
-static void add_missing_bbs PARAMS ((rtx, basic_block, basic_block));
+static void init_ready_list (struct ready_list *);
+static int can_schedule_ready_p (rtx);
+static int new_ready (rtx);
+static int schedule_more_p (void);
+static const char *ebb_print_insn (rtx, int);
+static int rank (rtx, rtx);
+static int contributes_to_priority (rtx, rtx);
+static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
+static basic_block earliest_block_with_similiar_load (basic_block, rtx);
+static void add_deps_for_risky_insns (rtx, rtx);
+static basic_block schedule_ebb (rtx, rtx);
+static basic_block fix_basic_block_boundaries (basic_block, basic_block, rtx,
+ rtx);
+static void add_missing_bbs (rtx, basic_block, basic_block);
/* Return nonzero if there are more insns that should be scheduled. */
static int
-schedule_more_p ()
+schedule_more_p (void)
{
return sched_n_insns < target_n_insns;
}
once before scheduling a set of insns. */
static void
-init_ready_list (ready)
- struct ready_list *ready;
+init_ready_list (struct ready_list *ready)
{
rtx prev_head = current_sched_info->prev_head;
rtx next_tail = current_sched_info->next_tail;
insn can be scheduled, nonzero if we should silently discard it. */
static int
-can_schedule_ready_p (insn)
- rtx insn ATTRIBUTE_UNUSED;
+can_schedule_ready_p (rtx insn ATTRIBUTE_UNUSED)
{
sched_n_insns++;
return 1;
if it should be moved to the ready list or the queue, or zero if we
should silently discard it. */
static int
-new_ready (next)
- rtx next ATTRIBUTE_UNUSED;
+new_ready (rtx next ATTRIBUTE_UNUSED)
{
return 1;
}
to be formatted so that multiple output lines will line up nicely. */
static const char *
-ebb_print_insn (insn, aligned)
- rtx insn;
- int aligned ATTRIBUTE_UNUSED;
+ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
{
static char tmp[80];
is to be preferred. Zero if they are equally good. */
static int
-rank (insn1, insn2)
- rtx insn1, insn2;
+rank (rtx insn1, rtx insn2)
{
basic_block bb1 = BLOCK_FOR_INSN (insn1);
basic_block bb2 = BLOCK_FOR_INSN (insn2);
calculations. */
static int
-contributes_to_priority (next, insn)
- rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
+contributes_to_priority (rtx next ATTRIBUTE_UNUSED,
+ rtx insn ATTRIBUTE_UNUSED)
{
return 1;
}
-/* INSN is a JUMP_INSN. Store the set of registers that must be considered
- to be set by this jump in SET. */
+ /* INSN is a JUMP_INSN, COND_SET is the set of registers that are
+ conditionally set before INSN. Store the set of registers that
+ must be considered as used by this jump in USED and that of
+ registers that must be considered as set in SET. */
static void
-compute_jump_reg_dependencies (insn, set)
- rtx insn;
- regset set;
+compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used,
+ regset set)
{
basic_block b = BLOCK_FOR_INSN (insn);
edge e;
for (e = b->succ; e; e = e->succ_next)
- if ((e->flags & EDGE_FALLTHRU) == 0)
- {
- bitmap_operation (set, set, e->dest->global_live_at_start,
- BITMAP_IOR);
- }
+ if (e->flags & EDGE_FALLTHRU)
+ /* The jump may be a by-product of a branch that has been merged
+ in the main codepath after being conditionalized. Therefore
+ it may guard the fallthrough block from using a value that has
+ conditionally overwritten that of the main codepath. So we
+ consider that it restores the value of the main codepath. */
+ bitmap_operation (set, e->dest->global_live_at_start, cond_set,
+ BITMAP_AND);
+ else
+ bitmap_operation (used, used, e->dest->global_live_at_start,
+ BITMAP_IOR);
}
/* Used in schedule_insns to initialize current_sched_info for scheduling
NULL, NULL,
NULL, NULL,
- 0, 1
+ 0, 1, 0
};
\f
/* It is possible that ebb scheduling eliminated some blocks.
Place blocks from FIRST to LAST before BEFORE. */
static void
-add_missing_bbs (before, first, last)
- rtx before;
- basic_block first, last;
+add_missing_bbs (rtx before, basic_block first, basic_block last)
{
for (; last != first->prev_bb; last = last->prev_bb)
{
before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before);
NOTE_BASIC_BLOCK (before) = last;
- last->head = before;
- last->end = before;
+ BB_HEAD (last) = before;
+ BB_END (last) = before;
update_bb_for_insn (last);
}
}
structures between BB and LAST. */
static basic_block
-fix_basic_block_boundaries (bb, last, head, tail)
- basic_block bb, last;
- rtx head, tail;
+fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head,
+ rtx tail)
{
rtx insn = head;
- rtx last_inside = bb->head;
+ rtx last_inside = BB_HEAD (bb);
rtx aftertail = NEXT_INSN (tail);
- head = bb->head;
+ head = BB_HEAD (bb);
for (; insn != aftertail; insn = NEXT_INSN (insn))
{
- if (GET_CODE (insn) == CODE_LABEL)
+ if (LABEL_P (insn))
abort ();
/* Create new basic blocks just before first insn. */
if (inside_basic_block_p (insn))
rtx note;
/* Re-emit the basic block note for newly found BB header. */
- if (GET_CODE (insn) == CODE_LABEL)
+ if (LABEL_P (insn))
{
note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn);
head = insn;
In this case we can create new basic block. It is
always exactly one basic block last in the sequence. Handle
it by splitting the edge and repositioning the block.
- This is somewhat hackish, but at least avoid cut&paste
+ This is somewhat hackish, but at least avoid cut&paste
- Safter sollution can be to bring the code into sequence,
+ A safer solution can be to bring the code into sequence,
do the split and re-emit it back in case this will ever
trigger problem. */
f = bb->prev_bb->succ;
if (f)
{
last = curr_bb = split_edge (f);
- h = curr_bb->head;
- curr_bb->head = head;
- curr_bb->end = insn;
+ h = BB_HEAD (curr_bb);
+ BB_HEAD (curr_bb) = head;
+ BB_END (curr_bb) = insn;
/* Edge splitting created misplaced BASIC_BLOCK note, kill
it. */
delete_insn (h);
delete_insn_chain (head, insn);
/* We keep some notes in the way that may split barrier from the
jump. */
- if (GET_CODE (next) == BARRIER)
+ if (BARRIER_P (next))
{
emit_barrier_after (prev_nonnote_insn (head));
delete_insn (next);
}
else
{
- curr_bb->head = head;
- curr_bb->end = insn;
- add_missing_bbs (curr_bb->head, bb, curr_bb->prev_bb);
+ BB_HEAD (curr_bb) = head;
+ BB_END (curr_bb) = insn;
+ add_missing_bbs (BB_HEAD (curr_bb), bb, curr_bb->prev_bb);
}
- note = GET_CODE (head) == CODE_LABEL ? NEXT_INSN (head) : head;
+ note = LABEL_P (head) ? NEXT_INSN (head) : head;
NOTE_BASIC_BLOCK (note) = curr_bb;
update_bb_for_insn (curr_bb);
bb = curr_bb->next_bb;
break;
}
}
- add_missing_bbs (last->next_bb->head, bb, last);
+ add_missing_bbs (BB_HEAD (last->next_bb), bb, last);
return bb->prev_bb;
}
blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */
static basic_block
-earliest_block_with_similiar_load (last_block, load_insn)
- basic_block last_block;
- rtx load_insn;
+earliest_block_with_similiar_load (basic_block last_block, rtx load_insn)
{
rtx back_link;
basic_block bb, earliest_block = NULL;
if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
/* insn2 not guaranteed to be a 1 base reg load. */
continue;
-
+
for (bb = last_block; bb; bb = bb->aux)
if (insn2_block == bb)
break;
return earliest_block;
}
-/* The following function adds dependecies between jumps and risky
+/* The following function adds dependencies between jumps and risky
insns in given ebb. */
static void
-add_deps_for_risky_insns (head, tail)
- rtx head, tail;
+add_deps_for_risky_insns (rtx head, rtx tail)
{
rtx insn, prev;
int class;
rtx last_jump = NULL_RTX;
rtx next_tail = NEXT_INSN (tail);
basic_block last_block = NULL, bb;
-
+
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
- if (GET_CODE (insn) == JUMP_INSN)
+ if (JUMP_P (insn))
{
bb = BLOCK_FOR_INSN (insn);
bb->aux = last_block;
bb = bb->aux;
if (!bb)
break;
- prev = bb->end;
+ prev = BB_END (bb);
}
}
- /* FALLTHRU */
+ /* Fall through. */
case TRAP_RISKY:
case IRISKY:
case PRISKY_CANDIDATE:
if (add_dependence (insn, prev, REG_DEP_ANTI))
add_forward_dependence (prev, insn, REG_DEP_ANTI);
break;
-
+
default:
break;
}
and TAIL. */
static basic_block
-schedule_ebb (head, tail)
- rtx head, tail;
+schedule_ebb (rtx head, rtx tail)
{
int n_insns;
basic_block b;
this pass. */
void
-schedule_ebbs (dump_file)
- FILE *dump_file;
+schedule_ebbs (FILE *dump_file)
{
basic_block bb;
+ int probability_cutoff;
+
+ if (profile_info && flag_branch_probabilities)
+ probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
+ else
+ probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY);
+ probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff;
/* Taking care of this degenerate case makes the rest of
this code simpler. */
current_sched_info = &ebb_sched_info;
- allocate_reg_life_data ();
compute_bb_for_insn ();
/* Schedule every region in the subroutine. */
FOR_EACH_BB (bb)
{
- rtx head = bb->head;
+ rtx head = BB_HEAD (bb);
rtx tail;
for (;;)
{
edge e;
- tail = bb->end;
+ tail = BB_END (bb);
if (bb->next_bb == EXIT_BLOCK_PTR
- || GET_CODE (bb->next_bb->head) == CODE_LABEL)
+ || LABEL_P (BB_HEAD (bb->next_bb)))
break;
for (e = bb->succ; e; e = e->succ_next)
if ((e->flags & EDGE_FALLTHRU) != 0)
break;
if (! e)
break;
- if (e->probability < REG_BR_PROB_BASE / 2)
+ if (e->probability <= probability_cutoff)
break;
bb = bb->next_bb;
}
a note or two. */
while (head != tail)
{
- if (GET_CODE (head) == NOTE)
+ if (NOTE_P (head))
head = NEXT_INSN (head);
- else if (GET_CODE (tail) == NOTE)
+ else if (NOTE_P (tail))
tail = PREV_INSN (tail);
- else if (GET_CODE (head) == CODE_LABEL)
+ else if (LABEL_P (head))
head = NEXT_INSN (head);
else
break;