[cfg-branch] update the CFG in schedule_ebbs
Jan Hubicka
jh@suse.cz
Fri Apr 19 15:44:00 GMT 2002
Hi,
the attached patch teaches Bernd's ebb scheduler to update CFG, so it can be run
as default sched or sched2 pass. Together with tracer it should do proper trace
scheduling, but additional patch to use ebb scheduler in sched1 pass and to
avoid crossjumping before sched2 is needed I will try to install tomorrow.
It works by re-recognizing the basic block boundaries in the scheduled superblock,
that got somewhat tricky, as I need to care cases where basic block disappears
or get created. I will try to think if I can come with cleaner way.
ALso currently the liveness is recomputed that is just too expensive, I will
need to add to update liveness properly later.
Honza
Sat Apr 20 00:36:00 CEST 2002 Jan Hubicka <jh@suse.cz>
* basic-block.h (inside_basic_block_p, control_flow_insn_p): Declare.
* cfgbuild.c (inside_basic_block_p, control_flow_insn_p): Make global.
* haifa-sched.c (unlink_other_notes): Delete NOTE_INSN_BASIC_BLOCK.
* sched-ebb.c (scheudle_ebb): Fix CFG, return last update BB.
(fix_basic_block_boudaries, add_missing_bbs): New.
(schedule_ebbs): Verify flow info, use CFG.
* toplev.c (flag_superblock_scheduling): New.
(lang_independent_options): Add schedule-superblocks
(rest_of_compilation): Use schedule_ebbs when asked to do so.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.127.2.22
diff -c -3 -p -r1.127.2.22 basic-block.h
*** basic-block.h 16 Apr 2002 18:14:15 -0000 1.127.2.22
--- basic-block.h 19 Apr 2002 22:20:21 -0000
*************** basic_block loop_split_edge_with PARAMS
*** 778,783 ****
--- 778,785 ----
void force_single_succ_latches PARAMS ((struct loops *));
bool just_once_each_iteration_p PARAMS ((struct loops *,struct loop *, basic_block));
int num_loop_insns PARAMS ((struct loop *));
+ bool inside_basic_block_p PARAMS ((rtx));
+ bool control_flow_insn_p PARAMS ((rtx));
#define CP_SIMPLE_PREHEADERS 1
#define CP_INSIDE_CFGLAYOUT 2
Index: cfgbuild.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/cfgbuild.c,v
retrieving revision 1.8.4.6
diff -c -3 -p -r1.8.4.6 cfgbuild.c
*** cfgbuild.c 30 Mar 2002 22:51:30 -0000 1.8.4.6
--- cfgbuild.c 19 Apr 2002 22:20:21 -0000
*************** static void make_label_edge PARAMS ((sb
*** 56,68 ****
static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx));
static void find_bb_boundaries PARAMS ((basic_block));
static void compute_outgoing_frequencies PARAMS ((basic_block));
- static bool inside_basic_block_p PARAMS ((rtx));
- static bool control_flow_insn_p PARAMS ((rtx));
/* Return true if insn is something that should be contained inside basic
block. */
! static bool
inside_basic_block_p (insn)
rtx insn;
{
--- 56,66 ----
static void make_eh_edge PARAMS ((sbitmap *, basic_block, rtx));
static void find_bb_boundaries PARAMS ((basic_block));
static void compute_outgoing_frequencies PARAMS ((basic_block));
/* Return true if insn is something that should be contained inside basic
block. */
! bool
inside_basic_block_p (insn)
rtx insn;
{
*************** inside_basic_block_p (insn)
*** 95,101 ****
/* Return true if INSN may cause control flow transfer, so it should be last in
the basic block. */
! static bool
control_flow_insn_p (insn)
rtx insn;
{
--- 93,99 ----
/* Return true if INSN may cause control flow transfer, so it should be last in
the basic block. */
! bool
control_flow_insn_p (insn)
rtx insn;
{
Index: haifa-sched.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/haifa-sched.c,v
retrieving revision 1.190.2.5
diff -c -3 -p -r1.190.2.5 haifa-sched.c
*** haifa-sched.c 5 Mar 2002 18:58:23 -0000 1.190.2.5
--- haifa-sched.c 19 Apr 2002 22:20:22 -0000
*************** unlink_other_notes (insn, tail)
*** 1070,1075 ****
--- 1070,1076 ----
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_BEG
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_RANGE_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)
{
Index: sched-ebb.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/sched-ebb.c,v
retrieving revision 1.6.4.2
diff -c -3 -p -r1.6.4.2 sched-ebb.c
*** sched-ebb.c 7 Jan 2002 14:50:58 -0000 1.6.4.2
--- sched-ebb.c 19 Apr 2002 22:20:23 -0000
*************** static const char *print_insn PARAMS ((r
*** 53,59 ****
static int rank PARAMS ((rtx, rtx));
static int contributes_to_priority PARAMS ((rtx, rtx));
static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
! static void schedule_ebb PARAMS ((rtx, rtx));
/* Return nonzero if there are more insns that should be scheduled. */
--- 53,61 ----
static int rank PARAMS ((rtx, rtx));
static int contributes_to_priority PARAMS ((rtx, rtx));
static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
! static basic_block schedule_ebb PARAMS ((rtx, rtx));
! static basic_block fix_basic_block_boundaries PARAMS ((int, int, rtx, rtx));
! static void add_missing_bbs PARAMS ((rtx, int, int));
/* Return nonzero if there are more insns that should be scheduled. */
*************** static struct sched_info ebb_sched_info
*** 197,214 ****
0, 1
};
/* Schedule a single extended basic block, defined by the boundaries HEAD
and TAIL. */
! static void
schedule_ebb (head, tail)
rtx head, tail;
{
int n_insns;
struct deps tmp_deps;
if (no_real_insns_p (head, tail))
! return;
init_deps_global ();
--- 199,335 ----
0, 1
};
+ /* It is possible that ebb scheduling elliminated some blocks.
+ Place block from FIRST to LAST before BEFORE. */
+
+ static void
+ add_missing_bbs (before, first, last)
+ rtx before;
+ int first, last;
+ {
+ int i;
+
+ for (i = last; i >= first; i--)
+ {
+ before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before);
+ NOTE_BASIC_BLOCK (before) = BASIC_BLOCK (i);
+ BASIC_BLOCK (i)->head = before;
+ BASIC_BLOCK (i)->end = before;
+ update_bb_for_insn (BASIC_BLOCK (i));
+ }
+ }
+
+ /* 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 (bb, last, head, tail)
+ int bb, last;
+ rtx head, tail;
+ {
+ rtx insn = head;
+ rtx last_inside = BASIC_BLOCK (bb)->head;
+ rtx aftertail = NEXT_INSN (tail);
+
+ head = BASIC_BLOCK (bb)->head;
+
+ for (; insn != aftertail; insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == CODE_LABEL)
+ abort ();
+ if (inside_basic_block_p (insn))
+ {
+ if (!last_inside)
+ {
+ rtx note;
+
+ /* Re-emit the basic block note for newly found BB header. */
+ if (GET_CODE (insn) == CODE_LABEL)
+ {
+ 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;
+ }
+ 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 = BASIC_BLOCK (last);
+ if (bb == last + 1)
+ {
+ edge f;
+ rtx h;
+
+ /* 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
+
+ Safter sollution can be to bring the code into sequence,
+ do the split and re-emit it back in case this will ever
+ trigger problem. */
+ f = BASIC_BLOCK (bb - 1)->succ;
+ while (!(f->flags & EDGE_FALLTHRU))
+ f = f->succ_next;
+ curr_bb = split_edge (f);
+ h = curr_bb->head;
+ curr_bb->head = head;
+ curr_bb->end = insn;
+ /* Edge splitting created missplaced BASIC_BLOCK note, kill
+ it. */
+ delete_insn (h);
+ }
+ else
+ {
+ if (curr_bb->index < bb)
+ abort ();
+ curr_bb->head = head;
+ curr_bb->end = insn;
+ }
+ note = GET_CODE (head) == CODE_LABEL ? NEXT_INSN (head) : head;
+ NOTE_BASIC_BLOCK (note) = curr_bb;
+ update_bb_for_insn (curr_bb);
+ add_missing_bbs (curr_bb->head, bb, curr_bb->index - 1);
+ bb = curr_bb->index + 1;
+ last_inside = NULL;
+ }
+ }
+ if (last != n_basic_blocks - 1)
+ add_missing_bbs (BASIC_BLOCK (last + 1)->head, bb, last);
+ return BASIC_BLOCK (bb - 1);
+ }
+
/* Schedule a single extended basic block, defined by the boundaries HEAD
and TAIL. */
! static basic_block
schedule_ebb (head, tail)
rtx head, tail;
{
int n_insns;
+ basic_block b;
struct deps tmp_deps;
+ int first_bb = BLOCK_FOR_INSN (head) -> index;
+ int last_bb = BLOCK_FOR_INSN (tail) -> index;
+ verify_flow_info ();
if (no_real_insns_p (head, tail))
! return BLOCK_FOR_INSN (tail);
init_deps_global ();
*************** schedule_ebb (head, tail)
*** 268,275 ****
--- 389,398 ----
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;
}
/* The one entry point in this file. DUMP_FILE is the dump file for
*************** schedule_ebbs (dump_file)
*** 314,330 ****
break;
if (! e)
break;
! if (GET_CODE (tail) == JUMP_INSN)
! {
! rtx x = find_reg_note (tail, REG_BR_PROB, 0);
! if (x)
! {
! int pred_val = INTVAL (XEXP (x, 0));
! if (pred_val > REG_BR_PROB_BASE / 2)
! break;
! }
! }
!
i++;
}
--- 437,444 ----
break;
if (! e)
break;
! if (e->probability < REG_BR_PROB_BASE * 60 / 100)
! break;
i++;
}
*************** schedule_ebbs (dump_file)
*** 342,348 ****
break;
}
! schedule_ebb (head, tail);
}
/* It doesn't make much sense to try and update life information here - we
--- 456,462 ----
break;
}
! i = schedule_ebb (head, tail)->index;
}
/* It doesn't make much sense to try and update life information here - we
*************** schedule_ebbs (dump_file)
*** 355,360 ****
--- 469,476 ----
if (write_symbols != NO_DEBUG)
rm_redundant_line_notes ();
+
+ verify_flow_info ();
scope_to_insns_finalize ();
Index: toplev.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/toplev.c,v
retrieving revision 1.537.2.67
diff -c -3 -p -r1.537.2.67 toplev.c
*** toplev.c 16 Apr 2002 18:15:33 -0000 1.537.2.67
--- toplev.c 19 Apr 2002 22:20:25 -0000
*************** int flag_pedantic_errors = 0;
*** 740,745 ****
--- 740,746 ----
global_alloc. */
int flag_schedule_insns = 0;
+ static int flag_superblock_scheduling = 1;
int flag_schedule_insns_after_reload = 0;
/* The following flags have effect only for scheduling before register
*************** static const lang_independent_options f_
*** 1081,1086 ****
--- 1082,1089 ----
N_("Delete useless null pointer checks") },
{"schedule-insns", &flag_schedule_insns, 1,
N_("Reschedule instructions before register allocation") },
+ {"schedule-superblocks", &flag_superblock_scheduling, 1,
+ N_("When scheduling, do superblock sheduling") },
{"schedule-insns2", &flag_schedule_insns_after_reload, 1,
N_("Reschedule instructions after register allocation") },
{"sched-interblock",&flag_schedule_interblock, 1,
*************** rest_of_compilation (decl)
*** 3509,3515 ****
split_all_insns (1);
! schedule_insns (rtl_dump_file);
close_dump_file (DFI_sched2, print_rtl_with_bb, get_insns ());
timevar_pop (TV_SCHED2);
--- 3512,3528 ----
split_all_insns (1);
! if (flag_superblock_scheduling)
! {
! schedule_ebbs (rtl_dump_file);
! /* No liveness updating code yet, but it should be easy to do */
! count_or_remove_death_notes (NULL, 1);
! life_analysis (get_insns (), rtl_dump_file, PROP_FINAL);
! }
! else
! schedule_insns (rtl_dump_file);
! cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE
! | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
close_dump_file (DFI_sched2, print_rtl_with_bb, get_insns ());
timevar_pop (TV_SCHED2);
More information about the Gcc-patches
mailing list