Patchwork Scheduler: Save state at the end of a block

login
register
mail settings
Submitter Bernd Schmidt
Date Aug. 13, 2012, 10:32 a.m.
Message ID <5028D7D4.3090209@codesourcery.com>
Download mbox | patch
Permalink /patch/176902/
State New
Headers show

Comments

Bernd Schmidt - Aug. 13, 2012, 10:32 a.m.
This is a small patch for sched-rgn that attempts to save DFA state at
the end of a basic block and re-use it in successor blocks. This was a
customer-requested optimization; I've not seen it make much of a
difference in any macro benchmarks.

Bootstrapped and tested on x86_64-linux and also tested on c6x-elf. OK?


Bernd
Andrey Belevantsev - Aug. 13, 2012, 12:57 p.m.
On 13.08.2012 14:32, Bernd Schmidt wrote:
> This is a small patch for sched-rgn that attempts to save DFA state at
> the end of a basic block and re-use it in successor blocks. This was a
> customer-requested optimization; I've not seen it make much of a
> difference in any macro benchmarks.

FWIW, this was definitely helpful for sel-sched on ia64, as far as I 
recall, and likewise on some of the smaller tests.

Andrey

>
> Bootstrapped and tested on x86_64-linux and also tested on c6x-elf. OK?
>
>
> Bernd
>
Vladimir Makarov - Aug. 13, 2012, 3:42 p.m.
On 08/13/2012 06:32 AM, Bernd Schmidt wrote:
> This is a small patch for sched-rgn that attempts to save DFA state at
> the end of a basic block and re-use it in successor blocks. This was a
> customer-requested optimization; I've not seen it make much of a
> difference in any macro benchmarks.
> Bootstrapped and tested on x86_64-linux and also tested on c6x-elf. OK?
>
>
>
Yes.  Thanks for the patch, Bernd.
Maxim Kuvyrkov - Aug. 14, 2012, 4:39 a.m.
On 13/08/2012, at 10:32 PM, Bernd Schmidt wrote:

> This is a small patch for sched-rgn that attempts to save DFA state at
> the end of a basic block and re-use it in successor blocks. This was a
> customer-requested optimization; I've not seen it make much of a
> difference in any macro benchmarks.
> 
> Bootstrapped and tested on x86_64-linux and also tested on c6x-elf. OK?

This patch looks OK to me.  This is a simple optimization that brings one of the benefits of sched-ebb to sched-rgn.

Vladimir, you are probably the best person to formally approve this patch.  Does it look OK to you?

Thank you,

--
Maxim Kuvyrkov
CodeSourcery / Mentor Graphics
Bernd Schmidt - Oct. 8, 2012, 11:26 a.m.
On 08/13/2012 05:42 PM, Vladimir Makarov wrote:
> On 08/13/2012 06:32 AM, Bernd Schmidt wrote:
>> This is a small patch for sched-rgn that attempts to save DFA state at
>> the end of a basic block and re-use it in successor blocks. This was a
>> customer-requested optimization; I've not seen it make much of a
>> difference in any macro benchmarks.
>> Bootstrapped and tested on x86_64-linux and also tested on c6x-elf. OK?
>>
>>
>>
> Yes.  Thanks for the patch, Bernd.

It's been a while, so I thought I'd better mention I've checked this in
now after retesting.


Bernd

Patch

	* sched-int.h (schedule_block): Adjust declaration.
	* sched-rgn.c (bb_state_array, bb_state): New static variables.
	(sched_rgn_init): Initialize them.
	(sched_rgn_free): Free them.
	(schedule_region): Save scheduling state for future blocks, and
	pass such state to schedule_block.
	* params.def (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF): New.
	* doc/invoke.texi (--param): Document it.
	* haifa-sched.c (schedule_block): New arg init_state.  Use it to
	initialize state if nonnull.  All callers changed.
	Call advance_one_cycle after scheduling.

Index: gcc/sched-ebb.c
===================================================================
--- gcc/sched-ebb.c	(revision 189284)
+++ gcc/sched-ebb.c	(working copy)
@@ -544,7 +544,7 @@  schedule_ebb (rtx head, rtx tail, bool m
 
   /* Make ready list big enough to hold all the instructions from the ebb.  */
   sched_extend_ready_list (rgn_n_insns);
-  success = schedule_block (&target_bb);
+  success = schedule_block (&target_bb, NULL);
   gcc_assert (success || modulo_scheduling);
 
   /* Free ready list.  */
Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 189284)
+++ gcc/doc/invoke.texi	(working copy)
@@ -9101,6 +9101,11 @@  The minimal probability of speculation s
 speculative insns are scheduled.
 The default value is 40.
 
+@item sched-spec-state-edge-prob-cutoff
+The minimum probability an edge must have for the scheduler to save its
+state across it.
+The default value is 10.
+
 @item sched-mem-true-dep-cost
 Minimal distance (in CPU cycles) between store and load targeting same
 memory locations.  The default value is 1.
Index: gcc/haifa-sched.c
===================================================================
--- gcc/haifa-sched.c	(revision 189284)
+++ gcc/haifa-sched.c	(working copy)
@@ -5542,7 +5542,7 @@  verify_shadows (void)
    region.  */
 
 bool
-schedule_block (basic_block *target_bb)
+schedule_block (basic_block *target_bb, state_t init_state)
 {
   int i;
   bool success = modulo_ii == 0;
@@ -5573,7 +5573,10 @@  schedule_block (basic_block *target_bb)
   if (sched_verbose)
     dump_new_block_header (0, *target_bb, head, tail);
 
-  state_reset (curr_state);
+  if (init_state == NULL)
+    state_reset (curr_state);
+  else
+    memcpy (curr_state, init_state, dfa_state_size);
 
   /* Clear the ready list.  */
   ready.first = ready.veclen - 1;
@@ -6029,7 +6032,9 @@  schedule_block (basic_block *target_bb)
     }
   if (ls.modulo_epilogue)
     success = true;
+
  end_schedule:
+  advance_one_cycle ();
   if (modulo_ii > 0)
     {
       /* Once again, debug insn suckiness: they can be on the ready list
Index: gcc/sched-int.h
===================================================================
--- gcc/sched-int.h	(revision 189284)
+++ gcc/sched-int.h	(working copy)
@@ -1291,7 +1291,7 @@  extern int dep_cost (dep_t);
 extern int set_priorities (rtx, rtx);
 
 extern void sched_setup_bb_reg_pressure_info (basic_block, rtx);
-extern bool schedule_block (basic_block *);
+extern bool schedule_block (basic_block *, state_t);
 
 extern int cycle_issued_insns;
 extern int issue_rate;
Index: gcc/sched-rgn.c
===================================================================
--- gcc/sched-rgn.c	(revision 189284)
+++ gcc/sched-rgn.c	(working copy)
@@ -125,6 +125,9 @@  int current_blocks;
 static basic_block *bblst_table;
 static int bblst_size, bblst_last;
 
+static char *bb_state_array;
+static state_t *bb_state;
+
 /* Target info declarations.
 
    The block currently being scheduled is referred to as the "target" block,
@@ -2974,9 +2977,21 @@  schedule_region (int rgn)
       curr_bb = first_bb;
       if (dbg_cnt (sched_block))
         {
-          schedule_block (&curr_bb);
+	  edge f;
+
+          schedule_block (&curr_bb, bb_state[first_bb->index]);
           gcc_assert (EBB_FIRST_BB (bb) == first_bb);
           sched_rgn_n_insns += sched_n_insns;
+	  f = find_fallthru_edge (last_bb->succs);
+	  if (f && f->probability * 100 / REG_BR_PROB_BASE >=
+	      PARAM_VALUE (PARAM_SCHED_STATE_EDGE_PROB_CUTOFF))
+	    {
+	      memcpy (bb_state[f->dest->index], curr_state,
+		      dfa_state_size);
+	      if (sched_verbose >= 5)
+		fprintf (sched_dump, "saving state for edge %d->%d\n",
+			 f->src->index, f->dest->index);
+	    }
         }
       else
         {
@@ -3009,6 +3024,8 @@  schedule_region (int rgn)
 void
 sched_rgn_init (bool single_blocks_p)
 {
+  int i;
+
   min_spec_prob = ((PARAM_VALUE (PARAM_MIN_SPEC_PROB) * REG_BR_PROB_BASE)
 		    / 100);
 
@@ -3020,6 +3037,23 @@  sched_rgn_init (bool single_blocks_p)
   CONTAINING_RGN (ENTRY_BLOCK) = -1;
   CONTAINING_RGN (EXIT_BLOCK) = -1;
 
+  if (!sel_sched_p ())
+    {
+      bb_state_array = (char *) xmalloc (last_basic_block * dfa_state_size);
+      bb_state = XNEWVEC (state_t, last_basic_block);
+      for (i = 0; i < last_basic_block; i++)
+	{
+	  bb_state[i] = (state_t) (bb_state_array + i * dfa_state_size);
+      
+	  state_reset (bb_state[i]);
+	}
+    }
+  else
+    {
+      bb_state_array = NULL;
+      bb_state = NULL;
+    }
+
   /* Compute regions for scheduling.  */
   if (single_blocks_p
       || n_basic_blocks == NUM_FIXED_BLOCKS + 1
@@ -3056,6 +3090,9 @@  sched_rgn_init (bool single_blocks_p)
 void
 sched_rgn_finish (void)
 {
+  free (bb_state_array);
+  free (bb_state);
+
   /* Reposition the prologue and epilogue notes in case we moved the
      prologue/epilogue insns.  */
   if (reload_completed)
Index: gcc/params.def
===================================================================
--- gcc/params.def	(revision 189284)
+++ gcc/params.def	(working copy)
@@ -611,6 +611,11 @@  DEFPARAM(PARAM_SCHED_SPEC_PROB_CUTOFF,
          "The minimal probability of speculation success (in percents), so that speculative insn will be scheduled.",
          40, 0, 100)
 
+DEFPARAM(PARAM_SCHED_STATE_EDGE_PROB_CUTOFF,
+         "sched-state-edge-prob-cutoff",
+         "The minimum probability an edge must have for the scheduler to save its state across it.",
+         10, 0, 100)
+
 DEFPARAM(PARAM_SELSCHED_MAX_LOOKAHEAD,
          "selsched-max-lookahead",
          "The maximum size of the lookahead window of selective scheduling",