This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Patch: Scheduler support for IA-64 speculation [5/5]
- From: Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>
- To: gcc-patches at gcc dot gnu dot org
- Cc: "Vladimir N. Makarov" <vmakarov at redhat dot com>, Jim Wilson <wilson at specifixinc dot com>, Andrey Belevantsev <abel at ispras dot ru>
- Date: Fri, 30 Dec 2005 15:18:03 +0300
- Subject: Patch: Scheduler support for IA-64 speculation [5/5]
Hi,
This patch adds support for IA-64 data/control speculation to haifa
scheduler.
By default, conservative approach is used to choose instruction for
speculative scheduling (i.e. only after reload and only if there
are no non-speculative instructions in the ready list). This approach
gives no performance regressions on both SPECint and SPECfp, while
still shows improvement of gap (+4.9%), amp (+10%), mesa (+1%) and mgrid
(+1%).
INSN_PRIORITY computation should be fixed to make it possible to
use non-conservative strategy on speculation.
The expense of using speculation is approximately 1.7% of bootstrap time.
The patch was bootstrapped and regtested on the 20051125 weekly snapshot
on ia64-linux and i686-linux, and bootstrapped and regtested on the
20051224 weekly snapshot on i686-linux.
Ok for mainline?
Thanks, Maxim
2005-12-30 Maxim Kuvyrkov <mkuvyrkov@ispras.ru>
* target.h (rtl.h): New include.
(struct spec_info_def): New opaque declaration.
(struct gcc_target.sched): New fields: adjust_cost_2, h_i_d_extended,
speculate_insn, need_block_p, gen_check,
first_cycle_multipass_dfa_lookahead_guard_spec, set_sched_flags.
* target-def.h (TARGET_SCHED_ADJUST_COST_2,
TARGET_SCHED_H_I_D_EXTENDED, TARGET_SCHED_SPECULATE_INSN,
TARGET_SCHED_NEEDS_BLOCK_P, TARGET_SCHED_GEN_CHECK,
TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD_GUARD_SPEC,
TARGET_SCHED_SET_SCHED_FLAGS): New macros to initialize fields in
gcc_target.sched.
(TARGET_SCHED): Use new macros.
* rtl.h (copy_DEPS_LIST_list): New prototype.
* sched-int.h (struct sched_info): Change signature of new_ready field,
adjust all initializations. New fields: add_remove_insn,
begin_schedule_ready, insn_points, add_block, advance_target_bb,
fix_recovery_cfg, region_head_or_leaf_p.
(struct spec_info_def): New structure declaration.
(spec_info_t): New typedef.
(struct haifa_insn_data): New fields: todo_spec, done_spec, check_spec,
insn_anti_points, recovery_block, orig_pat, check_no.
(glat_start, glat_end): New variables declaraions.
(TODO_SPEC, DONE_SPEC, CHECK_SPEC, INSN_POINTS, SET_INSN_POINTS,
RECOVERY_BLOCK, ORIG_PAT, CHECK_NO): New access macros.
(enum SCHED_FLAGS): New constants: SCHED_RGN, SCHED_EBB,
DETACH_LIFE_INFO, USE_GLAT.
(enum SPEC_SCHED_FLAGS): New enumeration.
(MIN_SCHED_POINTS, MAX_SCHED_POINTS, NOTE_NOTE_BB_P): New macros.
(extend_dependency_caches, xrecalloc, unlink_bb_notes, add_block,
attach_life_info, debug_spec_status, check_reg_live): New functions.
(get_block_head_tail): Change signature to get_ebb_head_tail, adjust
all uses in ddg.c, modulo-sched.c, haifa-sched.c, sched-rgn.c,
sched-ebb.c
* ddg.c (get_block_head_tail): Adjust all uses.
* modulo-sched.c (get_block_head_tail): Adjust all uses.
* haifa-sched.c (get_block_head_tail): Adjust all uses.
(ISSUE_POINTS): New macros.
(spec_info_var, spec_info, glat_start, glat_end): New global variables.
(nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control,
bb_header, old_last_basic_block, before_recovery,
current_sched_info_var): New static variables.
(insn_cost1): New function. Move logic from insn_cost to here.
(find_insn_reg_weight1): New function. Move logic from
find_insn_reg_weight to here.
(reemit_notes, ready_add, move_insn, max_issue): Change signature.
(ready_add_first, move_insn1): Removed.
(extend_h_i_d, extend_ready, extend_global, extend_all, init_h_i_d,
extend_bb): New static functions to support extension of scheduler's
data structures.
(generate_recovery_code, process_insn_depend_be_in_spec,
begin_speculative_block, add_to_speculative_block,
init_before_recovery, create_recovery_block, create_check_block_twin,
fix_recovery_deps): New static functions to support
generation of recovery code.
(fix_jump_move, find_fallthru_edge, dump_new_block_header,
restore_bb_notes, move_block_after_check, move_succs): New static
functions to support ebb scheduling.
(init_glat, init_glat1, attach_life_info1, free_glat): New static
functions to support handling of register live information.
(insn_points, associate_line_notes_with_blocks, change_pattern,
speculate_insn, sched_remove_insn, clear_priorities,
calc_priorities): New static functions.
(check_cfg, has_edge_p, check_sched_flags, dump_spec_status): New
static functions for consistancy checking.
(move_insn): Added code to handle ebb scheduling.
(max_issue): Added code to choose between speculative and
non-speculative instructions.
(schedule_block): Added code to handle ebb scheduling and scheduling of
speculative instructions.
(sched_init): Initialize new variables.
(sched_finish): Free new variables. Print statistics.
(try_ready): Added code to handle speculative instructions.
* lists.c (copy_DEPS_LIST_list): New function.
* sched-deps.c (extend_dependency_caches): New function. Move logic
from create_dependency_caches to here.
* genattr.c (main): Code to output prototype for
dfa_clear_single_insn_cache.
* genautomata.c (DFA_CLEAR_SINGLE_INSN_CACHE_FUNC_NAME): New macros.
(output_dfa_clean_insn_cache_func): Code to output
dfa_clear_single_insn_cache function.
* sched-ebb.c (get_block_head_tail): Adjust all uses.
(n_insns, dont_calc_deps, ebb_head, ebb_tail, last_bb, max_frequency):
New static variables.
(can_schedule_ready_p, fix_basic_block_boundaries, add_missing_bbs):
Removed.
(begin_schedule_ready, add_remove_insn, insn_points, add_block1,
advance_target_bb, fix_recovery_cfg, ebb_head_or_leaf_p): Implement
hooks from struct sched_info.
(ebb_sched_info): Initialize new fields.
(schedule_ebbs): Added code to update register live information.
* sched-rgn.c (get_block_head_tail): Adjust all uses.
(struct region): New fields: dont_calc_deps, has_real_ebb.
(RGN_DONT_CALC_DEPS, RGN_HAS_REAL_EBB): New access macros.
(BB_TO_BLOCK): Fixed to handle EBBs.
(EBB_FIRST_BB, EBB_LAST_BB): New macros.
(ebb_head): New static variable.
(debug_regions): Fixed to handles EBBs.
(find_rgns, find_more_rgns): Initialize new fields.
(check_live_1, update_live_1): Fixed to work with glat_start instead of
global_live_at_start.
(begin_schedule_ready_p, new_ready, add_remove_insn, insn_points,
extend_regions, add_block1, fix_recovery_cfg, advance_target_bb,
region_head_or_leaf_p): Implement new hooks.
(check_dead_notes1): New static function.
(schedule_regions): Fixed code that updates register live information
to handle EBBs.
(schedule_region): Fixed to handle EBBs.
* params.def (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY,
PARAM_SCHED_SPEC_POINTS_CUTOFF): New parameters.
* invoke.texi (max-sched-insn-conflict-delay, spec-points-cutoff):
Document.
Index: gcc/sched-ebb.c
===================================================================
--- gcc/sched-ebb.c (.../insn-tick) (revision 2239)
+++ gcc/sched-ebb.c (.../recovery) (revision 2239)
@@ -47,9 +47,23 @@ static int target_n_insns;
/* The number of insns scheduled so far. */
static int sched_n_insns;
+/* The number of insns to be scheduled in total. */
+static int n_insns;
+
+/* Set of blocks, that already have their dependencies calculated. */
+static bitmap_head dont_calc_deps;
+/* Set of basic blocks, that are ebb heads of tails respectively. */
+static bitmap_head ebb_head, ebb_tail;
+
+/* Last basic block in current ebb. */
+static basic_block last_bb;
+
+/* The maximal frequency of all basic block in current ebb. */
+static int max_frequency;
+
/* Implementations of the sched_info functions for region scheduling. */
static void init_ready_list (void);
-static int can_schedule_ready_p (rtx);
+static void begin_schedule_ready (rtx, rtx);
static int schedule_more_p (void);
static const char *ebb_print_insn (rtx, int);
static int rank (rtx, rtx);
@@ -58,9 +72,16 @@ static void compute_jump_reg_dependencie
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);
+
+static void add_remove_insn (rtx, int);
+static int insn_points (rtx, int);
+static void add_block1 (basic_block, basic_block);
+static basic_block advance_target_bb (basic_block, rtx);
+static void fix_recovery_cfg (int, int, int);
+
+#ifdef ENABLE_CHECKING
+static int ebb_head_or_leaf_p (basic_block, int);
+#endif
/* Return nonzero if there are more insns that should be scheduled. */
@@ -98,14 +119,75 @@ init_ready_list (void)
}
}
-/* Called after taking INSN from the ready list. Returns nonzero if this
- insn can be scheduled, nonzero if we should silently discard it. */
+/* INSN is being scheduled - update counters. */
-static int
-can_schedule_ready_p (rtx insn ATTRIBUTE_UNUSED)
+static void
+begin_schedule_ready (rtx insn, rtx last)
{
sched_n_insns++;
- return 1;
+
+ if (control_flow_insn_p (insn)
+ && last != PREV_INSN (insn)
+ && BLOCK_FOR_INSN (last) == last_bb)
+ {
+ edge e;
+ edge_iterator ei;
+ basic_block bb;
+
+ /* An obscure special case, where we do have partially dead
+ instruction scheduled after last control flow instruction.
+ 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
+
+ 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. */
+
+ gcc_assert (BLOCK_FOR_INSN (insn) == last_bb
+ && !RECOVERY_BLOCK (insn)
+ && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (last));
+
+ /* We don't use split_edge() now because it has an issue, with
+ miltiple NOTE_INSN_LOOP_BEG before e->dest: it creates new
+ basic block before _first_ such note. When we splitting fallthru
+ edge, it is clear, that we should create basic block before _all_
+ NOTE_INSN_LOOP_BEG notes. May be this is a bug in cfgrtl.c. But
+ I am not sure. */
+
+ FOR_EACH_EDGE (e, ei, last_bb->succs)
+ if (e->flags & EDGE_FALLTHRU)
+ break;
+
+ insn = NEXT_INSN (insn);
+
+ if (e)
+ gcc_assert (NOTE_P (insn)
+ || LABEL_P (insn));
+ else
+ {
+ gcc_assert (BARRIER_P (insn));
+ insn = NEXT_INSN (insn);
+ }
+
+ bb = create_basic_block (insn, 0, last_bb);
+
+ if (e)
+ {
+ gcc_assert (!(e->flags & EDGE_COMPLEX));
+
+ BB_COPY_PARTITION (bb, last_bb);
+ redirect_edge_succ (e, bb);
+ /* May be (EDGE_FALLTHRU | EDGE_CAN_FALLTHRU)? If yes, fix in
+ cfgrtl.c: split_edge() too. */
+ make_single_succ_edge (bb, bb->next_bb, EDGE_FALLTHRU);
+ }
+
+ add_block (bb, last_bb);
+
+ last_bb = bb;
+ }
}
/* Return a string that contains the insn uid and optionally anything else
@@ -172,9 +254,9 @@ compute_jump_reg_dependencies (rtx insn,
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_and (set, e->dest->il.rtl->global_live_at_start, cond_set);
+ bitmap_and (set, glat_start [e->dest->index], cond_set);
else
- bitmap_ior_into (used, e->dest->il.rtl->global_live_at_start);
+ bitmap_ior_into (used, glat_start [e->dest->index]);
}
/* Used in schedule_insns to initialize current_sched_info for scheduling
@@ -183,7 +265,7 @@ compute_jump_reg_dependencies (rtx insn,
static struct sched_info ebb_sched_info =
{
init_ready_list,
- can_schedule_ready_p,
+ NULL,
schedule_more_p,
NULL,
rank,
@@ -195,143 +277,20 @@ static struct sched_info ebb_sched_info
NULL, NULL,
0, 1, 0,
- 0
+ add_remove_insn,
+ begin_schedule_ready,
+ insn_points,
+ add_block1,
+ advance_target_bb,
+ fix_recovery_cfg,
+#ifdef ENABLE_CHECKING
+ ebb_head_or_leaf_p,
+#endif
+ /* We need to DETACH_LIVE_INFO to be able to create new basic blocks.
+ See begin_schedule_ready (). */
+ SCHED_EBB | USE_GLAT | DETACH_LIFE_INFO
};
-/* It is possible that ebb scheduling eliminated some blocks.
- Place blocks from FIRST to LAST before BEFORE. */
-
-static void
-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;
- BB_HEAD (last) = before;
- BB_END (last) = before;
- update_bb_for_insn (last);
- }
-}
-
-/* Fixup the CFG after EBB scheduling. Re-recognize the basic
- block boundaries in between HEAD and TAIL and update basic block
- structures between BB and LAST. */
-
-static basic_block
-fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head,
- rtx tail)
-{
- rtx insn = head;
- rtx last_inside = BB_HEAD (bb);
- rtx aftertail = NEXT_INSN (tail);
-
- head = BB_HEAD (bb);
-
- for (; insn != aftertail; insn = NEXT_INSN (insn))
- {
- gcc_assert (!LABEL_P (insn));
- /* Create new basic blocks just before first insn. */
- if (inside_basic_block_p (insn))
- {
- if (!last_inside)
- {
- rtx note;
-
- /* Re-emit the basic block note for newly found BB header. */
- if (LABEL_P (insn))
- {
- note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn);
- head = insn;
- last_inside = note;
- }
- else
- {
- note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn);
- head = note;
- last_inside = insn;
- }
- }
- else
- last_inside = insn;
- }
- /* Control flow instruction terminate basic block. It is possible
- that we've eliminated some basic blocks (made them empty).
- Find the proper basic block using BLOCK_FOR_INSN and arrange things in
- a sensible way by inserting empty basic blocks as needed. */
- if (control_flow_insn_p (insn) || (insn == tail && last_inside))
- {
- basic_block curr_bb = BLOCK_FOR_INSN (insn);
- rtx note;
-
- if (!control_flow_insn_p (insn))
- curr_bb = last;
- if (bb == last->next_bb)
- {
- edge f;
- rtx h;
- edge_iterator ei;
-
- /* An obscure special case, where we do have partially dead
- instruction scheduled after last control flow instruction.
- 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
-
- 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. */
-
- FOR_EACH_EDGE (f, ei, bb->prev_bb->succs)
- if (f->flags & EDGE_FALLTHRU)
- break;
-
- if (f)
- {
- last = curr_bb = split_edge (f);
- 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);
- }
- /* It may happen that code got moved past unconditional jump in
- case the code is completely dead. Kill it. */
- else
- {
- rtx next = next_nonnote_insn (insn);
- delete_insn_chain (head, insn);
- /* We keep some notes in the way that may split barrier from the
- jump. */
- if (BARRIER_P (next))
- {
- emit_barrier_after (prev_nonnote_insn (head));
- delete_insn (next);
- }
- insn = NULL;
- }
- }
- else
- {
- BB_HEAD (curr_bb) = head;
- BB_END (curr_bb) = insn;
- add_missing_bbs (BB_HEAD (curr_bb), bb, curr_bb->prev_bb);
- }
- 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;
- last_inside = NULL;
- if (!insn)
- break;
- }
- }
- add_missing_bbs (BB_HEAD (last->next_bb), bb, last);
- return bb->prev_bb;
-}
-
/* Returns the earliest block in EBB currently being processed where a
"similar load" 'insn2' is found, and hence LOAD_INSN can move
speculatively into the found block. All the following must hold:
@@ -411,7 +370,7 @@ add_deps_for_risky_insns (rtx head, rtx
basic_block last_block = NULL, bb;
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
- if (JUMP_P (insn))
+ if (control_flow_insn_p (insn))
{
bb = BLOCK_FOR_INSN (insn);
bb->aux = last_block;
@@ -486,33 +445,63 @@ add_deps_for_risky_insns (rtx head, rtx
static basic_block
schedule_ebb (rtx head, rtx tail)
{
- int n_insns;
basic_block b;
struct deps tmp_deps;
basic_block first_bb = BLOCK_FOR_INSN (head);
- basic_block last_bb = BLOCK_FOR_INSN (tail);
+ last_bb = BLOCK_FOR_INSN (tail);
if (no_real_insns_p (head, tail))
return BLOCK_FOR_INSN (tail);
- init_deps_global ();
+ gcc_assert (INSN_P (head) && INSN_P (tail));
+
+ if (!bitmap_bit_p (&dont_calc_deps, first_bb->index))
+ {
+ init_deps_global ();
+
+ /* Compute LOG_LINKS. */
+ init_deps (&tmp_deps);
+ sched_analyze (&tmp_deps, head, tail);
+ free_deps (&tmp_deps);
- /* Compute LOG_LINKS. */
- init_deps (&tmp_deps);
- sched_analyze (&tmp_deps, head, tail);
- free_deps (&tmp_deps);
+ /* Compute INSN_DEPEND. */
+ compute_forward_dependences (head, tail);
- /* Compute INSN_DEPEND. */
- compute_forward_dependences (head, tail);
+ add_deps_for_risky_insns (head, tail);
- add_deps_for_risky_insns (head, tail);
+ if (targetm.sched.dependencies_evaluation_hook)
+ targetm.sched.dependencies_evaluation_hook (head, tail);
- if (targetm.sched.dependencies_evaluation_hook)
- targetm.sched.dependencies_evaluation_hook (head, tail);
+ finish_deps_global ();
+ }
+ else
+ /* Only recovery blocks can have their dependencies already calculated,
+ and they always are single block ebbs. */
+ gcc_assert (first_bb == last_bb);
/* Set priorities. */
n_insns = set_priorities (head, tail);
+ /* Calculate MAX_FREQUENCY. */
+ max_frequency = first_bb->frequency;
+ if (first_bb != last_bb)
+ {
+ basic_block bb = first_bb;
+
+ do
+ {
+ bb = bb->next_bb;
+ if (bb->frequency > max_frequency)
+ max_frequency = bb->frequency;
+ }
+ while (bb != last_bb);
+ }
+
+ if (max_frequency > BB_FREQ_MAX
+ || max_frequency <= 0)
+ /* Sometimes this happens... */
+ max_frequency = BB_FREQ_MAX;
+
current_sched_info->prev_head = PREV_INSN (head);
current_sched_info->next_tail = NEXT_INSN (tail);
@@ -542,10 +531,16 @@ schedule_ebb (rtx head, rtx tail)
schedule_block (). */
rm_other_notes (head, tail);
+ unlink_bb_notes (first_bb, last_bb);
+
current_sched_info->queue_must_finish_empty = 1;
- schedule_block (-1, n_insns);
+ b = first_bb;
+ schedule_block (&b, &n_insns);
+ /* We might pack all instructions into fewer blocks,
+ so we may made some of them empty. Can't assert (b == last_bb). */
+
/* Sanity check: verify that all region insns were scheduled. */
gcc_assert (sched_n_insns == n_insns);
head = current_sched_info->head;
@@ -553,10 +548,17 @@ schedule_ebb (rtx head, rtx tail)
if (write_symbols != NO_DEBUG)
restore_line_notes (head, tail);
- b = fix_basic_block_boundaries (first_bb, last_bb, head, tail);
- finish_deps_global ();
- return b;
+ if (EDGE_COUNT (last_bb->preds) == 0)
+ /* LAST_BB is unreachable. */
+ {
+ gcc_assert (first_bb != last_bb
+ && EDGE_COUNT (last_bb->succs) == 0);
+ last_bb = last_bb->prev_bb;
+ delete_basic_block (last_bb->next_bb);
+ }
+
+ return last_bb;
}
/* The one entry point in this file. DUMP_FILE is the dump file for
@@ -567,6 +569,9 @@ schedule_ebbs (FILE *dump_file)
{
basic_block bb;
int probability_cutoff;
+ rtx tail;
+ sbitmap large_region_blocks, blocks;
+ int any_large_regions;
if (profile_info && flag_branch_probabilities)
probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK);
@@ -587,11 +592,18 @@ schedule_ebbs (FILE *dump_file)
compute_bb_for_insn ();
+ /* Initialize DONT_CALC_DEPS and ebb-{start, end} markers. */
+ bitmap_initialize (&dont_calc_deps, 0);
+ bitmap_clear (&dont_calc_deps);
+ bitmap_initialize (&ebb_head, 0);
+ bitmap_clear (&ebb_head);
+ bitmap_initialize (&ebb_tail, 0);
+ bitmap_clear (&ebb_tail);
+
/* Schedule every region in the subroutine. */
FOR_EACH_BB (bb)
{
rtx head = BB_HEAD (bb);
- rtx tail;
for (;;)
{
@@ -625,11 +637,71 @@ schedule_ebbs (FILE *dump_file)
break;
}
+ bitmap_set_bit (&ebb_head, BLOCK_NUM (head));
bb = schedule_ebb (head, tail);
+ bitmap_set_bit (&ebb_tail, bb->index);
}
+ bitmap_clear (&dont_calc_deps);
- /* Updating life info can be done by local propagation over the modified
- superblocks. */
+ gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO);
+ /* We can create new basic blocks during scheduling, and
+ attach_life_info () will create regsets for them
+ (along with attaching existing info back). */
+ attach_life_info ();
+
+ /* Updating register live information. */
+ allocate_reg_life_data ();
+
+ any_large_regions = 0;
+ large_region_blocks = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (large_region_blocks);
+ FOR_EACH_BB (bb)
+ SET_BIT (large_region_blocks, bb->index);
+
+ blocks = sbitmap_alloc (last_basic_block);
+ sbitmap_zero (blocks);
+
+ /* Update life information. For regions consisting of multiple blocks
+ we've possibly done interblock scheduling that affects global liveness.
+ For regions consisting of single blocks we need to do only local
+ liveness. */
+ FOR_EACH_BB (bb)
+ {
+ int bbi;
+
+ bbi = bb->index;
+
+ if (!bitmap_bit_p (&ebb_head, bbi)
+ || !bitmap_bit_p (&ebb_tail, bbi)
+ /* New blocks (e.g. recovery blocks) should be processed
+ as parts of large regions. */
+ || !glat_start[bbi])
+ any_large_regions = 1;
+ else
+ {
+ SET_BIT (blocks, bbi);
+ RESET_BIT (large_region_blocks, bbi);
+ }
+ }
+
+ update_life_info (blocks, UPDATE_LIFE_LOCAL, 0);
+ sbitmap_free (blocks);
+
+ if (any_large_regions)
+ {
+ update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL, 0);
+
+#ifdef ENABLE_CHECKING
+ /* !!! We can't check reg_live_info here because of the fact,
+ that destination registers of COND_EXEC's may be dead
+ before scheduling (while they should be alive). Don't know why. */
+ /*check_reg_live ();*/
+#endif
+ }
+ sbitmap_free (large_region_blocks);
+
+ bitmap_clear (&ebb_head);
+ bitmap_clear (&ebb_tail);
/* Reposition the prologue and epilogue notes in case we moved the
prologue/epilogue insns. */
@@ -641,3 +713,80 @@ schedule_ebbs (FILE *dump_file)
sched_finish ();
}
+
+/* INSN has been added to/removed from current ebb. */
+static void
+add_remove_insn (rtx insn ATTRIBUTE_UNUSED, int remove_p)
+{
+ if (!remove_p)
+ target_n_insns++;
+ else
+ target_n_insns--;
+}
+
+/* Adjust INSN_POINTS. */
+static int
+insn_points (rtx insn, int points)
+{
+ return (points * BLOCK_FOR_INSN (insn)->frequency) / max_frequency;
+}
+
+/* BB was added to ebb after AFTER. */
+static void
+add_block1 (basic_block bb, basic_block after)
+{
+ /* Recovery blocks are always bounded by BARRIERS,
+ therefore, they always form single block EBB,
+ therefore, we can use rec->index to identify such EBBs. */
+ if (after == EXIT_BLOCK_PTR)
+ bitmap_set_bit (&dont_calc_deps, bb->index);
+ else if (after == last_bb)
+ last_bb = bb;
+}
+
+/* Return next block in ebb chain. */
+static basic_block
+advance_target_bb (basic_block bb, rtx insn)
+{
+ if (insn)
+ {
+ if (BLOCK_FOR_INSN (insn) != bb
+ && control_flow_insn_p (insn)
+ && !RECOVERY_BLOCK (insn)
+ && !RECOVERY_BLOCK (BB_END (bb)))
+ {
+ gcc_assert (!control_flow_insn_p (BB_END (bb))
+ && NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (bb->next_bb)));
+ return bb;
+ }
+ else
+ return 0;
+ }
+ else if (bb != last_bb)
+ return bb->next_bb;
+ else
+ gcc_unreachable ();
+}
+
+/* Fix internal data after interblock movement of jump instruction. */
+static void
+fix_recovery_cfg (int bbi ATTRIBUTE_UNUSED,
+ int jump_bbi ATTRIBUTE_UNUSED,
+ int jump_bb_nexti)
+{
+ gcc_assert (last_bb->index != bbi);
+
+ if (jump_bb_nexti == last_bb->index)
+ last_bb = BASIC_BLOCK (jump_bbi);
+}
+
+#ifdef ENABLE_CHECKING
+static int
+ebb_head_or_leaf_p (basic_block bb, int leaf_p)
+{
+ if (!leaf_p)
+ return bitmap_bit_p (&ebb_head, bb->index);
+ else
+ return bitmap_bit_p (&ebb_tail, bb->index);
+}
+#endif /* ENABLE_CHECKING */
Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi (.../insn-tick) (revision 2239)
+++ gcc/doc/invoke.texi (.../recovery) (revision 2239)
@@ -6119,6 +6119,15 @@ The maximum number of iterations through
N - do at most N iterations.
The default value is 2.
+@item max-sched-insn-conflict-delay
+The maximum conflict delay for an insn to be considered for speculative motion.
+The default value is 3.
+
+@item sched-spec-points-cutoff
+The minimum number of points the speculative instruction should
+get to be scheduled.
+The default value is 100.
+
@item max-last-value-rtl
The maximum size measured as number of RTLs that can be recorded in an expression
Index: gcc/target.h
===================================================================
--- gcc/target.h (.../insn-tick) (revision 2239)
+++ gcc/target.h (.../recovery) (revision 2239)
@@ -49,8 +49,11 @@ Foundation, 51 Franklin Street, Fifth Fl
#include "tm.h"
#include "insn-modes.h"
+/* For enum reg_note. */
+#include "rtl.h"
struct stdarg_info;
+struct spec_info_def;
/* The struct used by the secondary_reload target hook. */
typedef struct secondary_reload_info
@@ -299,6 +302,52 @@ struct gcc_target
between the already scheduled insn (first parameter) and the
the second insn (second parameter). */
bool (* is_costly_dependence) (rtx, rtx, rtx, int, int);
+
+ /* Given the current cost, COST, of an insn, INSN, calculate and
+ return a new cost based on its relationship to DEP_INSN through the
+ dependence of type DEP_TYPE. The default is to make no adjustment. */
+ int (* adjust_cost_2) (rtx insn, enum reg_note, rtx def_insn, int cost);
+
+ /* The following member value is a pointer to a function called
+ by the insn scheduler. This hook is called to notify backend,
+ that new instructions were emitted. */
+ void (* h_i_d_extended) (void);
+
+ /* The following member value is a pointer to a function called
+ by the insn scheduler. It should return 1, if instruction has
+ speculative form, or -1, if it hasn't. The first parameter is
+ instruction, the second parameter is type of requested speculation,
+ and the third parameter is a pointer to the pattern of corresponding
+ speculative instruction (set if return value == 1). */
+ int (* speculate_insn) (rtx, int, rtx *);
+
+ /* The following member value is a pointer to a function called
+ by the insn scheduler. It should return nonzero, if check instruction,
+ passed as parameter, needs a recovery block. */
+ int (* needs_block_p) (rtx);
+
+ /* The following member value is a pointer to a function called
+ by the insn scheduler. It should return pattern for check instruction.
+ The first parameter is speculative instruction, the second parameter
+ is label of corresponding recovery block (or null, if simple check
+ requested). The third parameter is nonzero, if mutation of check
+ requested (e.i. from ld.c to chk.a) - in this case the first parameter
+ is previous check. */
+ rtx (* gen_check) (rtx, rtx, int);
+
+ /* The following member value is pointer to a function controlling
+ what insns from the ready insn queue will be considered for the
+ multipass insn scheduling. If the hook returns zero for insn
+ passed as the parameter, the insn will be not chosen to be
+ issued. This hook is used to discard speculative instructions,
+ that stand at the first position of the ready list. */
+ int (* first_cycle_multipass_dfa_lookahead_guard_spec) (rtx);
+
+ /* The following member value is pointer to a function, that provides
+ information about speculation capabilities of the target.
+ First parameter is pointer to 'flags' field of current_sched_info.
+ Second parameter is pointer to spec_info variable. */
+ void (* set_sched_flags) (unsigned int *, struct spec_info_def *);
} sched;
/* Functions relating to vectorization. */
Index: gcc/ddg.c
===================================================================
--- gcc/ddg.c (.../insn-tick) (revision 2239)
+++ gcc/ddg.c (.../recovery) (revision 2239)
@@ -379,7 +379,7 @@ build_intra_loop_deps (ddg_ptr g)
init_deps (&tmp_deps);
/* Do the intra-block data dependence analysis for the given block. */
- get_block_head_tail (g->bb->index, &head, &tail);
+ get_ebb_head_tail (g->bb, g->bb, &head, &tail);
sched_analyze (&tmp_deps, head, tail);
/* Build intra-loop data dependencies using the scheduler dependency
Index: gcc/lists.c
===================================================================
--- gcc/lists.c (.../insn-tick) (revision 2239)
+++ gcc/lists.c (.../recovery) (revision 2239)
@@ -250,4 +250,21 @@ remove_free_INSN_LIST_elem (rtx elem, rt
free_INSN_LIST_node (remove_list_elem (elem, listp));
}
+/* Create and return a copy of the DEPS_LIST LIST. */
+rtx
+copy_DEPS_LIST_list (rtx list)
+{
+ rtx res = 0, *resp = &res;
+
+ while (list)
+ {
+ *resp = alloc_DEPS_LIST (XEXP (list, 0), 0, XINT (list, 2),
+ XINT (list, 3));
+ PUT_REG_NOTE_KIND (*resp, REG_NOTE_KIND (list));
+ resp = &XEXP (*resp, 1);
+ list = XEXP (list, 1);
+ }
+ return res;
+}
+
#include "gt-lists.h"
Index: gcc/genautomata.c
===================================================================
--- gcc/genautomata.c (.../insn-tick) (revision 2239)
+++ gcc/genautomata.c (.../recovery) (revision 2239)
@@ -7422,6 +7422,8 @@ output_reserved_units_table_name (FILE *
#define DFA_CLEAN_INSN_CACHE_FUNC_NAME "dfa_clean_insn_cache"
+#define DFA_CLEAR_SINGLE_INSN_CACHE_FUNC_NAME "dfa_clear_single_insn_cache"
+
#define DFA_START_FUNC_NAME "dfa_start"
#define DFA_FINISH_FUNC_NAME "dfa_finish"
@@ -9046,7 +9048,8 @@ output_cpu_unit_reservation_p (void)
fprintf (output_file, " return 0;\n}\n\n");
}
-/* The function outputs PHR interface function `dfa_clean_insn_cache'. */
+/* The function outputs PHR interface functions `dfa_clean_insn_cache'
+ and 'dfa_clear_single_insn_cache'. */
static void
output_dfa_clean_insn_cache_func (void)
{
@@ -9058,6 +9061,16 @@ output_dfa_clean_insn_cache_func (void)
I_VARIABLE_NAME, I_VARIABLE_NAME,
DFA_INSN_CODES_LENGTH_VARIABLE_NAME, I_VARIABLE_NAME,
DFA_INSN_CODES_VARIABLE_NAME, I_VARIABLE_NAME);
+
+ fprintf (output_file,
+ "void\n%s (rtx %s)\n{\n int %s;\n\n",
+ DFA_CLEAR_SINGLE_INSN_CACHE_FUNC_NAME, INSN_PARAMETER_NAME,
+ I_VARIABLE_NAME);
+ fprintf (output_file,
+ " %s = INSN_UID (%s);\n if (%s < %s)\n %s [%s] = -1;\n}\n\n",
+ I_VARIABLE_NAME, INSN_PARAMETER_NAME, I_VARIABLE_NAME,
+ DFA_INSN_CODES_LENGTH_VARIABLE_NAME, DFA_INSN_CODES_VARIABLE_NAME,
+ I_VARIABLE_NAME);
}
/* The function outputs PHR interface function `dfa_start'. */
Index: gcc/haifa-sched.c
===================================================================
--- gcc/haifa-sched.c (.../insn-tick) (revision 2239)
+++ gcc/haifa-sched.c (.../recovery) (revision 2239)
@@ -196,6 +196,10 @@ struct haifa_insn_data *h_i_d;
#define RESOLVED_DEPS(INSN) (h_i_d[INSN_UID (INSN)].resolved_deps)
+#define ISSUE_POINTS(INSN)\
+ ((spec_info && (spec_info->flags & USE_ISSUE_POINTS)) ?\
+ INSN_POINTS (INSN) : MAX_SCHED_POINTS)
+
/* Vector indexed by basic block number giving the starting line-number
for each basic block. */
static rtx *line_note_head;
@@ -204,6 +208,30 @@ static rtx *line_note_head;
last element in the list. */
static rtx note_list;
+struct spec_info_def spec_info_var;
+/* Description of the speculative part of the scheduling.
+ If NULL - no speculation. */
+spec_info_t spec_info;
+
+/* True, if recovery block was added during scheduling of current block.
+ Used to determine, if we need to fix INSN_TICKs. */
+static int added_recovery_block_p;
+
+/* Counters of different types of speculative isntructions. */
+static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
+
+/* Pointers to GLAT data. See init_glat for more information. */
+regset *glat_start, *glat_end;
+
+/* Array used in {unlink, restore}_bb_notes. */
+static rtx *bb_header = 0;
+
+/* Number of basic_blocks. */
+static int old_last_basic_block;
+
+/* Basic block after which recovery blocks will be created. */
+static basic_block before_recovery;
+
/* Queues, etc. */
/* An instruction is ready to be scheduled when all insns preceding it
@@ -244,7 +272,7 @@ static rtx note_list;
/* Implement a circular buffer to delay instructions until sufficient
time has passed. For the new pipeline description interface,
- MAX_INSN_QUEUE_INDEX is a power of two minus one which is larger
+ MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
than maximal time of instruction execution computed by genattr.c on
the base maximal time of functional unit reservations and getting a
result. This is the longest time an insn may be queued. */
@@ -463,13 +491,15 @@ haifa_classify_insn (rtx insn)
/* Forward declarations. */
+HAIFA_INLINE static int insn_cost1 (rtx, enum reg_note, rtx, rtx);
static int priority (rtx);
static int rank_for_schedule (const void *, const void *);
static void swap_sort (rtx *, int);
static void queue_insn (rtx, int);
static int schedule_insn (rtx);
static int find_set_reg_weight (rtx);
-static void find_insn_reg_weight (int);
+static void find_insn_reg_weight (basic_block);
+static void find_insn_reg_weight1 (rtx);
static void adjust_priority (rtx);
static void advance_one_cycle (void);
@@ -498,11 +528,10 @@ static void advance_one_cycle (void);
static rtx unlink_other_notes (rtx, rtx);
static rtx unlink_line_notes (rtx, rtx);
-static rtx reemit_notes (rtx, rtx);
+static void reemit_notes (rtx);
static rtx *ready_lastpos (struct ready_list *);
-static void ready_add (struct ready_list *, rtx);
-static void ready_add_first (struct ready_list *, rtx);
+static void ready_add (struct ready_list *, rtx, int);
static void ready_sort (struct ready_list *);
static rtx ready_remove_first (struct ready_list *);
@@ -511,15 +540,14 @@ static int early_queue_to_ready (state_t
static void debug_ready_list (struct ready_list *);
-static rtx move_insn1 (rtx, rtx);
-static rtx move_insn (rtx, rtx);
+static void move_insn (rtx);
/* The following functions are used to implement multi-pass scheduling
on the first cycle. */
static rtx ready_element (struct ready_list *, int);
static rtx ready_remove (struct ready_list *, int);
static void ready_remove_insn (rtx);
-static int max_issue (struct ready_list *, int *);
+static int max_issue (struct ready_list *, int *, int);
static rtx choose_ready (struct ready_list *);
@@ -528,6 +556,47 @@ static int fix_tick_ready (rtx);
static void change_queue_index (rtx, int);
static void resolve_dep (rtx, rtx);
+/* The following functions are used to implement scheduling of data/control
+ speculative instructions. */
+
+static void extend_h_i_d (void);
+static void extend_ready (int, int);
+static void extend_global (rtx);
+static void extend_all (rtx, int *);
+static void init_h_i_d (rtx);
+static void generate_recovery_code (rtx, int *);
+static void process_insn_depend_be_in_spec (rtx, rtx, int, int);
+static void begin_speculative_block (rtx, int *);
+static void add_to_speculative_block (rtx, int *);
+static int insn_points (rtx);
+static edge find_fallthru_edge (basic_block);
+static void init_before_recovery (void);
+static basic_block create_recovery_block (void);
+static void create_check_block_twin (rtx, int *, int);
+static void fix_recovery_deps (basic_block);
+static void associate_line_notes_with_blocks (basic_block);
+static void change_pattern (rtx, rtx);
+static int speculate_insn (rtx, int, rtx *);
+static void dump_new_block_header (int, basic_block, rtx, rtx);
+static void restore_bb_notes (basic_block);
+static void extend_bb (basic_block);
+static void fix_jump_move (rtx);
+static void move_block_after_check (rtx);
+static void move_succs (VEC(edge,gc) **, basic_block);
+static void init_glat (void);
+static void init_glat1 (basic_block);
+static void attach_life_info1 (basic_block);
+static void free_glat (void);
+static void sched_remove_insn (rtx, int *);
+static void clear_priorities (rtx);
+static void calc_priorities (rtx);
+#ifdef ENABLE_CHECKING
+static void dump_spec_status (int, FILE *);
+static int has_edge_p (VEC(edge,gc) *, int);
+static void check_cfg (rtx, rtx);
+static void check_sched_flags (int, spec_info_t);
+#endif
+
#endif /* INSN_SCHEDULING */
/* Point to state used for the current scheduling pass. */
@@ -540,6 +609,9 @@ schedule_insns (FILE *dump_file ATTRIBUT
}
#else
+/* Working copy of frontend's sched_info variable. */
+static struct sched_info current_sched_info_var;
+
/* Pointer to the last instruction scheduled. Used by rank_for_schedule,
so that insns independent of the last scheduled insn will be preferred
over dependent instructions. */
@@ -553,6 +625,20 @@ static rtx last_scheduled_insn;
HAIFA_INLINE int
insn_cost (rtx insn, rtx link, rtx used)
{
+ return insn_cost1 (insn, used ? REG_NOTE_KIND (link) : 0, link, used);
+}
+
+/* Compute cost of executing INSN given the dependence on the insn USED.
+ If LINK is not NULL, then its REG_NOTE_KIND is used as a dependence type.
+ Otherwise, dependence between INSN and USED is assumed to be of type
+ DEP_TYPE. This function was introduced as a workaround for
+ targetm.adjust_cost hook.
+ This is the number of cycles between instruction issue and
+ instruction results. */
+
+HAIFA_INLINE static int
+insn_cost1 (rtx insn, enum reg_note dep_type, rtx link, rtx used)
+{
int cost = INSN_COST (insn);
if (cost < 0)
@@ -577,7 +663,7 @@ insn_cost (rtx insn, rtx link, rtx used)
}
/* In this case estimate cost without caring how insn is used. */
- if (link == 0 || used == 0)
+ if (used == 0)
return cost;
/* A USE insn should never require the value used to be computed.
@@ -587,11 +673,13 @@ insn_cost (rtx insn, rtx link, rtx used)
cost = 0;
else
{
+ gcc_assert (!link || dep_type == REG_NOTE_KIND (link));
+
if (INSN_CODE (insn) >= 0)
{
- if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
+ if (dep_type == REG_DEP_ANTI)
cost = 0;
- else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
+ else if (dep_type == REG_DEP_OUTPUT)
{
cost = (insn_default_latency (insn)
- insn_default_latency (used));
@@ -602,8 +690,14 @@ insn_cost (rtx insn, rtx link, rtx used)
cost = insn_latency (insn, used);
}
- if (targetm.sched.adjust_cost)
- cost = targetm.sched.adjust_cost (used, link, insn, cost);
+ if (targetm.sched.adjust_cost_2)
+ cost = targetm.sched.adjust_cost_2 (used, dep_type, insn, cost);
+ else
+ {
+ gcc_assert (link);
+ if (targetm.sched.adjust_cost)
+ cost = targetm.sched.adjust_cost (used, link, insn, cost);
+ }
if (cost < 0)
cost = 0;
@@ -630,21 +724,68 @@ priority (rtx insn)
this_priority = insn_cost (insn, 0, 0);
else
{
- for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
- {
- rtx next;
- int next_priority;
+ rtx prev_first, twin;
+ basic_block rec;
- next = XEXP (link, 0);
+ /* For recovery check instructions we calculate priority slightly
+ different than that of normal instructions. Instead of walking
+ through INSN_DEPEND (check) list, we walk through INSN_DEPEND list
+ of each instruction in the corresponding recovery block. */
- /* Critical path is meaningful in block boundaries only. */
- if (! (*current_sched_info->contributes_to_priority) (next, insn))
- continue;
+ rec = RECOVERY_BLOCK (insn);
+ if (!rec || rec == EXIT_BLOCK_PTR)
+ {
+ prev_first = PREV_INSN (insn);
+ twin = insn;
+ }
+ else
+ {
+ prev_first = NEXT_INSN (BB_HEAD (rec));
+ twin = PREV_INSN (BB_END (rec));
+ }
+
+ do
+ {
+ for (link = INSN_DEPEND (twin); link; link = XEXP (link, 1))
+ {
+ rtx next;
+ int next_priority;
+
+ next = XEXP (link, 0);
+
+ if (BLOCK_FOR_INSN (next) != rec)
+ {
+ /* Critical path is meaningful in block boundaries
+ only. */
+ if (! (*current_sched_info->contributes_to_priority)
+ (next, insn)
+ /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
+ then speculative instructions will less likely be
+ scheduled. That is because the priority of
+ their producers will increase, and, thus, the
+ producers will more likely be scheduled, thus,
+ resolving the dependence. */
+ || ((current_sched_info->flags & DO_SPECULATION)
+ && (DEP_STATUS (link) & SPECULATIVE)
+ && !(spec_info->flags
+ & COUNT_SPEC_IN_CRITICAL_PATH)))
+ continue;
+
+ next_priority = insn_cost1 (insn,
+ twin == insn ?
+ REG_NOTE_KIND (link) :
+ REG_DEP_ANTI,
+ twin == insn ? link : 0,
+ next) + priority (next);
- next_priority = insn_cost (insn, link, next) + priority (next);
- if (next_priority > this_priority)
- this_priority = next_priority;
+ if (next_priority > this_priority)
+ this_priority = next_priority;
+ }
+ }
+
+ twin = PREV_INSN (twin);
}
+ while (twin != prev_first);
}
INSN_PRIORITY (insn) = this_priority;
INSN_PRIORITY_KNOWN (insn) = 1;
@@ -674,7 +815,7 @@ rank_for_schedule (const void *x, const
rtx tmp2 = *(const rtx *) x;
rtx link;
int tmp_class, tmp2_class, depend_count1, depend_count2;
- int val, priority_val, weight_val, info_val;
+ int val, priority_val, weight_val, info_val, points_val;
/* The insn in a schedule group should be issued the first. */
if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
@@ -686,6 +827,11 @@ rank_for_schedule (const void *x, const
if (priority_val)
return priority_val;
+ /* Prefer insn with more points. */
+ if (spec_info && (spec_info->flags & USE_SORT_POINTS)
+ && (points_val = INSN_POINTS (tmp2) - INSN_POINTS (tmp)))
+ return points_val;
+
/* Prefer an insn with smaller contribution to registers-pressure. */
if (!reload_completed &&
(weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
@@ -806,43 +952,36 @@ ready_lastpos (struct ready_list *ready)
return ready->vec + ready->first - ready->n_ready + 1;
}
-/* Add an element INSN to the ready list so that it ends up with the lowest
- priority. */
+/* Add an element INSN to the ready list so that it ends up with the
+ lowest/highest priority dependending on (FIRST_P == 0/FIRST_P != 0). */
HAIFA_INLINE static void
-ready_add (struct ready_list *ready, rtx insn)
+ready_add (struct ready_list *ready, rtx insn, int first_p)
{
- if (ready->first == ready->n_ready)
+ if (!first_p)
{
- memmove (ready->vec + ready->veclen - ready->n_ready,
- ready_lastpos (ready),
- ready->n_ready * sizeof (rtx));
- ready->first = ready->veclen - 1;
+ if (ready->first == ready->n_ready)
+ {
+ memmove (ready->vec + ready->veclen - ready->n_ready,
+ ready_lastpos (ready),
+ ready->n_ready * sizeof (rtx));
+ ready->first = ready->veclen - 1;
+ }
+ ready->vec[ready->first - ready->n_ready] = insn;
}
- ready->vec[ready->first - ready->n_ready] = insn;
- ready->n_ready++;
-
- gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
- QUEUE_INDEX (insn) = QUEUE_READY;
-}
-
-/* Add an element INSN to the ready list so that it ends up with the highest
- priority. */
-
-static void
-ready_add_first (struct ready_list *ready, rtx insn)
-{
- if (ready->first == ready->veclen - 1)
+ else
{
- if (ready->n_ready)
- /* ready_lastpos() fails when called with (ready->n_ready == 0). */
- memmove (ready->vec + ready->veclen - ready->n_ready - 1,
- ready_lastpos (ready),
- ready->n_ready * sizeof (rtx));
- ready->first = ready->veclen - 2;
+ if (ready->first == ready->veclen - 1)
+ {
+ if (ready->n_ready)
+ /* ready_lastpos() fails when called with (ready->n_ready == 0). */
+ memmove (ready->vec + ready->veclen - ready->n_ready - 1,
+ ready_lastpos (ready),
+ ready->n_ready * sizeof (rtx));
+ ready->first = ready->veclen - 2;
+ }
+ ready->vec[++(ready->first)] = insn;
}
-
- ready->vec[++(ready->first)] = insn;
ready->n_ready++;
gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY);
@@ -1023,17 +1162,29 @@ schedule_insn (rtx insn)
/* Update dependent instructions. */
for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
{
- int effective_cost;
rtx next = XEXP (link, 0);
resolve_dep (next, insn);
- effective_cost = try_ready (next);
-
- if (effective_cost >= 0
- && SCHED_GROUP_P (next)
- && advance < effective_cost)
- advance = effective_cost;
+ if (!RECOVERY_BLOCK (insn)
+ || RECOVERY_BLOCK (insn) == EXIT_BLOCK_PTR)
+ {
+ int effective_cost;
+
+ effective_cost = try_ready (next);
+
+ if (effective_cost >= 0
+ && SCHED_GROUP_P (next)
+ && advance < effective_cost)
+ advance = effective_cost;
+ }
+ else
+ /* Check always has only one forward dependence (to the first insn in
+ the recovery block), therefore, this will be executed only once. */
+ {
+ gcc_assert (XEXP (link, 1) == 0);
+ fix_recovery_deps (RECOVERY_BLOCK (insn));
+ }
}
/* Annotate the instruction with issue information -- TImode
@@ -1064,7 +1215,7 @@ unlink_other_notes (rtx insn, rtx tail)
{
rtx prev = PREV_INSN (insn);
- while (insn != tail && NOTE_P (insn))
+ while (insn != tail && NOTE_NOT_BB_P (insn))
{
rtx next = NEXT_INSN (insn);
/* Delete the note from its current position. */
@@ -1076,7 +1227,6 @@ unlink_other_notes (rtx insn, rtx tail)
/* See sched_analyze to see how these are handled. */
if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
{
@@ -1123,31 +1273,43 @@ unlink_line_notes (rtx insn, rtx tail)
return insn;
}
-/* Return the head and tail pointers of BB. */
+/* Return the head and tail pointers of ebb starting at BEG and ending
+ at END. */
void
-get_block_head_tail (int b, rtx *headp, rtx *tailp)
+get_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp)
{
- /* HEAD and TAIL delimit the basic block being scheduled. */
- rtx head = BB_HEAD (BASIC_BLOCK (b));
- rtx tail = BB_END (BASIC_BLOCK (b));
-
- /* Don't include any notes or labels at the beginning of the
- basic block, or notes at the ends of basic blocks. */
- while (head != tail)
- {
- if (NOTE_P (head))
- head = NEXT_INSN (head);
- else if (NOTE_P (tail))
- tail = PREV_INSN (tail);
- else if (LABEL_P (head))
- head = NEXT_INSN (head);
- else
- break;
- }
+ rtx beg_head = BB_HEAD (beg);
+ rtx beg_tail = BB_END (beg);
+ rtx end_head = BB_HEAD (end);
+ rtx end_tail = BB_END (end);
+
+ /* Don't include any notes or labels at the beginning of the BEG
+ basic block, or notes at the end of the END basic blocks. */
+
+ if (LABEL_P (beg_head))
+ beg_head = NEXT_INSN (beg_head);
+
+ while (beg_head != beg_tail)
+ if (NOTE_P (beg_head))
+ beg_head = NEXT_INSN (beg_head);
+ else
+ break;
+
+ *headp = beg_head;
+
+ if (beg == end)
+ end_head = beg_head;
+ else if (LABEL_P (end_head))
+ end_head = NEXT_INSN (end_head);
+
+ while (end_head != end_tail)
+ if (NOTE_P (end_tail))
+ end_tail = PREV_INSN (end_tail);
+ else
+ break;
- *headp = head;
- *tailp = tail;
+ *tailp = end_tail;
}
/* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */
@@ -1182,7 +1344,7 @@ rm_line_notes (rtx head, rtx tail)
/* Farm out notes, and maybe save them in NOTE_LIST.
This is needed to keep the debugger from
getting completely deranged. */
- if (NOTE_P (insn))
+ if (NOTE_NOT_BB_P (insn))
{
prev = insn;
insn = unlink_line_notes (insn, next_tail);
@@ -1273,6 +1435,7 @@ restore_line_notes (rtx head, rtx tail)
NEXT_INSN (prev) = note;
PREV_INSN (insn) = note;
NEXT_INSN (note) = insn;
+ set_block_for_insn (note, BLOCK_FOR_INSN (insn));
}
else
{
@@ -1360,7 +1523,7 @@ rm_other_notes (rtx head, rtx tail)
/* Farm out notes, and maybe save them in NOTE_LIST.
This is needed to keep the debugger from
getting completely deranged. */
- if (NOTE_P (insn))
+ if (NOTE_NOT_BB_P (insn))
{
prev = insn;
@@ -1401,49 +1564,53 @@ find_set_reg_weight (rtx x)
/* Calculate INSN_REG_WEIGHT for all insns of a block. */
static void
-find_insn_reg_weight (int b)
+find_insn_reg_weight (basic_block bb)
{
rtx insn, next_tail, head, tail;
- get_block_head_tail (b, &head, &tail);
+ get_ebb_head_tail (bb, bb, &head, &tail);
next_tail = NEXT_INSN (tail);
for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
- {
- int reg_weight = 0;
- rtx x;
-
- /* Handle register life information. */
- if (! INSN_P (insn))
- continue;
+ find_insn_reg_weight1 (insn);
+}
- /* Increment weight for each register born here. */
- x = PATTERN (insn);
- reg_weight += find_set_reg_weight (x);
- if (GET_CODE (x) == PARALLEL)
- {
- int j;
- for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
- {
- x = XVECEXP (PATTERN (insn), 0, j);
- reg_weight += find_set_reg_weight (x);
- }
- }
- /* Decrement weight for each register that dies here. */
- for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
+/* Calculate INSN_REG_WEIGHT for single insntruction.
+ Separated from find_insn_reg_weight because of need
+ to initialize new instruction in generate_recovery_code. */
+static void
+find_insn_reg_weight1 (rtx insn)
+{
+ int reg_weight = 0;
+ rtx x;
+
+ /* Handle register life information. */
+ if (! INSN_P (insn))
+ return;
+
+ /* Increment weight for each register born here. */
+ x = PATTERN (insn);
+ reg_weight += find_set_reg_weight (x);
+ if (GET_CODE (x) == PARALLEL)
+ {
+ int j;
+ for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
{
- if (REG_NOTE_KIND (x) == REG_DEAD
- || REG_NOTE_KIND (x) == REG_UNUSED)
- reg_weight--;
+ x = XVECEXP (PATTERN (insn), 0, j);
+ reg_weight += find_set_reg_weight (x);
}
-
- INSN_REG_WEIGHT (insn) = reg_weight;
}
+ /* Decrement weight for each register that dies here. */
+ for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
+ {
+ if (REG_NOTE_KIND (x) == REG_DEAD
+ || REG_NOTE_KIND (x) == REG_UNUSED)
+ reg_weight--;
+ }
+
+ INSN_REG_WEIGHT (insn) = reg_weight;
}
-/* Scheduling clock, modified in schedule_block() and queue_to_ready (). */
-static int clock_var;
-
/* Move insns that became ready to fire from queue to ready list. */
static void
@@ -1465,7 +1632,7 @@ queue_to_ready (struct ready_list *ready
fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
- ready_add (ready, insn);
+ ready_add (ready, insn, 0);
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready without stalls\n");
}
@@ -1490,7 +1657,7 @@ queue_to_ready (struct ready_list *ready
fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
(*current_sched_info->print_insn) (insn, 0));
- ready_add (ready, insn);
+ ready_add (ready, insn, 0);
if (sched_verbose >= 2)
fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
}
@@ -1629,7 +1796,7 @@ early_queue_to_ready (state_t state, str
{
/* move from Q to R */
q_size -= 1;
- ready_add (ready, insn);
+ ready_add (ready, insn, 0);
if (prev_link)
XEXP (prev_link, 1) = next_link;
@@ -1683,36 +1850,17 @@ debug_ready_list (struct ready_list *rea
fprintf (sched_dump, "\n");
}
-/* move_insn1: Remove INSN from insn chain, and link it after LAST insn. */
-
-static rtx
-move_insn1 (rtx insn, rtx last)
-{
- NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
- PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
-
- NEXT_INSN (insn) = NEXT_INSN (last);
- PREV_INSN (NEXT_INSN (last)) = insn;
-
- NEXT_INSN (last) = insn;
- PREV_INSN (insn) = last;
-
- return insn;
-}
-
/* Search INSN for REG_SAVE_NOTE note pairs for
NOTE_INSN_{LOOP,EHREGION}_{BEG,END}; and convert them back into
NOTEs. The REG_SAVE_NOTE note following first one is contains the
saved value for NOTE_BLOCK_NUMBER which is useful for
- NOTE_INSN_EH_REGION_{BEG,END} NOTEs. LAST is the last instruction
- output by the instruction scheduler. Return the new value of LAST. */
+ NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */
-static rtx
-reemit_notes (rtx insn, rtx last)
+static void
+reemit_notes (rtx insn)
{
- rtx note, retval;
+ rtx note, last = insn;
- retval = last;
for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
{
if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
@@ -1723,31 +1871,91 @@ reemit_notes (rtx insn, rtx last)
remove_note (insn, note);
}
}
- return retval;
}
-/* Move INSN. Reemit notes if needed.
-
- Return the last insn emitted by the scheduler, which is the
- return value from the first call to reemit_notes. */
+/* Move INSN. Reemit notes if needed. Update CFG, if needed. */
-static rtx
-move_insn (rtx insn, rtx last)
+static void
+move_insn (rtx insn)
{
- rtx retval = NULL;
+ rtx last = last_scheduled_insn;
- move_insn1 (insn, last);
+ if (PREV_INSN (insn) != last)
+ {
+ basic_block bb;
+ rtx note;
+ int jump_p = 0;
- /* If this is the first call to reemit_notes, then record
- its return value. */
- if (retval == NULL_RTX)
- retval = reemit_notes (insn, insn);
- else
- reemit_notes (insn, insn);
+ bb = BLOCK_FOR_INSN (insn);
+
+ /* BB_HEAD is either LABEL or NOTE. */
+ gcc_assert (BB_HEAD (bb) != insn);
+
+ if (BB_END (bb) == insn)
+ /* If this is last instruction in BB, move end marker one
+ instruction up. */
+ {
+ /* Jumps are always placed at the end of basic block. */
+ jump_p = control_flow_insn_p (insn);
+
+ gcc_assert (!jump_p
+ || ((current_sched_info->flags & SCHED_RGN)
+ && RECOVERY_BLOCK (insn)
+ && RECOVERY_BLOCK (insn) != EXIT_BLOCK_PTR)
+ || (current_sched_info->flags & SCHED_EBB));
+
+ gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb);
+
+ BB_END (bb) = PREV_INSN (insn);
+ }
+
+ gcc_assert (BB_END (bb) != last);
+
+ if (jump_p)
+ /* We move the block note along with jump. */
+ {
+ note = NEXT_INSN (insn);
+
+ if (LABEL_P (note)
+ || BARRIER_P (note))
+ note = NEXT_INSN (note);
+
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
+ }
+ else
+ note = insn;
- SCHED_GROUP_P (insn) = 0;
+ NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note);
+ PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn);
- return retval;
+ NEXT_INSN (note) = NEXT_INSN (last);
+ PREV_INSN (NEXT_INSN (last)) = note;
+
+ NEXT_INSN (last) = insn;
+ PREV_INSN (insn) = last;
+
+ bb = BLOCK_FOR_INSN (last);
+
+ if (jump_p)
+ {
+ fix_jump_move (insn);
+
+ if (BLOCK_FOR_INSN (insn) != bb)
+ move_block_after_check (insn);
+
+ gcc_assert (BB_END (bb) == last);
+ }
+
+ set_block_for_insn (insn, bb);
+
+ /* Update BB_END, if needed. */
+ if (BB_END (bb) == last)
+ BB_END (bb) = insn;
+ }
+
+ reemit_notes (insn);
+
+ SCHED_GROUP_P (insn) = 0;
}
/* The following structure describe an entry of the stack of choices. */
@@ -1797,13 +2005,15 @@ static int cached_issue_rate = 0;
insns is insns with the best rank (the first insn in READY). To
make this function tries different samples of ready insns. READY
is current queue `ready'. Global array READY_TRY reflects what
- insns are already issued in this try. INDEX will contain index
- of the best insn in READY. The following function is used only for
- first cycle multipass scheduling. */
+ insns are already issued in this try. MAX_POINTS is the sum of points
+ of all instructions in READY. The function stops immediatelly,
+ if it reached the such a solution, that all instruction can be issued.
+ INDEX will contain index of the best insn in READY. The following
+ function is used only for first cycle multipass scheduling. */
static int
-max_issue (struct ready_list *ready, int *index)
+max_issue (struct ready_list *ready, int *index, int max_points)
{
- int n, i, all, n_ready, best, delay, tries_num;
+ int n, i, all, n_ready, best, delay, tries_num, points = -1;
struct choice_entry *top;
rtx insn;
@@ -1828,7 +2038,8 @@ max_issue (struct ready_list *ready, int
{
best = top - choice_stack;
*index = choice_stack [1].index;
- if (top->n == issue_rate - cycle_issued_insns || best == all)
+ points = top->n;
+ if (top->n == max_points || best == all)
break;
}
i = top->index;
@@ -1851,7 +2062,7 @@ max_issue (struct ready_list *ready, int
top->rest--;
n = top->n;
if (memcmp (top->state, curr_state, dfa_state_size) != 0)
- n++;
+ n += ISSUE_POINTS (insn);
top++;
top->rest = cached_first_cycle_multipass_dfa_lookahead;
top->index = i;
@@ -1868,7 +2079,14 @@ max_issue (struct ready_list *ready, int
ready_try [top->index] = 0;
top--;
}
- memcpy (curr_state, choice_stack->state, dfa_state_size);
+ memcpy (curr_state, choice_stack->state, dfa_state_size);
+
+ if (sched_verbose >= 4)
+ fprintf (sched_dump, ";;\t\tChoosed insn : %s; points : %d/%d\n",
+ (*current_sched_info->print_insn) (ready_element (ready, *index),
+ 0),
+ points, max_points);
+
return best;
}
@@ -1888,9 +2106,10 @@ choose_ready (struct ready_list *ready)
else
{
/* Try to choose the better insn. */
- int index = 0, i;
+ int index = 0, i, n;
rtx insn;
-
+ int max_points, try_data = 1, try_control = 1;
+
if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
{
cached_first_cycle_multipass_dfa_lookahead = lookahead;
@@ -1901,26 +2120,78 @@ choose_ready (struct ready_list *ready)
insn = ready_element (ready, 0);
if (INSN_CODE (insn) < 0)
return ready_remove_first (ready);
+
+ if (spec_info
+ && spec_info->flags & (PREFER_NON_DATA_SPEC
+ | PREFER_NON_CONTROL_SPEC))
+ {
+ rtx x;
+ int s;
+
+ for (i = 0, n = ready->n_ready; i < n; i++)
+ {
+ x = ready_element (ready, i);
+ s = TODO_SPEC (x);
+
+ if (spec_info->flags & PREFER_NON_DATA_SPEC
+ && !(s & DATA_SPEC))
+ {
+ try_data = 0;
+ if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC)
+ || !try_control)
+ break;
+ }
+
+ if (spec_info->flags & PREFER_NON_CONTROL_SPEC
+ && !(s & CONTROL_SPEC))
+ {
+ try_control = 0;
+ if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data)
+ break;
+ }
+ }
+ }
+
+ if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC))
+ || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
+ || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
+ && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec
+ (insn)))
+ {
+ change_queue_index (insn, 1);
+ return 0;
+ }
+
+ max_points = ISSUE_POINTS (insn);
+
for (i = 1; i < ready->n_ready; i++)
{
insn = ready_element (ready, i);
ready_try [i]
= (INSN_CODE (insn) < 0
+ || (!try_data && (TODO_SPEC (insn) & DATA_SPEC))
+ || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC))
|| (targetm.sched.first_cycle_multipass_dfa_lookahead_guard
- && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard (insn)));
+ && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard
+ (insn)));
+
+ if (!ready_try [i])
+ max_points += ISSUE_POINTS (insn);
}
- if (max_issue (ready, &index) == 0)
+
+ if (max_issue (ready, &index, max_points) == 0)
return ready_remove_first (ready);
else
return ready_remove (ready, index);
}
}
-/* Use forward list scheduling to rearrange insns of block B in region RGN,
- possibly bringing insns from subsequent blocks in the same region. */
+/* Use forward list scheduling to rearrange insns of block pointed to by
+ TARGET_BB, possibly bringing insns from subsequent blocks in the same
+ region. */
void
-schedule_block (int b, int rgn_n_insns)
+schedule_block (basic_block *target_bb, int *rgn_n_insns)
{
struct ready_list ready;
int i, first_cycle_insn_p;
@@ -1943,36 +2214,27 @@ schedule_block (int b, int rgn_n_insns)
gcc_assert (head != tail || INSN_P (head));
+ added_recovery_block_p = 0;
+
/* Debug info. */
if (sched_verbose)
- {
- fprintf (sched_dump,
- ";; ======================================================\n");
- fprintf (sched_dump,
- ";; -- basic block %d from %d to %d -- %s reload\n",
- b, INSN_UID (head), INSN_UID (tail),
- (reload_completed ? "after" : "before"));
- fprintf (sched_dump,
- ";; ======================================================\n");
- fprintf (sched_dump, "\n");
- }
+ dump_new_block_header (0, *target_bb, head, tail);
state_reset (curr_state);
/* Allocate the ready list. */
readyp = &ready;
- ready.veclen = rgn_n_insns + 1 + issue_rate;
+ ready.vec = NULL;
+ ready_try = NULL;
+ choice_stack = NULL;
+
+ extend_ready (-1, *rgn_n_insns);
+
ready.first = ready.veclen - 1;
- ready.vec = xmalloc (ready.veclen * sizeof (rtx));
ready.n_ready = 0;
/* It is used for first cycle multipass scheduling. */
temp_state = alloca (dfa_state_size);
- ready_try = xcalloc ((rgn_n_insns + 1), sizeof (char));
- choice_stack = xmalloc ((rgn_n_insns + 1)
- * sizeof (struct choice_entry));
- for (i = 0; i <= rgn_n_insns; i++)
- choice_stack[i].state = xmalloc (dfa_state_size);
if (targetm.sched.md_init)
targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen);
@@ -1980,6 +2242,9 @@ schedule_block (int b, int rgn_n_insns)
/* We start inserting insns after PREV_HEAD. */
last_scheduled_insn = prev_head;
+ gcc_assert (NOTE_P (last_scheduled_insn)
+ && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb);
+
/* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the
queue. */
q_ptr = 0;
@@ -1995,6 +2260,9 @@ schedule_block (int b, int rgn_n_insns)
in try_ready () (which is called through init_ready_list ()). */
(*current_sched_info->init_ready_list) ();
+ /* Now we can restore basic block notes and maintain precise cfg. */
+ restore_bb_notes (*target_bb);
+
last_clock_var = -1;
advance = 0;
@@ -2062,7 +2330,7 @@ schedule_block (int b, int rgn_n_insns)
if (sched_verbose >= 2)
{
- fprintf (sched_dump, ";;\tReady list (t =%3d): ",
+ fprintf (sched_dump, ";;\tReady list (t = %3d): ",
clock_var);
debug_ready_list (&ready);
}
@@ -2088,7 +2356,11 @@ schedule_block (int b, int rgn_n_insns)
/* Select and remove the insn from the ready list. */
if (sort_p)
- insn = choose_ready (&ready);
+ {
+ insn = choose_ready (&ready);
+ if (!insn)
+ continue;
+ }
else
insn = ready_remove_first (&ready);
@@ -2099,16 +2371,15 @@ schedule_block (int b, int rgn_n_insns)
/* SORT_P is used by the target to override sorting
of the ready list. This is needed when the target
has modified its internal structures expecting that
- the insn will be issued next. But ready_add would add
- the insn with the lowest priority. As we need the insn
+ the insn will be issued next. As we need the insn
to have the highest priority (so it will be returned by
- the ready_remove_first call above), we are calling
- ready_add_first instead.
+ the ready_remove_first call above), we invoke
+ ready_add (&ready, insn, 1).
But, still, there is one issue: INSN can be later
discarded by scheduler's frontend through
current_sched_info->can_schedule_ready_p. */
{
- ready_add_first (&ready, insn);
+ ready_add (&ready, insn, 1);
break;
}
@@ -2150,11 +2421,53 @@ schedule_block (int b, int rgn_n_insns)
continue;
}
- if (! (*current_sched_info->can_schedule_ready_p) (insn))
- goto next;
+ if (current_sched_info->can_schedule_ready_p
+ && ! (*current_sched_info->can_schedule_ready_p) (insn))
+ /* We normally get here only if we don't want to move
+ insn from the split block. */
+ {
+ TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
+ continue;
+ }
+
+ /* DECISSION is made. */
+
+ if (TODO_SPEC (insn) & SPECULATIVE)
+ generate_recovery_code (insn, rgn_n_insns);
+
+ if (control_flow_insn_p (last_scheduled_insn)
+ /* This is used to to switch basic blocks by request
+ from scheduler front-end (actually, sched-ebb.c only).
+ This is used to process blocks with single fallthru
+ edge. If successing block has jump, it [jump] will try
+ move at the end of current bb, thus corrupting CFG. */
+ || current_sched_info->advance_target_bb (*target_bb, insn))
+ {
+ *target_bb = current_sched_info->advance_target_bb
+ (*target_bb, 0);
+
+ if (sched_verbose)
+ {
+ rtx x;
- last_scheduled_insn = move_insn (insn, last_scheduled_insn);
+ x = next_real_insn (last_scheduled_insn);
+ gcc_assert (x);
+ dump_new_block_header (1, *target_bb, x, tail);
+ }
+ last_scheduled_insn = BB_HEAD(*target_bb);
+ if (LABEL_P (last_scheduled_insn))
+ last_scheduled_insn = NEXT_INSN (last_scheduled_insn);
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (last_scheduled_insn));
+ }
+
+ /* Update counters, etc in the scheduler's front end. */
+ (*current_sched_info->begin_schedule_ready) (insn,
+ last_scheduled_insn);
+
+ move_insn (insn);
+ last_scheduled_insn = insn;
+
if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
{
cycle_issued_insns++;
@@ -2179,7 +2492,6 @@ schedule_block (int b, int rgn_n_insns)
if (advance != 0)
break;
- next:
first_cycle_insn_p = 0;
/* Sort the ready list based on priority. This must be
@@ -2216,17 +2528,33 @@ schedule_block (int b, int rgn_n_insns)
{
/* We must maintain QUEUE_INDEX between blocks in region. */
for (i = ready.n_ready - 1; i >= 0; i--)
- QUEUE_INDEX (ready_element (&ready, i)) = QUEUE_NOWHERE;
+ {
+ rtx x;
+
+ x = ready_element (&ready, i);
+ QUEUE_INDEX (x) = QUEUE_NOWHERE;
+ TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
+ }
if (q_size)
for (i = 0; i <= max_insn_queue_index; i++)
{
rtx link;
for (link = insn_queue[i]; link; link = XEXP (link, 1))
- QUEUE_INDEX (XEXP (link, 0)) = QUEUE_NOWHERE;
+ {
+ rtx x;
+
+ x = XEXP (link, 0);
+ QUEUE_INDEX (x) = QUEUE_NOWHERE;
+ TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
+ }
free_INSN_LIST_list (&insn_queue[i]);
}
+ }
+ if (!current_sched_info->queue_must_finish_empty
+ || added_recovery_block_p)
+ {
/* INSN_TICK (minimum clock tick at which the insn becomes
ready) may be not correct for the insn in the subsequent
blocks of the region. We should use a correct value of
@@ -2236,6 +2564,14 @@ schedule_block (int b, int rgn_n_insns)
fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn);
}
+#ifdef ENABLE_CHECKING
+ /* After reload ia64 backend doesn't maintain BB_END, so
+ if we want to check anything, better do it now.
+ And it already clobbered previously scheduled code. */
+ if (current_sched_info->flags & SCHED_EBB)
+ check_cfg (BB_HEAD (BLOCK_FOR_INSN (prev_head)), 0);
+#endif
+
if (targetm.sched.md_finish)
targetm.sched.md_finish (sched_dump, sched_verbose);
@@ -2248,12 +2584,16 @@ schedule_block (int b, int rgn_n_insns)
of the insns. */
if (note_list != 0)
{
+ basic_block head_bb = BLOCK_FOR_INSN (head);
rtx note_head = note_list;
while (PREV_INSN (note_head))
{
+ set_block_for_insn (note_head, head_bb);
note_head = PREV_INSN (note_head);
}
+ /* In the above cycle we've missed this note: */
+ set_block_for_insn (note_head, head_bb);
PREV_INSN (note_head) = PREV_INSN (head);
NEXT_INSN (PREV_INSN (head)) = note_head;
@@ -2277,7 +2617,7 @@ schedule_block (int b, int rgn_n_insns)
free (ready.vec);
free (ready_try);
- for (i = 0; i <= rgn_n_insns; i++)
+ for (i = 0; i <= *rgn_n_insns; i++)
free (choice_stack [i].state);
free (choice_stack);
}
@@ -2319,17 +2659,23 @@ set_priorities (rtx head, rtx tail)
return n_insn;
}
+static int luid;
+
/* Initialize some global state for the scheduler. DUMP_FILE is to be used
for debugging output. */
void
sched_init (FILE *dump_file)
{
- int luid;
basic_block b;
rtx insn;
int i;
+ /* Switch to working copy of sched_info. */
+ memcpy (¤t_sched_info_var, current_sched_info,
+ sizeof (current_sched_info_var));
+ current_sched_info = ¤t_sched_info_var;
+
/* Disable speculative loads in their presence if cc0 defined. */
#ifdef HAVE_cc0
flag_schedule_speculative_load = 0;
@@ -2344,6 +2690,22 @@ sched_init (FILE *dump_file)
sched_dump = ((sched_verbose_param >= 10 || !dump_file)
? stderr : dump_file);
+ /* Initialize SPEC_INFO. */
+ if (targetm.sched.set_sched_flags)
+ {
+ spec_info = &spec_info_var;
+ targetm.sched.set_sched_flags (&(current_sched_info->flags), spec_info);
+ if (!(current_sched_info->flags & DO_SPECULATION))
+ /* So we won't read anything accidently. */
+ spec_info = 0;
+#ifdef ENABLE_CHECKING
+ check_sched_flags (current_sched_info->flags, spec_info);
+#endif
+ }
+ else
+ /* So we won't read anything accidently. */
+ spec_info = 0;
+
/* Initialize issue_rate. */
if (targetm.sched.issue_rate)
issue_rate = targetm.sched.issue_rate ();
@@ -2357,15 +2719,14 @@ sched_init (FILE *dump_file)
cached_first_cycle_multipass_dfa_lookahead = 0;
}
- /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
- pseudos which do not cross calls. */
- old_max_uid = get_max_uid () + 1;
-
- h_i_d = xcalloc (old_max_uid, sizeof (*h_i_d));
+ old_max_uid = 0;
+ h_i_d = 0;
+ extend_h_i_d ();
for (i = 0; i < old_max_uid; i++)
{
h_i_d[i].cost = -1;
+ h_i_d[i].todo_spec = HARD_DEP;
h_i_d[i].queue_index = QUEUE_NOWHERE;
h_i_d[i].tick = INVALID_TICK;
h_i_d[i].inter_tick = INVALID_TICK;
@@ -2404,59 +2765,30 @@ sched_init (FILE *dump_file)
init_alias_analysis ();
- if (write_symbols != NO_DEBUG)
- {
- rtx line;
-
- line_note_head = xcalloc (last_basic_block, sizeof (rtx));
-
- /* Save-line-note-head:
- Determine the line-number at the start of each basic block.
- This must be computed and saved now, because after a basic block's
- predecessor has been scheduled, it is impossible to accurately
- determine the correct line number for the first insn of the block. */
-
- FOR_EACH_BB (b)
- {
- for (line = BB_HEAD (b); line; line = PREV_INSN (line))
- if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
- {
- line_note_head[b->index] = line;
- break;
- }
- /* Do a forward search as well, since we won't get to see the first
- notes in a basic block. */
- for (line = BB_HEAD (b); line; line = NEXT_INSN (line))
- {
- if (INSN_P (line))
- break;
- if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
- line_note_head[b->index] = line;
- }
- }
- }
-
- /* The following is done to keep current_sched_info->next_tail non null. */
+ line_note_head = 0;
+ old_last_basic_block = 0;
+ glat_start = 0;
+ glat_end = 0;
+ extend_bb (0);
- insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
- if (NEXT_INSN (insn) == 0
- || (!NOTE_P (insn)
- && !LABEL_P (insn)
- /* Don't emit a NOTE if it would end up before a BARRIER. */
- && !BARRIER_P (NEXT_INSN (insn))))
- {
- emit_note_after (NOTE_INSN_DELETED, insn);
- /* Make insn to appear outside BB. */
- BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
- }
+ if (current_sched_info->flags & USE_GLAT)
+ init_glat ();
/* Compute INSN_REG_WEIGHT for all blocks. We must do this before
removing death notes. */
FOR_EACH_BB_REVERSE (b)
- find_insn_reg_weight (b->index);
+ find_insn_reg_weight (b);
if (targetm.sched.md_init_global)
targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid);
+
+ nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
+ before_recovery = 0;
+
+#ifdef ENABLE_CHECKING
+ /* This is used preferably for finding bugs in check_cfg () itself. */
+ check_cfg (0, 0);
+#endif
}
/* Free global data used during insn scheduling. */
@@ -2469,11 +2801,38 @@ sched_finish (void)
dfa_finish ();
free_dependency_caches ();
end_alias_analysis ();
- if (write_symbols != NO_DEBUG)
- free (line_note_head);
+ free (line_note_head);
+ free_glat ();
if (targetm.sched.md_finish_global)
- targetm.sched.md_finish_global (sched_dump, sched_verbose);
+ targetm.sched.md_finish_global (sched_dump, sched_verbose);
+
+ if (spec_info && spec_info->dump)
+ {
+ char c = reload_completed ? 'a' : 'b';
+
+ fprintf (spec_info->dump,
+ ";; %s:\n", current_function_name ());
+
+ fprintf (spec_info->dump,
+ ";; Procedure %cr-begin-data-spec motions == %d\n",
+ c, nr_begin_data);
+ fprintf (spec_info->dump,
+ ";; Procedure %cr-be-in-data-spec motions == %d\n",
+ c, nr_be_in_data);
+ fprintf (spec_info->dump,
+ ";; Procedure %cr-begin-control-spec motions == %d\n",
+ c, nr_begin_control);
+ fprintf (spec_info->dump,
+ ";; Procedure %cr-be-in-control-spec motions == %d\n",
+ c, nr_be_in_control);
+ }
+
+#ifdef ENABLE_CHECKING
+ /* After reload ia64 backend clobbers CFG, so can't check anything. */
+ if (current_sched_info->flags & SCHED_RGN)
+ check_cfg (0, 0);
+#endif
}
/* Fix INSN_TICKs of the instructions in the subsequent blocks. */
@@ -2549,18 +2908,175 @@ fix_inter_tick (rtx head, rtx tail)
0 < N - queued for N cycles. */
int
try_ready (rtx next)
-{
- if (LOG_LINKS (next)
- || (current_sched_info->new_ready
- && !current_sched_info->new_ready (next)))
- {
- gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);
- return -1;
- }
+{
+ int old_ts, *ts;
+ rtx link;
+ int points = MIN_SCHED_POINTS - 1;
+
+ ts = &TODO_SPEC (next);
+ old_ts = *ts;
+
+ gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP)));
+ gcc_assert ((old_ts & HARD_DEP)
+ || (old_ts & SPECULATIVE));
+
+ if (!(current_sched_info->flags & DO_SPECULATION))
+ {
+ if (!LOG_LINKS (next))
+ *ts &= ~HARD_DEP;
+ }
+ else
+ {
+ *ts &= ~SPECULATIVE & ~HARD_DEP;
+
+ link = LOG_LINKS (next);
+ if (link)
+ {
+ /* LOG_LINKS are maintained sorted.
+ So if DEP_STATUS of the first dep is SPECULATIVE,
+ than all other deps are speculative too. */
+ if (DEP_STATUS (link) & SPECULATIVE)
+ {
+ /* Now we've got NEXT with speculative deps only.
+ 1. Look at the deps to see what we have to do.
+ 2. Check if we can do 'todo'. */
+ do
+ *ts |= DEP_STATUS (link) & SPECULATIVE;
+ while ((link = XEXP (link, 1)));
+
+ /* The following 'if' should be superstited with
+ ready_try filters. */
+ if (spec_info->flags & USE_SPEC_POINTS)
+ /* Check that NEXT is good enough to be added to ready list. */
+ {
+ points = insn_points (next);
+ if (points < spec_info->spec_points_cutoff)
+ /* Too few points. */
+ *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+ }
+ }
+ else
+ *ts |= HARD_DEP;
+ }
+ }
+
+ if (*ts & HARD_DEP)
+ gcc_assert (*ts == old_ts
+ && QUEUE_INDEX (next) == QUEUE_NOWHERE);
+ else if (current_sched_info->new_ready)
+ current_sched_info->new_ready (next, ts);
+
+ /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
+ have its original pattern or changed (speculative) one. This is due
+ to changing ebb in region scheduling.
+ * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
+ has speculative pattern.
+
+ We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
+ control-speculative NEXT could have been discarded by sched-rgn.c
+ (the same case as when discarded by can_schedule_ready_p ()). */
+
+ if ((*ts & SPECULATIVE)
+ /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
+ need to change anything. */
+ && *ts != old_ts)
+ {
+ int res;
+ rtx new_pat;
+
+ gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
+
+ res = speculate_insn (next, *ts, &new_pat);
+
+ switch (res)
+ {
+ case -1:
+ /* It would be nice to change DEP_STATUS of all dependences,
+ which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
+ so we won't reanalyze anything.
+ Gonna do that in the stable version. */
+ *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+ break;
+
+ case 0:
+ break;
+
+ case 1:
+ if (!ORIG_PAT (next))
+ /* If we gonna to overwrite the original pattern of insn,
+ save it. */
+ ORIG_PAT (next) = PATTERN (next);
+
+ change_pattern (next, new_pat);
+ break;
+
+ default:
+ gcc_unreachable ();
+ }
+ }
+
+ /* We need to restore pattern only if (*ts == 0), because otherwise it is
+ either correct (*ts & SPECULATIVE),
+ or we simply don't care (*ts & HARD_DEP). */
+
+ if (ORIG_PAT (next) && RECOVERY_BLOCK (next))
+ gcc_assert (RECOVERY_BLOCK (next) == EXIT_BLOCK_PTR);
+
+ if (*ts == 0 && ORIG_PAT (next) && !RECOVERY_BLOCK (next))
+ /* We should change pattern of every previously speculative
+ instruction - and we determine if NEXT was speculative by using
+ ORIG_PAT field. Except one case - simple checks have ORIG_PAT
+ pat too, hence we also check for the "Universal Check Flag" (UCF) -
+ RECOVERY_BLOCK. */
+ {
+ change_pattern (next, ORIG_PAT (next));
+ ORIG_PAT (next) = 0;
+ }
+
+ if (*ts & HARD_DEP)
+ {
+ /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
+ control-speculative NEXT could have been discarded by sched-rgn.c
+ (the same case as when discarded by can_schedule_ready_p ()). */
+ /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/
+
+ change_queue_index (next, QUEUE_NOWHERE);
+ return -1;
+ }
+
+ if (spec_info
+ && (spec_info->flags &
+ (USE_SPEC_POINTS | USE_ISSUE_POINTS | USE_SORT_POINTS)))
+ {
+ if (points == MIN_SCHED_POINTS - 1)
+ points = insn_points (next);
+
+ SET_INSN_POINTS (next, points);
+ }
+ else
+ gcc_assert (INSN_POINTS (next) == MAX_SCHED_POINTS);
if (sched_verbose >= 2)
- fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s\n",
- (*current_sched_info->print_insn) (next, 0));
+ {
+ int s = TODO_SPEC (next);
+
+ fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
+ (*current_sched_info->print_insn) (next, 0));
+
+ if (spec_info && spec_info->dump)
+ {
+ if (s & BEGIN_DATA)
+ fprintf (spec_info->dump, "; data-spec;");
+ if (s & BEGIN_CONTROL)
+ fprintf (spec_info->dump, "; control-spec;");
+ if (s & BE_IN_CONTROL)
+ fprintf (spec_info->dump, "; in-control-spec;");
+ }
+
+ fprintf (sched_dump, "\n");
+ }
+
+ adjust_priority (next);
return fix_tick_ready (next);
}
@@ -2610,8 +3126,6 @@ fix_tick_ready (rtx next)
delay = QUEUE_READY;
change_queue_index (next, delay);
-
- adjust_priority (next);
return delay;
}
@@ -2641,7 +3155,7 @@ change_queue_index (rtx next, int delay)
/* Add it to the proper place. */
if (delay == QUEUE_READY)
- ready_add (readyp, next);
+ ready_add (readyp, next, 0);
else if (delay >= 1)
queue_insn (next, delay);
@@ -2675,4 +3189,1461 @@ resolve_dep (rtx next, rtx insn)
&& (LOG_LINKS (next) || INSN_DEP_COUNT (next) == 0));
}
+/* Extend H_I_D data. */
+static void
+extend_h_i_d (void)
+{
+ /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for
+ pseudos which do not cross calls. */
+ int new_max_uid = get_max_uid() + 1;
+ h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d));
+ old_max_uid = new_max_uid;
+}
+
+/* Extend READY, READY_TRY and CHOICE_STACK arrays. */
+static void
+extend_ready (int old_rgn_n_insns, int new_rgn_n_insns)
+{
+ int i;
+
+ readyp->veclen = new_rgn_n_insns + 1 + issue_rate;
+ readyp->vec = xrealloc (readyp->vec, readyp->veclen * sizeof (rtx));
+
+ ready_try = xrecalloc (ready_try, new_rgn_n_insns + 1, old_rgn_n_insns + 1,
+ sizeof (char));
+
+ choice_stack = xrealloc (choice_stack, (new_rgn_n_insns + 1)
+ * sizeof (struct choice_entry));
+ for (i = old_rgn_n_insns + 1; i <= new_rgn_n_insns; i++)
+ choice_stack[i].state = xmalloc (dfa_state_size);
+}
+
+/* Extend global scheduler structures (those, that live across calls to
+ schedule_block). */
+static void
+extend_global (rtx insn)
+{
+ /* These structures have scheduler scope. */
+ extend_h_i_d ();
+ init_h_i_d (insn);
+
+ targetm.sched.h_i_d_extended ();
+ extend_dependency_caches (1, 0);
+}
+
+/* Extends global all local scheduler structures. */
+static void
+extend_all (rtx insn, int *rgn_n_insns)
+{
+ extend_global (insn);
+
+ /* These structures have block scope. */
+ extend_ready (*rgn_n_insns, *rgn_n_insns + 1);
+ (*rgn_n_insns)++;
+
+ (*current_sched_info->add_remove_insn) (insn, 0);
+}
+
+/* Initialize h_i_d entry of the new INSN with default values.
+ Values, that are not explicitly initialized here, hold zero. */
+static void
+init_h_i_d (rtx insn)
+{
+ INSN_LUID (insn) = luid++;
+ INSN_COST (insn) = -1;
+ TODO_SPEC (insn) = HARD_DEP;
+ QUEUE_INDEX (insn) = QUEUE_NOWHERE;
+ INSN_TICK (insn) = INVALID_TICK;
+ INTER_TICK (insn) = INVALID_TICK;
+ find_insn_reg_weight1 (insn);
+}
+
+/* Generates recovery code for INSN. */
+static void
+generate_recovery_code (rtx insn, int *rgn_n_insns)
+{
+ if (TODO_SPEC (insn) & BEGIN_SPEC)
+ begin_speculative_block (insn, rgn_n_insns);
+
+ /* Here we have insn with no dependencies to
+ instructions other then CHECK_SPEC ones. */
+
+ if (TODO_SPEC (insn) & BE_IN_SPEC)
+ add_to_speculative_block (insn, rgn_n_insns);
+}
+
+/* Helper function.
+ Tries to add speculative dependencies between instructions in INSN_DEPEND
+ list and TWIN. */
+static void
+process_insn_depend_be_in_spec (rtx insn_depend, rtx twin, int fs,
+ int mutate_p ATTRIBUTE_UNUSED)
+{
+ rtx link;
+
+ /* Copy all links from INSN_DEPEND of insn to the check as well. */
+ for (link = insn_depend; link; link = XEXP (link, 1))
+ {
+ int ds, dw;
+ rtx consumer;
+
+ consumer = XEXP (link, 0);
+
+ ds = DEP_STATUS (link);
+ gcc_assert (mutate_p || !(ds & BE_IN_SPEC));
+
+ if ((ds & DEP_TYPES) == DEP_TRUE)
+ {
+ ds = (ds & ~(HARD_DEP | BEGIN_SPEC)) | fs;
+ dw = MIN_DEP_WEIGHT;
+ }
+ else
+ {
+ ds = (ds & ~BEGIN_SPEC) | HARD_DEP;
+ dw = HARD_DEP_WEIGHT;
+ }
+
+ gcc_assert (!mutate_p
+ || (DEP_STATUS (link) == ds
+ && DEP_WEIGHT (link) == dw)
+ || HAS_INTERNAL_DEP (consumer));
+
+ add_back_forw_dep (consumer, twin, REG_NOTE_KIND (link), ds, dw);
+ }
+}
+
+/* Generates recovery code for BEGIN speculative INSN. */
+static void
+begin_speculative_block (rtx insn, int *rgn_n_insns)
+{
+ if (TODO_SPEC (insn) & BEGIN_DATA)
+ nr_begin_data++;
+ if (TODO_SPEC (insn) & BEGIN_CONTROL)
+ nr_begin_control++;
+
+ create_check_block_twin (insn, rgn_n_insns, 0);
+
+ TODO_SPEC (insn) &= ~BEGIN_SPEC;
+}
+
+/* Generates recovery code for BE_IN speculative INSN. */
+static void
+add_to_speculative_block (rtx insn, int *rgn_n_insns)
+{
+ int ts;
+ rtx link, twins = NULL;
+
+ ts = TODO_SPEC (insn);
+ gcc_assert (!(ts & ~BE_IN_SPEC));
+
+ if (ts & BE_IN_DATA)
+ nr_be_in_data++;
+ if (ts & BE_IN_CONTROL)
+ nr_be_in_control++;
+
+ TODO_SPEC (insn) &= ~BE_IN_SPEC;
+ gcc_assert (!TODO_SPEC (insn));
+
+ DONE_SPEC (insn) |= ts;
+
+ /* First we convert all simple checks to branchy. */
+ for (link = LOG_LINKS (insn); link;)
+ {
+ rtx check;
+
+ check = XEXP (link, 0);
+
+ if (RECOVERY_BLOCK (check))
+ {
+ create_check_block_twin (check, rgn_n_insns, 1);
+ link = LOG_LINKS (insn);
+ }
+ else
+ link = XEXP (link, 1);
+ }
+
+ clear_priorities (insn);
+
+ do
+ {
+ rtx link, check, twin;
+ basic_block rec;
+
+ link = LOG_LINKS (insn);
+ gcc_assert (!(DEP_STATUS (link) & BEGIN_SPEC)
+ && (DEP_STATUS (link) & BE_IN_SPEC)
+ && (DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+
+ check = XEXP (link, 0);
+ gcc_assert (!RECOVERY_BLOCK (check) && !ORIG_PAT (check)
+ && QUEUE_INDEX (check) == QUEUE_NOWHERE);
+
+ rec = BLOCK_FOR_INSN (check);
+
+ twin = emit_insn_before (copy_rtx (PATTERN (insn)), BB_END (rec));
+ extend_global (twin);
+
+ RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn));
+
+ if (sched_verbose && spec_info->dump)
+ /* INSN_BB (insn) isn't determined for twin insns yet.
+ So we can't use current_sched_info->print_insn. */
+ fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
+ INSN_UID (twin), rec->index);
+
+ twins = alloc_INSN_LIST (twin, twins);
+
+ /* Add dependences between TWIN and all apropriate
+ instructions from REC. */
+ do
+ {
+ add_back_forw_dep (twin, check, REG_DEP_TRUE,
+ HARD_DEP | DEP_TRUE, HARD_DEP_WEIGHT);
+
+ do
+ {
+ link = XEXP (link, 1);
+ if (link)
+ {
+ check = XEXP (link, 0);
+ if (BLOCK_FOR_INSN (check) == rec)
+ break;
+ }
+ else
+ break;
+ }
+ while (1);
+ }
+ while (link);
+
+ process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, ts, 0);
+
+ for (link = LOG_LINKS (insn); link;)
+ {
+ check = XEXP (link, 0);
+
+ if (BLOCK_FOR_INSN (check) == rec)
+ {
+ delete_back_forw_dep (insn, check);
+ link = LOG_LINKS (insn);
+ }
+ else
+ link = XEXP (link, 1);
+ }
+ }
+ while (LOG_LINKS (insn));
+
+ /* We can't add the dependence between insn and twin earlier because
+ that would make twin appear in the INSN_DEPEND (insn). */
+ while (twins)
+ {
+ rtx twin;
+
+ twin = XEXP (twins, 0);
+ calc_priorities (twin);
+ add_back_forw_dep (twin, insn, REG_DEP_OUTPUT,
+ HARD_DEP | DEP_OUTPUT, HARD_DEP_WEIGHT);
+
+ twin = XEXP (twins, 1);
+ free_INSN_LIST_node (twins);
+ twins = twin;
+ }
+}
+
+/* Extends and fills with zeros array pointed to by P. */
+void *
+xrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size)
+{
+ gcc_assert (new_nmemb >= old_nmemb);
+ p = xrealloc (p, new_nmemb * size);
+ memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size);
+ return p;
+}
+
+/* Calculate points for INSN. */
+static int
+insn_points (rtx insn)
+{
+ int res;
+
+ if (LOG_LINKS (insn))
+ {
+ static const int K = MAX_SCHED_POINTS / WEAK_DEP_MAX;
+ /* Magic number. It is (1 + log(MAX_SCHED_POINTS, MAX_INT)). */
+ static int N = 4;
+ rtx link;
+ int n = 0;
+
+ res = 1; /* This usually helps to skip division. */
+ for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+ {
+ if (++n >= N)
+ /* We came close to overflow.
+ Don't think that this is a rare case. */
+ res /= MAX_SCHED_POINTS;
+
+ res *= MAX_SCHED_POINTS - DEP_WEIGHT (link) * K;
+ }
+
+ if (n >= N)
+ n = N - 1;
+ while (--n)
+ res /= MAX_SCHED_POINTS;
+
+ gcc_assert (res <= MAX_SCHED_POINTS);
+
+ if (res < MIN_SCHED_POINTS)
+ res = MIN_SCHED_POINTS;
+ }
+ else
+ res = MAX_SCHED_POINTS;
+
+ res = (*current_sched_info->insn_points) (insn, res);
+
+ if (res > MAX_SCHED_POINTS)
+ /* Probability of basic block can be > 1.0 (may be that is a bug).
+ So, workaround. */
+ res = MAX_SCHED_POINTS;
+ else if (res < MIN_SCHED_POINTS)
+ res = MIN_SCHED_POINTS;
+
+ return res;
+}
+
+/* Helper function.
+ Find fallthru edge from PRED. */
+static edge
+find_fallthru_edge (basic_block pred)
+{
+ edge e;
+ edge_iterator ei;
+ basic_block succ;
+
+ succ = pred->next_bb;
+ gcc_assert (succ->prev_bb == pred);
+
+ if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
+ {
+ FOR_EACH_EDGE (e, ei, pred->succs)
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ gcc_assert (e->dest == succ);
+ return e;
+ }
+ }
+ else
+ {
+ FOR_EACH_EDGE (e, ei, succ->preds)
+ if (e->flags & EDGE_FALLTHRU)
+ {
+ gcc_assert (e->src == pred);
+ return e;
+ }
+ }
+
+ return NULL;
+}
+
+/* Initialize BEFORE_RECOVERY variable. */
+static void
+init_before_recovery (void)
+{
+ basic_block last;
+ edge e;
+
+ last = EXIT_BLOCK_PTR->prev_bb;
+ e = find_fallthru_edge (last);
+
+ if (e)
+ {
+ /* We create two basic blocks:
+ 1. Single instruction block is inserted right after E->SRC
+ and has jump to
+ 2. Empty block right before EXIT_BLOCK.
+ Between these two blocks recovery blocks will be emitted. */
+
+ basic_block single, empty;
+ rtx x, label;
+
+ single = create_empty_bb (last);
+ empty = create_empty_bb (single);
+
+ single->count = last->count;
+ empty->count = last->count;
+ single->frequency = last->frequency;
+ empty->frequency = last->frequency;
+ BB_COPY_PARTITION (single, last);
+ BB_COPY_PARTITION (empty, last);
+
+ redirect_edge_succ (e, single);
+ make_single_succ_edge (single, empty, 0);
+ make_single_succ_edge (empty, EXIT_BLOCK_PTR,
+ EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
+
+ label = block_label (empty);
+ x = emit_jump_insn_after (gen_jump (label), BB_END (single));
+ JUMP_LABEL (x) = label;
+ LABEL_NUSES (label)++;
+ extend_global (x);
+
+ emit_barrier_after (x);
+
+ add_block (empty, 0);
+ add_block (single, 0);
+
+ before_recovery = single;
+
+ if (sched_verbose >= 2 && spec_info->dump)
+ fprintf (spec_info->dump,
+ ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n",
+ last->index, single->index, empty->index);
+ }
+ else
+ before_recovery = last;
+}
+
+/* Returns new recovery block. */
+static basic_block
+create_recovery_block (void)
+{
+ rtx label;
+ basic_block rec;
+
+ added_recovery_block_p = 1;
+
+ if (!before_recovery)
+ init_before_recovery ();
+
+ label = gen_label_rtx ();
+ gcc_assert (BARRIER_P (NEXT_INSN (BB_END (before_recovery))));
+ label = emit_label_after (label, NEXT_INSN (BB_END (before_recovery)));
+
+ rec = create_basic_block (label, label, before_recovery);
+ emit_barrier_after (BB_END (rec));
+
+ rec->frequency = 0;
+ rec->count = 0;
+ if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED)
+ BB_SET_PARTITION (rec, BB_COLD_PARTITION);
+
+ if (sched_verbose && spec_info->dump)
+ fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n",
+ rec->index);
+
+ before_recovery = rec;
+
+ return rec;
+}
+
+/* This function creates recovery code for INSN. MUTATE_P is nonzero,
+ if INSN is a simple check, that should be converted to branchy one. */
+static void
+create_check_block_twin (rtx insn, int *rgn_n_insns, int mutate_p)
+{
+ basic_block rec;
+ rtx label, check, twin, link;
+ int ts, fs;
+
+ gcc_assert (ORIG_PAT (insn)
+ && (!mutate_p
+ || (RECOVERY_BLOCK (insn) == EXIT_BLOCK_PTR
+ && !(TODO_SPEC (insn) & SPECULATIVE))));
+
+ /* Create recovery block. */
+ if (mutate_p || targetm.sched.needs_block_p (insn))
+ {
+ rec = create_recovery_block ();
+ label = BB_HEAD (rec);
+ }
+ else
+ {
+ rec = EXIT_BLOCK_PTR;
+ label = 0;
+ }
+
+ /* Emit CHECK. */
+ check = targetm.sched.gen_check (insn, label, mutate_p);
+
+ if (rec != EXIT_BLOCK_PTR)
+ {
+ /* To have mem_reg alive at the beginning of second_bb,
+ we emit check BEFORE insn, so insn after splitting
+ insn will be at the beginning of second_bb, which will
+ provide us with the correct life information. */
+ check = emit_jump_insn_before (check, insn);
+ JUMP_LABEL (check) = label;
+ LABEL_NUSES (label)++;
+ }
+ else
+ check = emit_insn_before (check, insn);
+
+ /* Extend data structures. */
+ extend_all (check, rgn_n_insns);
+ RECOVERY_BLOCK (check) = rec;
+
+ if (sched_verbose && spec_info->dump)
+ fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n",
+ (*current_sched_info->print_insn) (check, 0));
+
+ gcc_assert (ORIG_PAT (insn));
+
+ /* Initialize TWIN (twin is a dublicate of original instruction
+ in the recovery block. */
+ if (rec != EXIT_BLOCK_PTR)
+ {
+ rtx link;
+
+ for (link = RESOLVED_DEPS (insn); link; link = XEXP (link, 1))
+ if (DEP_STATUS (link) & DEP_OUTPUT)
+ {
+ RESOLVED_DEPS (check) =
+ alloc_DEPS_LIST (XEXP (link, 0), RESOLVED_DEPS (check),
+ DEP_TRUE | HARD_DEP, HARD_DEP_WEIGHT);
+ PUT_REG_NOTE_KIND (RESOLVED_DEPS (check), REG_DEP_TRUE);
+ }
+
+ twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
+ extend_global (twin);
+
+ if (sched_verbose && spec_info->dump)
+ /* INSN_BB (insn) isn't determined for twin insns yet.
+ So we can't use current_sched_info->print_insn. */
+ fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n",
+ INSN_UID (twin), rec->index);
+ }
+ else
+ {
+ CHECK_NO (check) = CHECK_NO (insn);
+ ORIG_PAT (check) = ORIG_PAT (insn);
+ HAS_INTERNAL_DEP (check) = 1;
+ twin = check;
+ /* ??? We probably should change all OUTPUT dependencies to
+ (TRUE | OUTPUT). */
+ }
+
+ RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn));
+
+ if (rec != EXIT_BLOCK_PTR)
+ /* In case of branchy check, fix CFG. */
+ {
+ basic_block first_bb, second_bb;
+ rtx jump;
+ edge e;
+ int edge_flags;
+
+ first_bb = BLOCK_FOR_INSN (check);
+ e = split_block (first_bb, check);
+ /* split_block emits note if *check == BB_END. Probably it
+ is better to rip that note off. */
+ gcc_assert (e->src == first_bb);
+ second_bb = e->dest;
+
+ /* This is fixing of incoming edge. */
+ /* ??? Which other flags should be specified? */
+ if (BB_PARTITION (first_bb) != BB_PARTITION (rec))
+ /* Partition type is the same, if it is "unpartitioned". */
+ edge_flags = EDGE_CROSSING;
+ else
+ edge_flags = 0;
+
+ e = make_edge (first_bb, rec, edge_flags);
+ e->count = 0;
+ e->probability = 0;
+
+ add_block (second_bb, first_bb);
+
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb)));
+ label = block_label (second_bb);
+ jump = emit_jump_insn_after (gen_jump (label), BB_END (rec));
+ JUMP_LABEL (jump) = label;
+ LABEL_NUSES (label)++;
+ extend_global (jump);
+
+ if (BB_PARTITION (second_bb) != BB_PARTITION (rec))
+ /* Partition type is the same, if it is "unpartitioned". */
+ {
+ /* Rewritten from cfgrtl.c. */
+ if (flag_reorder_blocks_and_partition
+ && targetm.have_named_sections
+ /*&& !any_condjump_p (jump)*/)
+ /* any_condjump_p (jump) == false.
+ We don't need the same note for the check because
+ any_condjump_p (check) == true. */
+ {
+ REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
+ NULL_RTX,
+ REG_NOTES (jump));
+ }
+ edge_flags = EDGE_CROSSING;
+ }
+ else
+ edge_flags = 0;
+
+ make_single_succ_edge (rec, second_bb, edge_flags);
+
+ add_block (rec, EXIT_BLOCK_PTR);
+ }
+
+ /* Move backward dependences from INSN to CHECK and
+ move forward dependences from INSN to TWIN. */
+ for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+ {
+ int ds, dw;
+
+ /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
+ check --TRUE--> producer ??? or ANTI ???
+ twin --TRUE--> producer
+ twin --ANTI--> check
+
+ If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
+ check --ANTI--> producer
+ twin --ANTI--> producer
+ twin --ANTI--> check
+
+ If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
+ check ~~TRUE~~> producer
+ twin ~~TRUE~~> producer
+ twin --ANTI--> check */
+
+ ds = DEP_STATUS (link);
+
+ if (ds & BEGIN_SPEC)
+ {
+ gcc_assert (!mutate_p);
+
+ ds = (ds & ~BEGIN_SPEC) | HARD_DEP;
+ dw = HARD_DEP_WEIGHT;
+ }
+ else
+ dw = DEP_WEIGHT (link);
+
+ if (rec != EXIT_BLOCK_PTR)
+ {
+ add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link),
+ ds, dw);
+ add_back_forw_dep (twin, XEXP (link, 0), REG_NOTE_KIND (link),
+ ds, dw);
+ }
+ else
+ add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds, dw);
+ }
+
+ for (link = LOG_LINKS (insn); link;)
+ if ((DEP_STATUS (link) & BEGIN_SPEC)
+ || mutate_p)
+ /* We can delete this dep only if we
+ overcome it with BEGIN_SPECULATION.
+ If to overcome this dep we should do
+ BE_IN_SPECULATION stuff, keep it. */
+ {
+ delete_back_forw_dep (insn, XEXP (link, 0));
+ link = LOG_LINKS (insn);
+ }
+ else
+ link = XEXP (link, 1);
+
+ /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
+ here. */
+
+ gcc_assert (!DONE_SPEC (insn));
+ if (!mutate_p)
+ {
+ ts = TODO_SPEC (insn);
+
+ DONE_SPEC (insn) = ts & BEGIN_SPEC;
+ CHECK_SPEC (check) = ts & BEGIN_SPEC;
+ }
+ else
+ {
+ ts = CHECK_SPEC (insn);
+
+ CHECK_SPEC (check) = ts;
+ }
+
+ /* Future speculations. */
+ fs = DEP_TRUE;
+ if (ts & BEGIN_DATA)
+ fs |= BE_IN_DATA;
+ if (ts & BEGIN_CONTROL)
+ fs |= BE_IN_CONTROL;
+
+ /* Call the helper. */
+ process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, fs, mutate_p);
+
+ if (rec != EXIT_BLOCK_PTR)
+ {
+ /* Which types of dependencies should we use here is,
+ generally, machine-dependent question... But, for now,
+ it is not. */
+
+ if (!mutate_p)
+ {
+ add_back_forw_dep (check, insn, REG_DEP_TRUE,
+ HARD_DEP | DEP_TRUE, HARD_DEP_WEIGHT);
+ add_back_forw_dep (twin, insn, REG_DEP_OUTPUT,
+ HARD_DEP | DEP_OUTPUT, HARD_DEP_WEIGHT);
+ }
+ else
+ {
+ if (spec_info->dump)
+ fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
+ (*current_sched_info->print_insn) (insn, 0));
+
+ for (link = INSN_DEPEND (insn); link; link = INSN_DEPEND (insn))
+ delete_back_forw_dep (XEXP (link, 0), insn);
+
+ if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
+ try_ready (check);
+
+ sched_remove_insn (insn, rgn_n_insns);
+ }
+
+ add_back_forw_dep (twin, check, REG_DEP_ANTI,
+ HARD_DEP | DEP_ANTI, HARD_DEP_WEIGHT);
+ }
+ else
+ add_back_forw_dep (check, insn, REG_DEP_TRUE,
+ HARD_DEP | DEP_TRUE | DEP_OUTPUT, HARD_DEP_WEIGHT);
+
+ if (!mutate_p)
+ /* Fix priorities. If MUTATE_P is nonzero, this is not neccessary,
+ because it'll be done later in add_to_speculative_block. */
+ {
+ clear_priorities (twin);
+ calc_priorities (twin);
+ }
+}
+
+/* Removes dependency between instructions in the recovery block REC
+ and usual region instructions. It keeps inner dependences so it
+ won't be neccessary to recompute them. */
+static void
+fix_recovery_deps (basic_block rec)
+{
+ rtx note, insn, link, jump, ready_list = 0;
+ bitmap_head in_ready;
+
+ bitmap_initialize (&in_ready, 0);
+
+ /* NOTE - a basic block note. */
+ note = NEXT_INSN (BB_HEAD (rec));
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
+ insn = BB_END (rec);
+ gcc_assert (JUMP_P (insn));
+ insn = PREV_INSN (insn);
+
+ do
+ {
+ for (link = INSN_DEPEND (insn); link;)
+ {
+ rtx consumer;
+
+ consumer = XEXP (link, 0);
+
+ if (BLOCK_FOR_INSN (consumer) != rec)
+ {
+ delete_back_forw_dep (consumer, insn);
+
+ if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
+ {
+ ready_list = alloc_INSN_LIST (consumer, ready_list);
+ bitmap_set_bit (&in_ready, INSN_LUID (consumer));
+ }
+
+ link = INSN_DEPEND (insn);
+ }
+ else
+ {
+ int ds;
+
+ ds = DEP_STATUS (link);
+ gcc_assert ((ds & HARD_DEP) && (ds & DEP_TYPES) == DEP_TRUE);
+
+ link = XEXP (link, 1);
+ }
+ }
+
+ insn = PREV_INSN (insn);
+ }
+ while (insn != note);
+
+ bitmap_clear (&in_ready);
+
+ /* Try to add instructions to the ready or queue list. */
+ for (link = ready_list; link; link = XEXP (link, 1))
+ try_ready (XEXP (link, 0));
+ free_INSN_LIST_list (&ready_list);
+
+ /* Fixing jump's dependences. */
+ insn = BB_HEAD (rec);
+ jump = BB_END (rec);
+
+ gcc_assert (LABEL_P (insn));
+ insn = NEXT_INSN (insn);
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
+ /* Add dependences for JUMP from the other recovery insns. */
+ do
+ {
+ insn = NEXT_INSN (insn);
+ if (insn == jump)
+ break;
+
+ if (!INSN_DEPEND (insn))
+ add_back_forw_dep (jump, insn, REG_DEP_ANTI, HARD_DEP | DEP_ANTI,
+ HARD_DEP_WEIGHT);
+ }
+ while (1);
+}
+
+/* Saves information to keep line notes in the same block. */
+static void
+associate_line_notes_with_blocks (basic_block b)
+{
+ rtx line;
+
+ for (line = BB_HEAD (b); line; line = PREV_INSN (line))
+ if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
+ {
+ line_note_head[b->index] = line;
+ break;
+ }
+ /* Do a forward search as well, since we won't get to see the first
+ notes in a basic block. */
+ for (line = BB_HEAD (b); line; line = NEXT_INSN (line))
+ {
+ if (INSN_P (line))
+ break;
+ if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0)
+ line_note_head[b->index] = line;
+ }
+}
+
+/* Changes pattern of the INSN to NEW_PAT. */
+static void
+change_pattern (rtx insn, rtx new_pat)
+{
+ int t;
+
+ t = validate_change (insn, &PATTERN (insn), new_pat, 0);
+ gcc_assert (t);
+ /* Invalidate INSN_COST, so it'll be recalculated. */
+ INSN_COST (insn) = -1;
+ /* Invalidate INSN_TICK, so it'll be recalculated. */
+ INSN_TICK (insn) = INVALID_TICK;
+ dfa_clear_single_insn_cache (insn);
+}
+
+
+/* -1 - can't speculate,
+ 0 - for speculation with REQUEST mode it is OK to use
+ current instruction pattern,
+ 1 - need to change pattern for *NEW_PAT to be speculative. */
+static int
+speculate_insn (rtx insn, int request, rtx *new_pat)
+{
+ gcc_assert (current_sched_info->flags & DO_SPECULATION
+ && (request & SPECULATIVE));
+
+ if (!NONJUMP_INSN_P (insn)
+ || HAS_INTERNAL_DEP (insn)
+ || SCHED_GROUP_P (insn)
+ || side_effects_p (PATTERN (insn))
+ || (request & spec_info->mask) != request)
+ return -1;
+
+ gcc_assert (!RECOVERY_BLOCK (insn));
+
+ if (request & BE_IN_SPEC)
+ {
+ if (may_trap_p (PATTERN (insn)))
+ return -1;
+
+ if (!(request & BEGIN_SPEC))
+ return 0;
+ }
+
+ return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat);
+}
+
+static void
+dump_new_block_header (int i, basic_block bb, rtx head, rtx tail)
+{
+ if (!i)
+ fprintf (sched_dump,
+ ";; ======================================================\n");
+ else
+ fprintf (sched_dump,
+ ";; =====================ADVANCING TO=====================\n");
+ fprintf (sched_dump,
+ ";; -- basic block %d from %d to %d -- %s reload\n",
+ bb->index, INSN_UID (head), INSN_UID (tail),
+ (reload_completed ? "after" : "before"));
+ fprintf (sched_dump,
+ ";; ======================================================\n");
+ fprintf (sched_dump, "\n");
+}
+
+/* Unlink basic block notes and labels and saves them, so they
+ can be easyly restored. We unlink basic block notes in EBB to
+ provide back-compatability with previous code, as target backends
+ assume, that there'll be only instructions between
+ current_sched_info->{head and tail}. We restore these notes as soon
+ as we can.
+ PS: In usual case (FIRST == LAST) nothing is really done. */
+void
+unlink_bb_notes (basic_block first, basic_block last)
+{
+ /* We DON'T unlink basic block notes of the first block in the ebb. */
+ if (first == last)
+ return;
+
+ bb_header = xmalloc (last_basic_block * sizeof (*bb_header));
+
+ /* Make a sentinel. */
+ if (last->next_bb != EXIT_BLOCK_PTR)
+ bb_header[last->next_bb->index] = 0;
+
+ first = first->next_bb;
+ do
+ {
+ rtx prev, label, note, next;
+
+ label = BB_HEAD (last);
+ if (LABEL_P (label))
+ note = NEXT_INSN (label);
+ else
+ note = label;
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
+
+ prev = PREV_INSN (label);
+ next = NEXT_INSN (note);
+ gcc_assert (prev && next);
+
+ NEXT_INSN (prev) = next;
+ PREV_INSN (next) = prev;
+
+ bb_header[last->index] = label;
+
+ if (last == first)
+ break;
+
+ last = last->prev_bb;
+ }
+ while (1);
+}
+
+/* Restore basic block notes. */
+static void
+restore_bb_notes (basic_block first)
+{
+ if (!bb_header)
+ return;
+
+ /* We DON'T unlink basic block notes of the first block in the ebb. */
+ first = first->next_bb;
+ /* Remember: FIRST is actually a second basic block in the ebb. */
+
+ while (first != EXIT_BLOCK_PTR
+ && bb_header[first->index])
+ {
+ rtx prev, label, note, next;
+
+ label = bb_header[first->index];
+ prev = PREV_INSN (label);
+ next = NEXT_INSN (prev);
+
+ if (LABEL_P (label))
+ note = NEXT_INSN (label);
+ else
+ note = label;
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
+
+ bb_header[first->index] = 0;
+
+ NEXT_INSN (prev) = label;
+ NEXT_INSN (note) = next;
+ PREV_INSN (next) = note;
+
+ first = first->next_bb;
+ }
+
+ free (bb_header);
+ bb_header = 0;
+}
+
+/* Extend per basic block data structures of the scheduler. */
+static void
+extend_bb (basic_block bb)
+{
+ rtx insn;
+
+ if (write_symbols != NO_DEBUG)
+ {
+ /* Save-line-note-head:
+ Determine the line-number at the start of each basic block.
+ This must be computed and saved now, because after a basic block's
+ predecessor has been scheduled, it is impossible to accurately
+ determine the correct line number for the first insn of the block. */
+ line_note_head = xrecalloc (line_note_head, last_basic_block,
+ old_last_basic_block,
+ sizeof (*line_note_head));
+
+ if (bb)
+ associate_line_notes_with_blocks (bb);
+ else
+ FOR_EACH_BB (bb)
+ associate_line_notes_with_blocks (bb);
+ }
+
+ old_last_basic_block = last_basic_block;
+
+ if (current_sched_info->flags & USE_GLAT)
+ {
+ glat_start = xrealloc (glat_start,
+ last_basic_block * sizeof (*glat_start));
+ glat_end = xrealloc (glat_end, last_basic_block * sizeof (*glat_end));
+ }
+
+ /* The following is done to keep current_sched_info->next_tail non null. */
+
+ insn = BB_END (EXIT_BLOCK_PTR->prev_bb);
+ if (NEXT_INSN (insn) == 0
+ || (!NOTE_P (insn)
+ && !LABEL_P (insn)
+ /* Don't emit a NOTE if it would end up before a BARRIER. */
+ && !BARRIER_P (NEXT_INSN (insn))))
+ {
+ emit_note_after (NOTE_INSN_DELETED, insn);
+ /* Make insn to appear outside BB. */
+ BB_END (EXIT_BLOCK_PTR->prev_bb) = insn;
+ }
+}
+
+/* Add a basic block BB to extended basic block EBB.
+ If EBB is EXIT_BLOCK_PTR, then BB is recovery block.
+ If EBB is NULL, then BB should be a new region. */
+void
+add_block (basic_block bb, basic_block ebb)
+{
+ gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO
+ && bb->il.rtl->global_live_at_start == 0
+ && bb->il.rtl->global_live_at_end == 0);
+
+ extend_bb (bb);
+
+ glat_start[bb->index] = 0;
+ glat_end[bb->index] = 0;
+
+ if (current_sched_info->add_block)
+ /* This changes only data structures of the front-end. */
+ current_sched_info->add_block (bb, ebb);
+}
+
+/* Helper function.
+ Fix CFG after both in- and inter-block movement of
+ control_flow_insn_p JUMP. */
+static void
+fix_jump_move (rtx jump)
+{
+ basic_block bb, jump_bb, jump_bb_next;
+
+ bb = BLOCK_FOR_INSN (PREV_INSN (jump));
+ jump_bb = BLOCK_FOR_INSN (jump);
+ jump_bb_next = jump_bb->next_bb;
+
+ gcc_assert (current_sched_info->flags & SCHED_EBB
+ || (RECOVERY_BLOCK (jump)
+ && RECOVERY_BLOCK (jump) != EXIT_BLOCK_PTR));
+
+ if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next)))
+ /* if jump_bb_next is not empty. */
+ BB_END (jump_bb) = BB_END (jump_bb_next);
+
+ if (BB_END (bb) != PREV_INSN (jump))
+ /* Then there are instruction after jump that should be placed
+ to jump_bb_next. */
+ BB_END (jump_bb_next) = BB_END (bb);
+ else
+ /* Otherwise jump_bb_next is empty. */
+ BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next));
+
+ /* To make assertion in move_insn happy. */
+ BB_END (bb) = PREV_INSN (jump);
+
+ update_bb_for_insn (jump_bb_next);
+}
+
+/* Fix CFG after interblock movement of control_flow_insn_p JUMP. */
+static void
+move_block_after_check (rtx jump)
+{
+ basic_block bb, jump_bb, jump_bb_next;
+ VEC(edge,gc) *t;
+
+ bb = BLOCK_FOR_INSN (PREV_INSN (jump));
+ jump_bb = BLOCK_FOR_INSN (jump);
+ jump_bb_next = jump_bb->next_bb;
+
+ update_bb_for_insn (jump_bb);
+
+ gcc_assert (RECOVERY_BLOCK (jump)
+ || RECOVERY_BLOCK (BB_END (jump_bb_next)));
+
+ unlink_block (jump_bb_next);
+ link_block (jump_bb_next, bb);
+
+ t = bb->succs;
+ bb->succs = 0;
+ move_succs (&(jump_bb->succs), bb);
+ move_succs (&(jump_bb_next->succs), jump_bb);
+ move_succs (&t, jump_bb_next);
+
+ if (current_sched_info->fix_recovery_cfg)
+ current_sched_info->fix_recovery_cfg
+ (bb->index, jump_bb->index, jump_bb_next->index);
+}
+
+/* Helper function for move_block_after_check. */
+static void
+move_succs (VEC(edge,gc) **succsp, basic_block to)
+{
+ edge e;
+ edge_iterator ei;
+
+ gcc_assert (to->succs == 0);
+
+ to->succs = *succsp;
+
+ FOR_EACH_EDGE (e, ei, to->succs)
+ e->src = to;
+
+ *succsp = 0;
+}
+
+/* Initialize GLAT (global_live_at_{start, end}) structures.
+ GLAT structures are used to substitute global_live_{start, end}
+ regsets during scheduling. This is neccessary to use such functions
+ as split_block, that assume consistancy of register live information. */
+static void
+init_glat (void)
+{
+ basic_block bb;
+
+ FOR_ALL_BB (bb)
+ init_glat1 (bb);
+}
+
+/* Helper function for init_glat. */
+static void
+init_glat1 (basic_block bb)
+{
+ gcc_assert (bb->il.rtl->global_live_at_start != 0
+ && bb->il.rtl->global_live_at_end != 0);
+
+ glat_start[bb->index] = bb->il.rtl->global_live_at_start;
+ glat_end[bb->index] = bb->il.rtl->global_live_at_end;
+
+ if (current_sched_info->flags & DETACH_LIFE_INFO)
+ {
+ bb->il.rtl->global_live_at_start = 0;
+ bb->il.rtl->global_live_at_end = 0;
+ }
+}
+
+/* Attach reg_live_info back to basic blocks.
+ Also save regsets, that should not have been changed during scheduling,
+ for checking purposes (see check_reg_live). */
+void
+attach_life_info (void)
+{
+ basic_block bb;
+
+ FOR_ALL_BB (bb)
+ attach_life_info1 (bb);
+}
+
+/* Helper function for attach_life_info. */
+static void
+attach_life_info1 (basic_block bb)
+{
+ gcc_assert (bb->il.rtl->global_live_at_start == 0
+ && bb->il.rtl->global_live_at_end == 0);
+
+ if (glat_start[bb->index])
+ {
+ gcc_assert (glat_end[bb->index]);
+
+ bb->il.rtl->global_live_at_start = glat_start[bb->index];
+ bb->il.rtl->global_live_at_end = glat_end[bb->index];
+
+ /* Make them NULL, so they won't be freed in free_glat. */
+ glat_start[bb->index] = 0;
+ glat_end[bb->index] = 0;
+
+#ifdef ENABLE_CHECKING
+ if (bb->index < NUM_FIXED_BLOCKS
+ || current_sched_info->region_head_or_leaf_p (bb, 0))
+ {
+ glat_start[bb->index] = ALLOC_REG_SET (®_obstack);
+ COPY_REG_SET (glat_start[bb->index],
+ bb->il.rtl->global_live_at_start);
+ }
+
+ if (bb->index < NUM_FIXED_BLOCKS
+ || current_sched_info->region_head_or_leaf_p (bb, 1))
+ {
+ glat_end[bb->index] = ALLOC_REG_SET (®_obstack);
+ COPY_REG_SET (glat_end[bb->index], bb->il.rtl->global_live_at_end);
+ }
+#endif
+ }
+ else
+ {
+ gcc_assert (!glat_end[bb->index]);
+
+ bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack);
+ bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack);
+ }
+}
+
+/* Free GLAT information. */
+static void
+free_glat (void)
+{
+#ifdef ENABLE_CHECKING
+ if (current_sched_info->flags & DETACH_LIFE_INFO)
+ {
+ basic_block bb;
+
+ FOR_ALL_BB (bb)
+ {
+ if (glat_start[bb->index])
+ FREE_REG_SET (glat_start[bb->index]);
+ if (glat_end[bb->index])
+ FREE_REG_SET (glat_end[bb->index]);
+ }
+ }
+#endif
+
+ free (glat_start);
+ free (glat_end);
+}
+
+/* Remove INSN from the instruction stream.
+ INSN should have any dependencies. */
+static void
+sched_remove_insn (rtx insn, int *rgn_n_insns)
+{
+ change_queue_index (insn, QUEUE_NOWHERE);
+ current_sched_info->add_remove_insn (insn, 1);
+ remove_insn (insn);
+ (*rgn_n_insns)--;
+}
+
+/* Clear priorities of all instructions, that are
+ forward dependent on INSN. */
+static void
+clear_priorities (rtx insn)
+{
+ rtx link;
+
+ for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+ {
+ rtx pro;
+
+ pro = XEXP (link, 0);
+ if (INSN_PRIORITY_KNOWN (pro))
+ {
+ INSN_PRIORITY_KNOWN (pro) = 0;
+ clear_priorities (pro);
+ }
+ }
+}
+
+/* Recompute priorities of instructions, whose priorities might have been
+ changed due to changes in INSN. */
+static void
+calc_priorities (rtx insn)
+{
+ rtx link;
+
+ for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
+ {
+ rtx pro;
+
+ pro = XEXP (link, 0);
+ if (!INSN_PRIORITY_KNOWN (pro))
+ {
+ priority (pro);
+ calc_priorities (pro);
+ }
+ }
+}
+
+#ifdef ENABLE_CHECKING
+void
+debug_spec_status (int s)
+{
+ dump_spec_status (s, stderr);
+}
+
+static void
+dump_spec_status (int s, FILE *f)
+{
+ if (s & BEGIN_DATA)
+ fprintf (f, "BEGIN_DATA ");
+ if (s & BE_IN_DATA)
+ fprintf (f, "BE_IN_DATA ");
+ if (s & BEGIN_CONTROL)
+ fprintf (f, "BEGIN_CONTROL ");
+ if (s & BE_IN_CONTROL)
+ fprintf (f, "BE_IN_CONTROL ");
+
+ if (s & HARD_DEP)
+ fprintf (f, "HARD_DEP ");
+
+ if (s & DEP_TRUE)
+ fprintf (f, "DEP_TRUE ");
+ if (s & DEP_ANTI)
+ fprintf (f, "DEP_ANTI ");
+ if (s & DEP_OUTPUT)
+ fprintf (f, "DEP_OUTPUT ");
+
+ fprintf (f, "\n");
+}
+
+/* Helper function for check_cfg. */
+static int
+has_edge_p (VEC(edge,gc) *el, int type)
+{
+ edge e;
+ edge_iterator ei;
+
+ FOR_EACH_EDGE (e, ei, el)
+ if (e->flags & type)
+ return 1;
+ return 0;
+}
+
+/* Checks few properties of CFG. */
+static void
+check_cfg (rtx head, rtx tail)
+{
+ rtx next_tail;
+ basic_block bb = 0;
+ int not_first = 0, not_last;
+
+ if (head == NULL)
+ head = get_insns ();
+ if (tail == NULL)
+ tail = get_last_insn ();
+ next_tail = NEXT_INSN (tail);
+
+ do
+ {
+ not_last = head != tail;
+
+ if (not_first)
+ gcc_assert (NEXT_INSN (PREV_INSN (head)) == head);
+ if (not_last)
+ gcc_assert (PREV_INSN (NEXT_INSN (head)) == head);
+
+ if (LABEL_P (head)
+ || (NOTE_INSN_BASIC_BLOCK_P (head)
+ && (!not_first
+ || (not_first && !LABEL_P (PREV_INSN (head))))))
+ {
+ gcc_assert (bb == 0);
+ bb = BLOCK_FOR_INSN (head);
+ if (bb != 0)
+ gcc_assert (BB_HEAD (bb) == head);
+ else
+ /* This is the case of jump table. See inside_basic_block_p (). */
+ gcc_assert (LABEL_P (head) && !inside_basic_block_p (head));
+ }
+
+ if (bb == 0)
+ {
+ gcc_assert (!inside_basic_block_p (head));
+ head = NEXT_INSN (head);
+ }
+ else
+ {
+ gcc_assert (inside_basic_block_p (head)
+ || NOTE_P (head));
+ gcc_assert (BLOCK_FOR_INSN (head) == bb);
+
+ if (LABEL_P (head))
+ {
+ head = NEXT_INSN (head);
+ gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head));
+ }
+ else
+ {
+ if (control_flow_insn_p (head))
+ {
+ gcc_assert (BB_END (bb) == head);
+
+ if (any_uncondjump_p (head))
+ gcc_assert (EDGE_COUNT (bb->succs) == 1
+ && BARRIER_P (NEXT_INSN (head)));
+ else if (any_condjump_p (head))
+ gcc_assert (EDGE_COUNT (bb->succs) > 1
+ && !BARRIER_P (NEXT_INSN (head)));
+ }
+ if (BB_END (bb) == head)
+ {
+ if (EDGE_COUNT (bb->succs) > 1)
+ gcc_assert (control_flow_insn_p (head)
+ || has_edge_p (bb->succs, EDGE_COMPLEX));
+ bb = 0;
+ }
+
+ head = NEXT_INSN (head);
+ }
+ }
+
+ not_first = 1;
+ }
+ while (head != next_tail);
+
+ gcc_assert (bb == 0);
+}
+
+static void
+check_sched_flags (int f, spec_info_t spec_info)
+{
+ if (flag_sched_stalled_insns)
+ gcc_assert (!(f & DO_SPECULATION));
+ if (f & DO_SPECULATION)
+ gcc_assert (!flag_sched_stalled_insns
+ && (f & DETACH_LIFE_INFO)
+ && spec_info
+ && spec_info->mask);
+ if (f & DETACH_LIFE_INFO)
+ gcc_assert (f & USE_GLAT);
+}
+
+/* Checks global_live_at_{start, end} regsets. */
+void
+check_reg_live (void)
+{
+ basic_block bb;
+
+ FOR_ALL_BB (bb)
+ {
+ int i;
+
+ i = bb->index;
+
+ if (glat_start[i])
+ gcc_assert (bitmap_equal_p (bb->il.rtl->global_live_at_start,
+ glat_start[i]));
+ if (glat_end[i])
+ gcc_assert (bitmap_equal_p (bb->il.rtl->global_live_at_end,
+ glat_end[i]));
+ }
+}
+#endif /* ENABLE_CHECKING */
+
#endif /* INSN_SCHEDULING */
Index: gcc/modulo-sched.c
===================================================================
--- gcc/modulo-sched.c (.../insn-tick) (revision 2239)
+++ gcc/modulo-sched.c (.../recovery) (revision 2239)
@@ -269,6 +269,10 @@ static struct sched_info sms_sched_info
NULL, NULL,
0, 0, 0,
+ NULL, NULL, NULL, NULL, NULL, NULL,
+#ifdef ENABLE_CHECKING
+ NULL,
+#endif
0
};
@@ -318,7 +322,7 @@ const_iteration_count (rtx count_reg, ba
if (! pre_header)
return NULL_RTX;
- get_block_head_tail (pre_header->index, &head, &tail);
+ get_ebb_head_tail (pre_header, pre_header, &head, &tail);
for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
if (INSN_P (insn) && single_set (insn) &&
@@ -797,7 +801,7 @@ loop_single_full_bb_p (struct loop *loop
/* Make sure that basic blocks other than the header
have only notes labels or jumps. */
- get_block_head_tail (bbs[i]->index, &head, &tail);
+ get_ebb_head_tail (bbs[i], bbs[i], &head, &tail);
for (; head != NEXT_INSN (tail); head = NEXT_INSN (head))
{
if (NOTE_P (head) || LABEL_P (head)
@@ -1011,7 +1015,7 @@ sms_schedule (FILE *dump_file)
bb = loop->header;
- get_block_head_tail (bb->index, &head, &tail);
+ get_ebb_head_tail (bb, bb, &head, &tail);
latch_edge = loop_latch_edge (loop);
gcc_assert (loop->single_exit);
if (loop->single_exit->count)
@@ -1112,7 +1116,7 @@ sms_schedule (FILE *dump_file)
if (dump_file)
print_ddg (dump_file, g);
- get_block_head_tail (loop->header->index, &head, &tail);
+ get_ebb_head_tail (loop->header, loop->header, &head, &tail);
latch_edge = loop_latch_edge (loop);
gcc_assert (loop->single_exit);
Index: gcc/genattr.c
===================================================================
--- gcc/genattr.c (.../insn-tick) (revision 2239)
+++ gcc/genattr.c (.../recovery) (revision 2239)
@@ -255,6 +255,7 @@ main (int argc, char **argv)
printf (" define_insn_reservation will be changed after\n");
printf (" last call of dfa_start. */\n");
printf ("extern void dfa_clean_insn_cache (void);\n\n");
+ printf ("extern void dfa_clear_single_insn_cache (rtx);\n\n");
printf ("/* Initiate and finish work with DFA. They should be\n");
printf (" called as the first and the last interface\n");
printf (" functions. */\n");
Index: gcc/sched-deps.c
===================================================================
--- gcc/sched-deps.c (.../insn-tick) (revision 2239)
+++ gcc/sched-deps.c (.../recovery) (revision 2239)
@@ -1805,18 +1805,35 @@ init_dependency_caches (int luid)
what we consider "very high". */
if (luid / n_basic_blocks > 100 * 5)
{
- int i;
+ cache_size = 0;
+ extend_dependency_caches (luid, 1);
+ }
+}
+
+/* Create or extend (depending on CREATE_P) dependency caches to
+ size N. */
+void
+extend_dependency_caches (int n, int create_p)
+{
+ if (create_p || true_dependency_cache)
+ {
+ int i, luid = cache_size + n;
- true_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
- output_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
- anti_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
+ true_dependency_cache = xrealloc (true_dependency_cache,
+ luid * sizeof (bitmap_head));
+ output_dependency_cache = xrealloc (output_dependency_cache,
+ luid * sizeof (bitmap_head));
+ anti_dependency_cache = xrealloc (anti_dependency_cache,
+ luid * sizeof (bitmap_head));
#ifdef ENABLE_CHECKING
- forward_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
+ forward_dependency_cache = xrealloc (forward_dependency_cache,
+ luid * sizeof (bitmap_head));
#endif
if (current_sched_info->flags & DO_SPECULATION)
- spec_dependency_cache = xmalloc (luid * sizeof (bitmap_head));
+ spec_dependency_cache = xrealloc (spec_dependency_cache,
+ luid * sizeof (bitmap_head));
- for (i = 0; i < luid; i++)
+ for (i = cache_size; i < luid; i++)
{
bitmap_initialize (&true_dependency_cache[i], 0);
bitmap_initialize (&output_dependency_cache[i], 0);
Index: gcc/target-def.h
===================================================================
--- gcc/target-def.h (.../insn-tick) (revision 2239)
+++ gcc/target-def.h (.../recovery) (revision 2239)
@@ -266,6 +266,14 @@ Foundation, 51 Franklin Street, Fifth Fl
#define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD_GUARD 0
#define TARGET_SCHED_DFA_NEW_CYCLE 0
#define TARGET_SCHED_IS_COSTLY_DEPENDENCE 0
+#define TARGET_SCHED_ADJUST_COST_2 0
+#define TARGET_SCHED_H_I_D_EXTENDED 0
+#define TARGET_SCHED_SPECULATE_INSN 0
+#define TARGET_SCHED_NEEDS_BLOCK_P 0
+#define TARGET_SCHED_GEN_CHECK 0
+#define TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD_GUARD_SPEC 0
+#define TARGET_SCHED_SET_SCHED_FLAGS 0
+
#define TARGET_SCHED \
{TARGET_SCHED_ADJUST_COST, \
@@ -286,7 +294,14 @@ Foundation, 51 Franklin Street, Fifth Fl
TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD, \
TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD_GUARD, \
TARGET_SCHED_DFA_NEW_CYCLE, \
- TARGET_SCHED_IS_COSTLY_DEPENDENCE}
+ TARGET_SCHED_IS_COSTLY_DEPENDENCE, \
+ TARGET_SCHED_ADJUST_COST_2, \
+ TARGET_SCHED_H_I_D_EXTENDED, \
+ TARGET_SCHED_SPECULATE_INSN, \
+ TARGET_SCHED_NEEDS_BLOCK_P, \
+ TARGET_SCHED_GEN_CHECK, \
+ TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DFA_LOOKAHEAD_GUARD_SPEC, \
+ TARGET_SCHED_SET_SCHED_FLAGS}
#define TARGET_VECTORIZE_BUILTIN_MASK_FOR_LOAD 0
Index: gcc/rtl.h
===================================================================
--- gcc/rtl.h (.../insn-tick) (revision 2239)
+++ gcc/rtl.h (.../recovery) (revision 2239)
@@ -1658,6 +1658,7 @@ rtx alloc_DEPS_LIST (rtx, rtx, int, int)
void remove_free_DEPS_LIST_elem (rtx, rtx *);
void remove_free_INSN_LIST_elem (rtx, rtx *);
rtx remove_list_elem (rtx, rtx *);
+rtx copy_DEPS_LIST_list (rtx);
/* regclass.c */
Index: gcc/sched-int.h
===================================================================
--- gcc/sched-int.h (.../insn-tick) (revision 2239)
+++ gcc/sched-int.h (.../recovery) (revision 2239)
@@ -142,10 +142,12 @@ struct sched_info
int (*can_schedule_ready_p) (rtx);
/* Return nonzero if there are more insns that should be scheduled. */
int (*schedule_more_p) (void);
- /* Called after an insn has all its dependencies resolved. Return nonzero
- if it should be moved to the ready list or the queue, or zero if we
- should silently discard it. */
- int (*new_ready) (rtx);
+ /* Called after an insn has all its hard dependencies resolved.
+ Adjusts status of instruction (which is passed through second parameter)
+ to indicate if instruction should be moved to the ready list or the
+ queue, or if it should silently discard it (until next resolved
+ dependence). */
+ void (*new_ready) (rtx, int *);
/* Compare priority of two insns. Return a positive number if the second
insn is to be preferred for scheduling, and a negative one if the first
is to be preferred. Zero if they are equally good. */
@@ -180,12 +182,77 @@ struct sched_info
/* Maximum priority that has been assigned to an insn. */
int sched_max_insns_priority;
+
+ /* Hooks to support speculative scheduling. */
+
+ /* Called to notify frontend that instruction is being added (second
+ parameter == 0) or removed (second parameter == 1). */
+ void (*add_remove_insn) (rtx, int);
+
+ /* Called to notify frontend that instruction is being scheduled.
+ The first parameter - instruction to scheduled, the second parameter -
+ last scheduled instruction. */
+ void (*begin_schedule_ready) (rtx, rtx);
+
+ /* Adjust points (second parameter) that will get instruction (first
+ parameter). Return adjusted points. */
+ int (*insn_points) (rtx, int);
+
+ /* Called to notify frontend, that new basic block is being added.
+ The first parameter - new basic block.
+ The second parameter - block, after which new basic block is being added,
+ or EXIT_BLOCK_PTR, if recovery block is being added,
+ or NULL, if standalone block is being added. */
+ void (*add_block) (basic_block, basic_block);
+
+ /* If second parameter not NULL, return nonnull value, if basic block should
+ be advanced.
+ if second parameter == NULL, return next basic block in EBB.
+ First parameter - current basic block in EBB. */
+ basic_block (*advance_target_bb) (basic_block, rtx);
+
+ /* Called after blocks were rearranged due to movement of jump instruction.
+ The first parameter - index of basic block, in which jump currently is.
+ The second parameter - index of basic block, in which jump used
+ to be.
+ The third parameter - index of basic block, that follows the second
+ parameter. */
+ void (*fix_recovery_cfg) (int, int, int);
+
+#ifdef ENABLE_CHECKING
+ /* If the second parameter is zero, return nonzero, if block is head of the
+ region.
+ If the second parameter is nonzero, return nonzero, if block is leaf of
+ the region.
+ global_live_at_start should not change in region heads and
+ global_live_at_end should not change in region leafs due to scheduling. */
+ int (*region_head_or_leaf_p) (basic_block, int);
+#endif
/* ??? FIXME: should use straight bitfields inside sched_info instead of
this flag field. */
unsigned int flags;
};
+/* This structure holds description properties for speculative scheduling. */
+struct spec_info_def
+{
+ /* Holds types of alloweded speculations: BEGIN_{DATA|CONTROL},
+ BE_IN_{DATA_CONTROL}. */
+ int mask;
+
+ /* Dump file for additional information on speculative scheduling. */
+ FILE *dump;
+
+ /* Minimum number of points that should a speculative instruction get to
+ be scheduled. */
+ int spec_points_cutoff;
+
+ /* Flags from the enum SPEC_SCHED_FLAGS. */
+ int flags;
+};
+typedef struct spec_info_def *spec_info_t;
+
extern struct sched_info *current_sched_info;
/* Indexed by INSN_UID, the collection of all data associated with
@@ -250,9 +317,32 @@ struct haifa_insn_data
/* Nonzero if instruction has internal dependence
(e.g. add_dependence was invoked with (insn == elem)). */
unsigned int has_internal_dep : 1;
+
+ /* What speculations are neccessary to apply to schedule the instruction. */
+ int todo_spec;
+ /* What speculations were already applied. */
+ int done_spec;
+ /* What speculations are checked by this instruction. */
+ int check_spec;
+
+ /* insn_points are equal to (MAX_SCHED_POINTS - insn_anti_points). */
+ int insn_anti_points;
+
+ /* Recovery block for speculation checks. */
+ basic_block recovery_block;
+
+ /* Original pattern of the instruction. */
+ rtx orig_pat;
+
+ /* This is target-specific information. */
+ int check_no;
};
extern struct haifa_insn_data *h_i_d;
+/* Used only if (current_sched_info->flags & USE_GLAT) != 0.
+ These regsets store global_live_at_{start, end} information
+ for each basic block. */
+extern regset *glat_start, *glat_end;
/* Accessor macros for h_i_d. There are more in haifa-sched.c and
sched-rgn.c. */
@@ -265,6 +355,16 @@ extern struct haifa_insn_data *h_i_d;
#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost)
#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
#define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep)
+#define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec)
+#define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec)
+#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec)
+#define INSN_POINTS(INSN) (MAX_SCHED_POINTS - \
+ (h_i_d[INSN_UID (INSN)].insn_anti_points))
+#define SET_INSN_POINTS(INSN, P) (h_i_d[INSN_UID (INSN)].insn_anti_points =\
+ MAX_SCHED_POINTS - (P))
+#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block)
+#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat)
+#define CHECK_NO(INSN) (h_i_d[INSN_UID (INSN)].check_no)
#define DEP_STATUS(LINK) XINT(LINK, 2)
#define DEP_WEIGHT(LINK) XINT(LINK, 3)
@@ -341,9 +441,28 @@ enum SCHED_FLAGS {
/* Perform data or control (or both) speculation.
Results in generation of data and control speculative dependencies.
Requires USE_DEPS_LIST set. */
- DO_SPECULATION = USE_DEPS_LIST << 1
+ DO_SPECULATION = USE_DEPS_LIST << 1,
+ SCHED_RGN = DO_SPECULATION << 1,
+ SCHED_EBB = SCHED_RGN << 1,
+ DETACH_LIFE_INFO = SCHED_EBB << 1,
+ USE_GLAT = DETACH_LIFE_INFO << 1
+};
+
+enum SPEC_SCHED_FLAGS {
+ COUNT_SPEC_IN_CRITICAL_PATH = 1,
+ USE_SPEC_POINTS = COUNT_SPEC_IN_CRITICAL_PATH << 1,
+ USE_ISSUE_POINTS = USE_SPEC_POINTS << 1,
+ USE_SORT_POINTS = USE_ISSUE_POINTS << 1,
+ PREFER_NON_DATA_SPEC = USE_SORT_POINTS << 1,
+ PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
};
+#define MIN_SCHED_POINTS 1
+#define MAX_SCHED_POINTS 1000
+
+#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && NOTE_LINE_NUMBER (NOTE) !=\
+ NOTE_INSN_BASIC_BLOCK)
+
extern FILE *sched_dump;
extern int sched_verbose;
@@ -441,6 +560,7 @@ extern void compute_forward_dependences
extern rtx find_insn_list (rtx, rtx);
extern void init_dependency_caches (int);
extern void free_dependency_caches (void);
+extern void extend_dependency_caches (int, int);
extern void init_deps_global (void);
extern void finish_deps_global (void);
extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
@@ -451,7 +571,7 @@ extern void delete_back_forw_dep (rtx, r
/* Functions in haifa-sched.c. */
extern int haifa_classify_insn (rtx);
-extern void get_block_head_tail (int, rtx *, rtx *);
+extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
extern int no_real_insns_p (rtx, rtx);
extern void rm_line_notes (rtx, rtx);
@@ -463,10 +583,19 @@ extern void rm_other_notes (rtx, rtx);
extern int insn_cost (rtx, rtx, rtx);
extern int set_priorities (rtx, rtx);
-extern void schedule_block (int, int);
+extern void schedule_block (basic_block *, int *);
extern void sched_init (FILE *);
extern void sched_finish (void);
extern int try_ready (rtx);
+extern void * xrecalloc (void *, size_t, size_t, size_t);
+extern void unlink_bb_notes (basic_block, basic_block);
+extern void add_block (basic_block, basic_block);
+extern void attach_life_info (void);
+
+#ifdef ENABLE_CHECKING
+extern void debug_spec_status (int);
+extern void check_reg_live (void);
+#endif
#endif /* GCC_SCHED_INT_H */
Index: gcc/sched-rgn.c
===================================================================
--- gcc/sched-rgn.c (.../insn-tick) (revision 2239)
+++ gcc/sched-rgn.c (.../recovery) (revision 2239)
@@ -96,8 +96,13 @@ static bool sched_is_disabled_for_curren
control flow graph edges, in the 'up' direction. */
typedef struct
{
- int rgn_nr_blocks; /* Number of blocks in region. */
- int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
+ int rgn_nr_blocks; /* Number of extended basic blocks in region. */
+ int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */
+ /* Dependencies for this region are already computed. Basically, indicates,
+ that this is recovery block. */
+ unsigned int dont_calc_deps : 1;
+ /* This region has at least one non-trivial ebb. */
+ unsigned int has_real_ebb : 1;
}
region;
@@ -121,6 +126,8 @@ static int *containing_rgn;
#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
+#define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
+#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
#define BLOCK_TO_BB(block) (block_to_bb[block])
#define CONTAINING_RGN(block) (containing_rgn[block])
@@ -136,8 +143,13 @@ extern void debug_live (int, int);
static int current_nr_blocks;
static int current_blocks;
-/* The mapping from bb to block. */
-#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)])
+/* The mapping from ebb to block. */
+/* ebb_head [i] - is index in rgn_bb_table, while
+ EBB_HEAD (i) - is basic block index.
+ BASIC_BLOCK (EBB_HEAD (i)) - head of ebb. */
+#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
+#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
+#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
/* Target info declarations.
@@ -246,6 +258,12 @@ static edgeset *pot_split;
/* For every bb, a set of its ancestor edges. */
static edgeset *ancestor_edges;
+/* Array of EBBs sizes. Currently we can get a ebb only through
+ splitting of currently scheduling block, therefore, we don't need
+ ebb_head array for every region, its sufficient to hold it only
+ for current one. */
+static int *ebb_head;
+
static void compute_dom_prob_ps (int);
#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN))))
@@ -383,13 +401,12 @@ debug_regions (void)
rgn_table[rgn].rgn_nr_blocks);
fprintf (sched_dump, ";;\tbb/block: ");
- for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
- {
- current_blocks = RGN_BLOCKS (rgn);
+ /* We don't have ebb_head initialized yet, so we can't use
+ BB_TO_BLOCK (). */
+ current_blocks = RGN_BLOCKS (rgn);
- gcc_assert (bb == BLOCK_TO_BB (BB_TO_BLOCK (bb)));
- fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb));
- }
+ for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++)
+ fprintf (sched_dump, " %d/%d ", bb, rgn_bb_table[current_blocks + bb]);
fprintf (sched_dump, "\n\n");
}
@@ -411,6 +428,8 @@ find_single_block_region (void)
rgn_bb_table[nr_regions] = bb->index;
RGN_NR_BLOCKS (nr_regions) = 1;
RGN_BLOCKS (nr_regions) = nr_regions;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
CONTAINING_RGN (bb->index) = nr_regions;
BLOCK_TO_BB (bb->index) = 0;
nr_regions++;
@@ -854,6 +873,8 @@ find_rgns (void)
rgn_bb_table[idx] = bb->index;
RGN_NR_BLOCKS (nr_regions) = num_bbs;
RGN_BLOCKS (nr_regions) = idx++;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
CONTAINING_RGN (bb->index) = nr_regions;
BLOCK_TO_BB (bb->index) = count = 0;
@@ -923,6 +944,8 @@ find_rgns (void)
rgn_bb_table[idx] = bb->index;
RGN_NR_BLOCKS (nr_regions) = 1;
RGN_BLOCKS (nr_regions) = idx++;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
CONTAINING_RGN (bb->index) = nr_regions++;
BLOCK_TO_BB (bb->index) = 0;
}
@@ -1154,6 +1177,8 @@ find_more_rgns (int *degree, int *idxp,
degree[bbn] = -1;
rgn_bb_table[idx] = bbn;
RGN_BLOCKS (nr_regions) = idx++;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
CONTAINING_RGN (bbn) = nr_regions;
BLOCK_TO_BB (bbn) = 0;
@@ -1207,6 +1232,8 @@ find_more_rgns (int *degree, int *idxp,
{
RGN_BLOCKS (nr_regions) = idx;
RGN_NR_BLOCKS (nr_regions) = 1;
+ RGN_DONT_CALC_DEPS (nr_regions) = 0;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
nr_regions++;
}
@@ -1258,6 +1285,9 @@ compute_dom_prob_ps (int bb)
edge_iterator in_ei, out_ei;
edge in_edge, out_edge;
+ /* We shouldn't have any real ebbs yet. */
+ gcc_assert (ebb_head [bb] == bb + current_blocks);
+
prob[bb] = 0.0;
if (IS_RGN_ENTRY (bb))
{
@@ -1535,8 +1565,14 @@ check_live_1 (int src, rtx x)
{
basic_block b = candidate_table[src].split_bbs.first_member[i];
- if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start,
- regno + j))
+ /* We can have split blocks, that were recently generated.
+ such blocks are always outside current region. */
+ gcc_assert (glat_start[b->index]
+ || CONTAINING_RGN (b->index)
+ != CONTAINING_RGN (BB_TO_BLOCK (src)));
+ if (!glat_start[b->index]
+ || REGNO_REG_SET_P (glat_start[b->index],
+ regno + j))
{
return 0;
}
@@ -1550,7 +1586,11 @@ check_live_1 (int src, rtx x)
{
basic_block b = candidate_table[src].split_bbs.first_member[i];
- if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start, regno))
+ gcc_assert (glat_start[b->index]
+ || CONTAINING_RGN (b->index)
+ != CONTAINING_RGN (BB_TO_BLOCK (src)));
+ if (!glat_start[b->index]
+ || REGNO_REG_SET_P (glat_start[b->index], regno))
{
return 0;
}
@@ -1609,8 +1649,7 @@ update_live_1 (int src, rtx x)
{
basic_block b = candidate_table[src].update_bbs.first_member[i];
- SET_REGNO_REG_SET (b->il.rtl->global_live_at_start,
- regno + j);
+ SET_REGNO_REG_SET (glat_start[b->index], regno + j);
}
}
}
@@ -1620,7 +1659,7 @@ update_live_1 (int src, rtx x)
{
basic_block b = candidate_table[src].update_bbs.first_member[i];
- SET_REGNO_REG_SET (b->il.rtl->global_live_at_start, regno);
+ SET_REGNO_REG_SET (glat_start[b->index], regno);
}
}
}
@@ -1896,25 +1935,36 @@ static int sched_target_n_insns;
static int target_n_insns;
/* The number of insns from the entire region scheduled so far. */
static int sched_n_insns;
-/* Nonzero if the last scheduled insn was a jump. */
-static int last_was_jump;
/* Implementations of the sched_info functions for region scheduling. */
static void init_ready_list (void);
static int can_schedule_ready_p (rtx);
-static int new_ready (rtx);
+static void begin_schedule_ready (rtx, rtx);
+static void new_ready (rtx, int *);
static int schedule_more_p (void);
static const char *rgn_print_insn (rtx, int);
static int rgn_rank (rtx, rtx);
static int contributes_to_priority (rtx, rtx);
static void compute_jump_reg_dependencies (rtx, regset, regset, regset);
+/* Functions for speculative scheduling. */
+static void add_remove_insn (rtx, int);
+static int insn_points (rtx, int);
+static void extend_regions (void);
+static void add_block1 (basic_block, basic_block);
+static void fix_recovery_cfg (int, int, int);
+static basic_block advance_target_bb (basic_block, rtx);
+static void check_dead_notes1 (int, sbitmap);
+#ifdef ENABLE_CHECKING
+static int region_head_or_leaf_p (basic_block, int);
+#endif
+
/* Return nonzero if there are more insns that should be scheduled. */
static int
schedule_more_p (void)
{
- return ! last_was_jump && sched_target_n_insns < target_n_insns;
+ return sched_target_n_insns < target_n_insns;
}
/* Add all insns that are initially ready to the ready list READY. Called
@@ -1931,7 +1981,6 @@ init_ready_list (void)
target_n_insns = 0;
sched_target_n_insns = 0;
sched_n_insns = 0;
- last_was_jump = 0;
/* Print debugging information. */
if (sched_verbose >= 5)
@@ -1962,6 +2011,8 @@ init_ready_list (void)
{
try_ready (insn);
target_n_insns++;
+
+ gcc_assert (!(TODO_SPEC (insn) & BEGIN_CONTROL));
}
/* Add to ready list all 'ready' insns in valid source blocks.
@@ -1974,7 +2025,8 @@ init_ready_list (void)
rtx src_next_tail;
rtx tail, head;
- get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail);
+ get_ebb_head_tail (EBB_FIRST_BB (bb_src), EBB_LAST_BB (bb_src),
+ &head, &tail);
src_next_tail = NEXT_INSN (tail);
src_head = head;
@@ -1990,18 +2042,29 @@ init_ready_list (void)
static int
can_schedule_ready_p (rtx insn)
{
- if (JUMP_P (insn))
- last_was_jump = 1;
+ /* An interblock motion? */
+ if (INSN_BB (insn) != target_bb
+ && IS_SPECULATIVE_INSN (insn)
+ && !check_live (insn, INSN_BB (insn)))
+ return 0;
+ else
+ return 1;
+}
+/* Updates counter and other information. Splited from can_schedule_ready_p ()
+ because when we schedule insn speculatively then insn passed to
+ can_schedule_ready_p () differs from the one passed to
+ begin_schedule_ready (). */
+static void
+begin_schedule_ready (rtx insn, rtx last ATTRIBUTE_UNUSED)
+{
/* An interblock motion? */
if (INSN_BB (insn) != target_bb)
{
- basic_block b1;
-
if (IS_SPECULATIVE_INSN (insn))
{
- if (!check_live (insn, INSN_BB (insn)))
- return 0;
+ gcc_assert (check_live (insn, INSN_BB (insn)));
+
update_live (insn, INSN_BB (insn));
/* For speculative load, mark insns fed by it. */
@@ -2011,32 +2074,6 @@ can_schedule_ready_p (rtx insn)
nr_spec++;
}
nr_inter++;
-
- /* Update source block boundaries. */
- b1 = BLOCK_FOR_INSN (insn);
- if (insn == BB_HEAD (b1) && insn == BB_END (b1))
- {
- /* We moved all the insns in the basic block.
- Emit a note after the last insn and update the
- begin/end boundaries to point to the note. */
- rtx note = emit_note_after (NOTE_INSN_DELETED, insn);
- BB_HEAD (b1) = note;
- BB_END (b1) = note;
- }
- else if (insn == BB_END (b1))
- {
- /* We took insns from the end of the basic block,
- so update the end of block boundary so that it
- points to the first insn we did not move. */
- BB_END (b1) = PREV_INSN (insn);
- }
- else if (insn == BB_HEAD (b1))
- {
- /* We took insns from the start of the basic block,
- so update the start of block boundary so that
- it points to the first insn we did not move. */
- BB_HEAD (b1) = NEXT_INSN (insn);
- }
}
else
{
@@ -2044,28 +2081,40 @@ can_schedule_ready_p (rtx insn)
sched_target_n_insns++;
}
sched_n_insns++;
-
- return 1;
}
-/* Called after INSN has all its dependencies resolved. Return nonzero
+/* Called after INSN has all its hard dependencies resolved. Return nonzero
if it should be moved to the ready list or the queue, or zero if we
should silently discard it. */
-static int
-new_ready (rtx next)
+static void
+new_ready (rtx next, int *new_ts)
{
- /* For speculative insns, before inserting to ready/queue,
- check live, exception-free, and issue-delay. */
- if (INSN_BB (next) != target_bb
- && (!IS_VALID (INSN_BB (next))
+ if (INSN_BB (next) != target_bb)
+ {
+ int not_ex_free = 0;
+
+ /* For speculative insns, before inserting to ready/queue,
+ check live, exception-free, and issue-delay. */
+ if (!IS_VALID (INSN_BB (next))
|| CANT_MOVE (next)
|| (IS_SPECULATIVE_INSN (next)
&& ((recog_memoized (next) >= 0
- && min_insn_conflict_delay (curr_state, next, next) > 3)
+ && min_insn_conflict_delay (curr_state, next, next)
+ > PARAM_VALUE (PARAM_MAX_SCHED_INSN_CONFLICT_DELAY))
+ || RECOVERY_BLOCK (next)
|| !check_live (next, INSN_BB (next))
- || !is_exception_free (next, INSN_BB (next), target_bb)))))
- return 0;
- return 1;
+ || (not_ex_free = !is_exception_free (next, INSN_BB (next), target_bb)))))
+ {
+ if (not_ex_free
+ /* We are here because is_exception_free () == false.
+ But we possibly can handle that with control speculation. */
+ && current_sched_info->flags & DO_SPECULATION)
+ /* Here we got new control-speculative instruction. */
+ *new_ts |= BEGIN_CONTROL;
+ else
+ *new_ts = (*new_ts & ~SPECULATIVE) | HARD_DEP;
+ }
+ }
}
/* Return a string that contains the insn uid and optionally anything else
@@ -2128,7 +2177,8 @@ rgn_rank (rtx insn1, rtx insn2)
static int
contributes_to_priority (rtx next, rtx insn)
{
- return BLOCK_NUM (next) == BLOCK_NUM (insn);
+ /* NEXT and INSN reside in one ebb. */
+ return BLOCK_TO_BB (BLOCK_NUM (next)) == BLOCK_TO_BB (BLOCK_NUM (insn));
}
/* INSN is a JUMP_INSN, COND_SET is the set of registers that are
@@ -2164,7 +2214,16 @@ static struct sched_info region_sched_in
NULL, NULL,
0, 0, 0,
- 0
+ add_remove_insn,
+ begin_schedule_ready,
+ insn_points,
+ add_block1,
+ advance_target_bb,
+ fix_recovery_cfg,
+#ifdef ENABLE_CHECKING
+ region_head_or_leaf_p,
+#endif
+ SCHED_RGN | USE_GLAT
};
/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */
@@ -2463,7 +2522,8 @@ compute_block_backward_dependences (int
tmp_deps = bb_deps[bb];
/* Do the analysis for this block. */
- get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+ gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+ get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
sched_analyze (&tmp_deps, head, tail);
add_branch_dependences (head, tail);
@@ -2505,7 +2565,8 @@ debug_dependencies (void)
rtx next_tail;
rtx insn;
- get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+ gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+ get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
next_tail = NEXT_INSN (tail);
fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n",
BB_TO_BLOCK (bb), bb);
@@ -2598,41 +2659,61 @@ schedule_region (int rgn)
/* Set variables for the current region. */
current_nr_blocks = RGN_NR_BLOCKS (rgn);
current_blocks = RGN_BLOCKS (rgn);
+
+ /* See comments in add_block1, for what reasons we allocate +1 element. */
+ ebb_head = xrealloc (ebb_head, (current_nr_blocks + 1) * sizeof (*ebb_head));
+ for (bb = 0; bb <= current_nr_blocks; bb++)
+ ebb_head[bb] = current_blocks + bb;
/* Don't schedule region that is marked by
NOTE_DISABLE_SCHED_OF_BLOCK. */
if (sched_is_disabled_for_current_region_p ())
return;
- init_deps_global ();
+ if (!RGN_DONT_CALC_DEPS (rgn))
+ {
+ init_deps_global ();
- /* Initializations for region data dependence analysis. */
- bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
- for (bb = 0; bb < current_nr_blocks; bb++)
- init_deps (bb_deps + bb);
+ /* Initializations for region data dependence analysis. */
+ bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks);
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ init_deps (bb_deps + bb);
- /* Compute LOG_LINKS. */
- for (bb = 0; bb < current_nr_blocks; bb++)
- compute_block_backward_dependences (bb);
+ /* Compute LOG_LINKS. */
+ for (bb = 0; bb < current_nr_blocks; bb++)
+ compute_block_backward_dependences (bb);
- /* Compute INSN_DEPEND. */
- for (bb = current_nr_blocks - 1; bb >= 0; bb--)
- {
- rtx head, tail;
- get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+ /* Compute INSN_DEPEND. */
+ for (bb = current_nr_blocks - 1; bb >= 0; bb--)
+ {
+ rtx head, tail;
- compute_forward_dependences (head, tail);
+ gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+ get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
- if (targetm.sched.dependencies_evaluation_hook)
- targetm.sched.dependencies_evaluation_hook (head, tail);
+ compute_forward_dependences (head, tail);
- }
+ if (targetm.sched.dependencies_evaluation_hook)
+ targetm.sched.dependencies_evaluation_hook (head, tail);
+ }
+ free_pending_lists ();
+
+ finish_deps_global ();
+
+ free (bb_deps);
+ }
+ else
+ /* This is a recovery block. It is always a single block region. */
+ gcc_assert (current_nr_blocks == 1);
+
/* Set priorities. */
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
- get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+
+ gcc_assert (EBB_FIRST_BB (bb) == EBB_LAST_BB (bb));
+ get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
rgn_n_insns += set_priorities (head, tail);
}
@@ -2674,18 +2755,39 @@ schedule_region (int rgn)
/* Compute probabilities, dominators, split_edges. */
for (bb = 0; bb < current_nr_blocks; bb++)
compute_dom_prob_ps (bb);
+
+ if (current_nr_blocks > 1)
+ {
+ /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
+ /* We don't need them anymore. But we want to avoid dublication of
+ aux fields in the newly created edges. */
+ FOR_EACH_BB (block)
+ {
+ if (CONTAINING_RGN (block->index) != rgn)
+ continue;
+ FOR_EACH_EDGE (e, ei, block->succs)
+ e->aux = NULL;
+ }
+ }
}
/* Now we can schedule all blocks. */
for (bb = 0; bb < current_nr_blocks; bb++)
{
+ basic_block first_bb, last_bb, curr_bb;
rtx head, tail;
int b = BB_TO_BLOCK (bb);
- get_block_head_tail (b, &head, &tail);
+ first_bb = EBB_FIRST_BB (bb);
+ last_bb = EBB_LAST_BB (bb);
+
+ get_ebb_head_tail (first_bb, last_bb, &head, &tail);
if (no_real_insns_p (head, tail))
- continue;
+ {
+ gcc_assert (first_bb == last_bb);
+ continue;
+ }
current_sched_info->prev_head = PREV_INSN (head);
current_sched_info->next_tail = NEXT_INSN (tail);
@@ -2710,26 +2812,29 @@ schedule_region (int rgn)
if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
remove_note (head, note);
}
+ else
+ /* This means that first block in ebb is empty.
+ I looks to me as an impossible thing. There at least should be
+ a recovery check, that caused the splitting. */
+ gcc_unreachable ();
/* Remove remaining note insns from the block, save them in
note_list. These notes are restored at the end of
schedule_block (). */
rm_other_notes (head, tail);
+ unlink_bb_notes (first_bb, last_bb);
+
target_bb = bb;
gcc_assert (flag_schedule_interblock || current_nr_blocks == 1);
current_sched_info->queue_must_finish_empty = current_nr_blocks == 1;
- schedule_block (b, rgn_n_insns);
+ curr_bb = first_bb;
+ schedule_block (&curr_bb, &rgn_n_insns);
+ gcc_assert (EBB_FIRST_BB (bb) == first_bb);
sched_rgn_n_insns += sched_n_insns;
- /* Update target block boundaries. */
- if (head == BB_HEAD (BASIC_BLOCK (b)))
- BB_HEAD (BASIC_BLOCK (b)) = current_sched_info->head;
- if (tail == BB_END (BASIC_BLOCK (b)))
- BB_END (BASIC_BLOCK (b)) = current_sched_info->tail;
-
/* Clean up. */
if (current_nr_blocks > 1)
{
@@ -2748,29 +2853,16 @@ schedule_region (int rgn)
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
- get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail);
+
+ get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
restore_line_notes (head, tail);
}
}
/* Done with this region. */
- free_pending_lists ();
-
- finish_deps_global ();
-
- free (bb_deps);
if (current_nr_blocks > 1)
{
- /* Cleanup ->aux used for EDGE_TO_BIT mapping. */
- FOR_EACH_BB (block)
- {
- if (CONTAINING_RGN (block->index) != rgn)
- continue;
- FOR_EACH_EDGE (e, ei, block->succs)
- e->aux = NULL;
- }
-
free (prob);
sbitmap_vector_free (dom);
sbitmap_vector_free (pot_split);
@@ -2792,10 +2884,11 @@ init_regions (void)
int rgn;
nr_regions = 0;
- rgn_table = xmalloc ((n_basic_blocks) * sizeof (region));
- rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int));
- block_to_bb = xmalloc ((last_basic_block) * sizeof (int));
- containing_rgn = xmalloc ((last_basic_block) * sizeof (int));
+ rgn_table = 0;
+ rgn_bb_table = 0;
+ block_to_bb = 0;
+ containing_rgn = 0;
+ extend_regions ();
/* Compute regions for scheduling. */
if (reload_completed
@@ -2820,6 +2913,8 @@ init_regions (void)
to using the cfg code in flow.c. */
free_dominance_info (CDI_DOMINATORS);
}
+ RGN_BLOCKS (nr_regions) = RGN_BLOCKS (nr_regions - 1) +
+ RGN_NR_BLOCKS (nr_regions - 1);
if (CHECK_DEAD_NOTES)
@@ -2828,15 +2923,8 @@ init_regions (void)
deaths_in_region = xmalloc (sizeof (int) * nr_regions);
/* Remove all death notes from the subroutine. */
for (rgn = 0; rgn < nr_regions; rgn++)
- {
- int b;
-
- sbitmap_zero (blocks);
- for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
- SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
+ check_dead_notes1 (rgn, blocks);
- deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
- }
sbitmap_free (blocks);
}
else
@@ -2869,9 +2957,15 @@ schedule_insns (FILE *dump_file)
init_regions ();
+ /* EBB_HEAD is region-scope sctructure. But we realloc it for
+ each region to save time/memory/something else. */
+ ebb_head = 0;
+
/* Schedule every region in the subroutine. */
for (rgn = 0; rgn < nr_regions; rgn++)
schedule_region (rgn);
+
+ free(ebb_head);
/* Update life analysis for the subroutine. Do single block regions
first so that we can verify that live_at_start didn't change. Then
@@ -2886,8 +2980,11 @@ schedule_insns (FILE *dump_file)
that live_at_start should change at region heads. Not sure what the
best way to test for this kind of thing... */
+ if (current_sched_info->flags & DETACH_LIFE_INFO)
+ /* this flag can be set by target. */
+ attach_life_info ();
+
allocate_reg_life_data ();
- compute_bb_for_insn ();
any_large_regions = 0;
large_region_blocks = sbitmap_alloc (last_basic_block);
@@ -2902,8 +2999,13 @@ schedule_insns (FILE *dump_file)
we've possibly done interblock scheduling that affects global liveness.
For regions consisting of single blocks we need to do only local
liveness. */
- for (rgn = 0; rgn < nr_regions; rgn++)
- if (RGN_NR_BLOCKS (rgn) > 1)
+ for (rgn = 0; rgn < nr_regions; rgn++)
+ if (RGN_NR_BLOCKS (rgn) > 1
+ /* Or the only block of this region has been splitted. */
+ || RGN_HAS_REAL_EBB (rgn)
+ /* New blocks (e.g. recovery blocks) should be processed
+ as parts of large regions. */
+ || !glat_start[rgn_bb_table[RGN_BLOCKS (rgn)]])
any_large_regions = 1;
else
{
@@ -2915,16 +3017,21 @@ schedule_insns (FILE *dump_file)
regs_ever_live, which should not change after reload. */
update_life_info (blocks, UPDATE_LIFE_LOCAL,
(reload_completed ? PROP_DEATH_NOTES
- : PROP_DEATH_NOTES | PROP_REG_INFO));
+ : (PROP_DEATH_NOTES | PROP_REG_INFO)));
if (any_large_regions)
{
update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL,
- PROP_DEATH_NOTES | PROP_REG_INFO);
+ (reload_completed ? PROP_DEATH_NOTES
+ : (PROP_DEATH_NOTES | PROP_REG_INFO)));
+
+#ifdef ENABLE_CHECKING
+ check_reg_live ();
+#endif
}
if (CHECK_DEAD_NOTES)
{
- /* Verify the counts of basic block notes in single the basic block
+ /* Verify the counts of basic block notes in the single basic block
regions. */
for (rgn = 0; rgn < nr_regions; rgn++)
if (RGN_NR_BLOCKS (rgn) == 1)
@@ -2971,6 +3078,209 @@ schedule_insns (FILE *dump_file)
sbitmap_free (blocks);
sbitmap_free (large_region_blocks);
}
+
+/* INSN has been added to/removed from current region. */
+static void
+add_remove_insn (rtx insn, int remove_p)
+{
+ if (INSN_BB (insn) == target_bb)
+ {
+ if (!remove_p)
+ target_n_insns++;
+ else
+ target_n_insns--;
+ }
+}
+
+/* Adjust INSN_POINTS. */
+static int
+insn_points (rtx insn, int points)
+{
+ if (INSN_BB (insn) != target_bb)
+ return INSN_PROBABILITY (insn) * (points / 100);
+ else
+ return points;
+}
+
+/* Extend internal data structures. */
+static void
+extend_regions (void)
+{
+ rgn_table = xrealloc (rgn_table, (n_basic_blocks + 1) * sizeof (*rgn_table));
+ rgn_bb_table = xrealloc (rgn_bb_table, n_basic_blocks *
+ sizeof (*rgn_bb_table));
+ block_to_bb = xrealloc (block_to_bb, last_basic_block *
+ sizeof (*block_to_bb));
+ containing_rgn = xrealloc (containing_rgn, last_basic_block *
+ sizeof (*containing_rgn));
+}
+
+/* BB was added to ebb after AFTER. */
+static void
+add_block1 (basic_block bb, basic_block after)
+{
+ extend_regions ();
+
+ if (after == 0 || after == EXIT_BLOCK_PTR)
+ {
+ int i;
+
+ i = RGN_BLOCKS (nr_regions);
+ /* I - first free position in rgn_bb_table. */
+
+ rgn_bb_table[i] = bb->index;
+ RGN_NR_BLOCKS (nr_regions) = 1;
+ RGN_DONT_CALC_DEPS (nr_regions) = after == EXIT_BLOCK_PTR;
+ RGN_HAS_REAL_EBB (nr_regions) = 0;
+ CONTAINING_RGN (bb->index) = nr_regions;
+ BLOCK_TO_BB (bb->index) = 0;
+
+ nr_regions++;
+
+ RGN_BLOCKS (nr_regions) = i + 1;
+
+ if (CHECK_DEAD_NOTES)
+ {
+ sbitmap blocks = sbitmap_alloc (last_basic_block);
+ deaths_in_region = xrealloc (deaths_in_region, nr_regions *
+ sizeof (*deaths_in_region));
+
+ check_dead_notes1 (nr_regions - 1, blocks);
+
+ sbitmap_free (blocks);
+ }
+ }
+ else
+ {
+ int i, pos;
+
+ /* We need to fix rgn_table, block_to_bb, containing_rgn
+ and ebb_head. */
+
+ BLOCK_TO_BB (bb->index) = BLOCK_TO_BB (after->index);
+
+ /* We extend ebb_head to one more position to
+ easily find the last position of the last ebb in
+ the current region. Thus, ebb_head[BLOCK_TO_BB (after) + 1]
+ is _always_ valid for access. */
+
+ i = BLOCK_TO_BB (after->index) + 1;
+ for (pos = ebb_head[i]; rgn_bb_table[pos] != after->index; pos--);
+ pos++;
+ gcc_assert (pos > ebb_head[i - 1]);
+ /* i - ebb right after "AFTER". */
+ /* ebb_head[i] - VALID. */
+
+ /* Source position: ebb_head[i]
+ Destination posistion: ebb_head[i] + 1
+ Last position:
+ RGN_BLOCKS (nr_regions) - 1
+ Number of elements to copy: (last_position) - (source_position) + 1
+ */
+
+ memmove (rgn_bb_table + pos + 1,
+ rgn_bb_table + pos,
+ ((RGN_BLOCKS (nr_regions) - 1) - (pos) + 1)
+ * sizeof (*rgn_bb_table));
+
+ rgn_bb_table[pos] = bb->index;
+
+ for (; i <= current_nr_blocks; i++)
+ ebb_head [i]++;
+
+ i = CONTAINING_RGN (after->index);
+ CONTAINING_RGN (bb->index) = i;
+
+ RGN_HAS_REAL_EBB (i) = 1;
+
+ for (++i; i <= nr_regions; i++)
+ RGN_BLOCKS (i)++;
+
+ /* We don't need to call check_dead_notes1 () because this new block
+ is just a split of the old. We don't want to count anything twice. */
+ }
+}
+
+/* Fix internal data after interblock movement of jump instruction. */
+static void
+fix_recovery_cfg (int bbi, int check_bbi, int check_bb_nexti)
+{
+ int old_pos, new_pos, i;
+
+ BLOCK_TO_BB (check_bb_nexti) = BLOCK_TO_BB (bbi);
+
+ for (old_pos = ebb_head[BLOCK_TO_BB (check_bbi) + 1] - 1;
+ rgn_bb_table[old_pos] != check_bb_nexti;
+ old_pos--);
+ gcc_assert (old_pos > ebb_head[BLOCK_TO_BB (check_bbi)]);
+
+ for (new_pos = ebb_head[BLOCK_TO_BB (bbi) + 1] - 1;
+ rgn_bb_table[new_pos] != bbi;
+ new_pos--);
+ new_pos++;
+ gcc_assert (new_pos > ebb_head[BLOCK_TO_BB (bbi)]);
+
+ gcc_assert (new_pos < old_pos);
+
+ memmove (rgn_bb_table + new_pos + 1,
+ rgn_bb_table + new_pos,
+ (old_pos - new_pos) * sizeof (*rgn_bb_table));
+
+ rgn_bb_table[new_pos] = check_bb_nexti;
+
+ for (i = BLOCK_TO_BB (bbi) + 1; i <= BLOCK_TO_BB (check_bbi); i++)
+ ebb_head[i]++;
+}
+
+/* Return next block in ebb chain. */
+static basic_block
+advance_target_bb (basic_block bb, rtx insn)
+{
+ if (insn)
+ return 0;
+
+ gcc_assert (BLOCK_TO_BB (bb->index) == target_bb
+ && BLOCK_TO_BB (bb->next_bb->index) == target_bb);
+ return bb->next_bb;
+}
+
+static void
+check_dead_notes1 (int rgn, sbitmap blocks)
+{
+ int b;
+
+ sbitmap_zero (blocks);
+ for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
+ SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]);
+
+ deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1);
+}
+
+#ifdef ENABLE_CHECKING
+static int
+region_head_or_leaf_p (basic_block bb, int leaf_p)
+{
+ if (!leaf_p)
+ return bb->index == rgn_bb_table[RGN_BLOCKS (CONTAINING_RGN (bb->index))];
+ else
+ {
+ int i;
+ edge e;
+ edge_iterator ei;
+
+ i = CONTAINING_RGN (bb->index);
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (CONTAINING_RGN (e->dest->index) == i
+ /* except self-loop. */
+ && e->dest != bb)
+ return 0;
+
+ return 1;
+ }
+}
+#endif /* ENABLE_CHECKING */
+
#endif
static bool
Index: gcc/params.def
===================================================================
--- gcc/params.def (.../insn-tick) (revision 2239)
+++ gcc/params.def (.../recovery) (revision 2239)
@@ -497,6 +497,16 @@ DEFPARAM(PARAM_MAX_SCHED_MORE_REGIONS_IT
"The maximum number of iterations through CFG to find more regions",
2, 0, 0)
+DEFPARAM(PARAM_MAX_SCHED_INSN_CONFLICT_DELAY,
+ "max-sched-insn-conflict-delay",
+ "The maximum conflict delay for an insn to be considered for speculative motion",
+ 3, 1, 10)
+
+DEFPARAM(PARAM_SCHED_SPEC_POINTS_CUTOFF,
+ "sched-spec-points-cutoff",
+ "The minimum number of points the speculative instruction should get to be scheduled",
+ 100, 1, 1000)
+
DEFPARAM(PARAM_MAX_LAST_VALUE_RTL,
"max-last-value-rtl",
"The maximum number of RTL nodes that can be recorded as combiner's last value",