diff mbox

Fix sched-deps DEP_POSTPONED, ds_t documentation

Message ID CABu31nN5ErK7RhhJ6ig1BuH9ymV33CPBNAcHwCh1Yi4qH=Etrg@mail.gmail.com
State New
Headers show

Commit Message

Steven Bosscher May 12, 2013, 3:45 p.m. UTC 
Hello,

While working on a sched-deps based delay slot scheduler, I've come to
the conclusion that the dependencies themselves must indicate whether
the dependent ref is delayed. So I started hacking sched-deps and ran
into trouble... It turns out there is a problem introduced along with
DEP_POSTPONED last year, but the real problem is the complicated ds_t
representation and the unclear documentation. The first *6* bits on a
ds_t were reserved for the dependence type, and two more bits were
reserved for HARD_DEP and DEP_CANCELLED:

-/* First '6' stands for 4 dep type bits and the HARD_DEP and DEP_CANCELLED
-   bits.
-   Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
-   dep weakness.  */
-#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 6) / 4)

But DEP_POSTPONED adds another bit:

/* Instruction has non-speculative dependence.  This bit represents the
   property of an instruction - not the one of a dependence.
  Therefore, it can appear only in the TODO_SPEC field of an instruction.  */
#define HARD_DEP (DEP_CONTROL << 1)

/* Set in the TODO_SPEC field of an instruction for which new_ready
   has decided not to schedule it speculatively.  */
 #define DEP_POSTPONED (HARD_DEP << 1)

/* Set if a dependency is cancelled via speculation.  */
#define DEP_CANCELLED (DEP_POSTPONED << 1)

I wanted to add another flag, DEP_DELAYED, and optimistically just
added another bit, the compiler started warning, etc.


So far we seem to've gotten away with this because the sign bit on a
ds_t was unused:

/* We exclude sign bit.  */
#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)


The attached patch extends the ds_t documentation to clarify in a
comment how all the bits are used. I've made ds_t and dw_t unsigned
int, because ds_t is just a collection of bits, and dw_t is unsigned.
The target hooks I had to update are all only used by ia64.

I opportunistically reserved the one left-over bit for my own purposes ;-)

Bootstrapped&tested on ia64-unknown-linux-gnu and on
powerpc64-unknown-linux-gnu unix-{,-m32).
OK for trunk?

Ciao!
Steven
* sched-int.h (ds_t, dw_t): Make unsigned int.
	Fix documentation that describes how all the ds_t bits are used.
	Reserve the last bit for delayed-branch scheduling.
	(BITS_PER_DEP_STATUS): Move to ds_t typedef.
	(BITS_PER_DEP_WEAK): Fix definition and documentation.
	(gen_dep_weak_1): Remove prototype.
	* sched-deps.c (get_dep_weak_1): Make static.
	* target.def (speculate_insn, needs_block_p, gen_spec_check,
	get_insn_spec_ds, get_insn_checked_ds): Adjust hook prototypes.
	* doc/tm.texi: Regenerate.
	* config/ia64/ia64.c (ia64_needs_block_p):
	(ia64_gen_spec_check):

Comments

Steven Bosscher May 17, 2013, 7:01 p.m. UTC | #1 
Ping

On Sun, May 12, 2013 at 5:45 PM, Steven Bosscher wrote:
> Hello,
>
> While working on a sched-deps based delay slot scheduler, I've come to
> the conclusion that the dependencies themselves must indicate whether
> the dependent ref is delayed. So I started hacking sched-deps and ran
> into trouble... It turns out there is a problem introduced along with
> DEP_POSTPONED last year, but the real problem is the complicated ds_t
> representation and the unclear documentation. The first *6* bits on a
> ds_t were reserved for the dependence type, and two more bits were
> reserved for HARD_DEP and DEP_CANCELLED:
>
> -/* First '6' stands for 4 dep type bits and the HARD_DEP and DEP_CANCELLED
> -   bits.
> -   Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
> -   dep weakness.  */
> -#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 6) / 4)
>
> But DEP_POSTPONED adds another bit:
>
> /* Instruction has non-speculative dependence.  This bit represents the
>    property of an instruction - not the one of a dependence.
>   Therefore, it can appear only in the TODO_SPEC field of an instruction.  */
> #define HARD_DEP (DEP_CONTROL << 1)
>
> /* Set in the TODO_SPEC field of an instruction for which new_ready
>    has decided not to schedule it speculatively.  */
>  #define DEP_POSTPONED (HARD_DEP << 1)
>
> /* Set if a dependency is cancelled via speculation.  */
> #define DEP_CANCELLED (DEP_POSTPONED << 1)
>
> I wanted to add another flag, DEP_DELAYED, and optimistically just
> added another bit, the compiler started warning, etc.
>
>
> So far we seem to've gotten away with this because the sign bit on a
> ds_t was unused:
>
> /* We exclude sign bit.  */
> #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
>
>
> The attached patch extends the ds_t documentation to clarify in a
> comment how all the bits are used. I've made ds_t and dw_t unsigned
> int, because ds_t is just a collection of bits, and dw_t is unsigned.
> The target hooks I had to update are all only used by ia64.
>
> I opportunistically reserved the one left-over bit for my own purposes ;-)
>
> Bootstrapped&tested on ia64-unknown-linux-gnu and on
> powerpc64-unknown-linux-gnu unix-{,-m32).
> OK for trunk?
>
> Ciao!
> Steven
Steven Bosscher May 23, 2013, 8:51 p.m. UTC | #2 
Ping**2

On Fri, May 17, 2013 at 9:01 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> Ping
>
> On Sun, May 12, 2013 at 5:45 PM, Steven Bosscher wrote:
>> Hello,
>>
>> While working on a sched-deps based delay slot scheduler, I've come to
>> the conclusion that the dependencies themselves must indicate whether
>> the dependent ref is delayed. So I started hacking sched-deps and ran
>> into trouble... It turns out there is a problem introduced along with
>> DEP_POSTPONED last year, but the real problem is the complicated ds_t
>> representation and the unclear documentation. The first *6* bits on a
>> ds_t were reserved for the dependence type, and two more bits were
>> reserved for HARD_DEP and DEP_CANCELLED:
>>
>> -/* First '6' stands for 4 dep type bits and the HARD_DEP and DEP_CANCELLED
>> -   bits.
>> -   Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
>> -   dep weakness.  */
>> -#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 6) / 4)
>>
>> But DEP_POSTPONED adds another bit:
>>
>> /* Instruction has non-speculative dependence.  This bit represents the
>>    property of an instruction - not the one of a dependence.
>>   Therefore, it can appear only in the TODO_SPEC field of an instruction.  */
>> #define HARD_DEP (DEP_CONTROL << 1)
>>
>> /* Set in the TODO_SPEC field of an instruction for which new_ready
>>    has decided not to schedule it speculatively.  */
>>  #define DEP_POSTPONED (HARD_DEP << 1)
>>
>> /* Set if a dependency is cancelled via speculation.  */
>> #define DEP_CANCELLED (DEP_POSTPONED << 1)
>>
>> I wanted to add another flag, DEP_DELAYED, and optimistically just
>> added another bit, the compiler started warning, etc.
>>
>>
>> So far we seem to've gotten away with this because the sign bit on a
>> ds_t was unused:
>>
>> /* We exclude sign bit.  */
>> #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
>>
>>
>> The attached patch extends the ds_t documentation to clarify in a
>> comment how all the bits are used. I've made ds_t and dw_t unsigned
>> int, because ds_t is just a collection of bits, and dw_t is unsigned.
>> The target hooks I had to update are all only used by ia64.
>>
>> I opportunistically reserved the one left-over bit for my own purposes ;-)
>>
>> Bootstrapped&tested on ia64-unknown-linux-gnu and on
>> powerpc64-unknown-linux-gnu unix-{,-m32).
>> OK for trunk?
>>
>> Ciao!
>> Steven
Vladimir Makarov May 24, 2013, 3:51 p.m. UTC | #3 
On 13-05-23 4:51 PM, Steven Bosscher wrote:
> Ping**2
>
Steven, sorry for the delay.  The patch is ok.  Thanks for better 
documentation too.  We need it as the scheduler is becoming more and 
more complicated.
diff mbox

Patch

Index: sched-int.h
===================================================================
--- sched-int.h	(revision 198799)
+++ sched-int.h	(working copy)
@@ -193,10 +193,11 @@  extern void sched_create_recovery_edges (basic_blo
 extern state_t curr_state;
 
 /* Type to represent status of a dependence.  */
-typedef int ds_t;
+typedef unsigned int ds_t;
+#define BITS_PER_DEP_STATUS HOST_BITS_PER_INT
 
 /* Type to represent weakness of speculative dependence.  */
-typedef int dw_t;
+typedef unsigned int dw_t;
 
 extern enum reg_note ds_to_dk (ds_t);
 extern ds_t dk_to_ds (enum reg_note);
@@ -743,6 +744,7 @@  struct _haifa_deps_insn_data
   unsigned int cant_move : 1;
 };
 
+
 /* Bits used for storing values of the fields in the following
    structure.  */
 #define INCREASE_BITS 8
@@ -952,34 +954,54 @@  extern vec<haifa_deps_insn_data_def> h_d_i_d;
 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
 
-/* Dep status (aka ds_t) of the link encapsulates information, that is needed
-   for speculative scheduling.  Namely, it is 4 integers in the range
-   [0, MAX_DEP_WEAK] and 3 bits.
-   The integers correspond to the probability of the dependence to *not*
-   exist, it is the probability, that overcoming of this dependence will
-   not be followed by execution of the recovery code.  Nevertheless,
-   whatever high the probability of success is, recovery code should still
-   be generated to preserve semantics of the program.  To find a way to
-   get/set these integers, please refer to the {get, set}_dep_weak ()
-   functions in sched-deps.c .
-   The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
-   output- and anti- dependence.  It is not enough for speculative scheduling
-   to know just the major type of all the dependence between two instructions,
-   as only true dependence can be overcome.
-   There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
-   for using to describe instruction's status.  It is set whenever instruction
-   has at least one dependence, that cannot be overcame.
+
+/* Dep status (aka ds_t) of the link encapsulates all information for a given
+   dependency, including everything that is needed for speculative scheduling.
+
+   The lay-out of a ds_t is as follows:
+
+   1. Integers corresponding to the probability of the dependence to *not*
+      exist.  This is the probability that overcoming this dependence will
+      not be followed by execution of the recovery code.  Note that however
+      high this probability is, the recovery code should still always be
+      generated to preserve semantics of the program.
+
+      The probability values can be set or retrieved using the functions
+      the set_dep_weak() and get_dep_weak() in sched-deps.c.  The values
+      are always in the range [0, MAX_DEP_WEAK].
+
+	BEGIN_DATA	: BITS_PER_DEP_WEAK
+	BE_IN_DATA	: BITS_PER_DEP_WEAK
+	BEGIN_CONTROL	: BITS_PER_DEP_WEAK
+	BE_IN_CONTROL	: BITS_PER_DEP_WEAK
+
+      The basic type of DS_T is a host int.  For a 32-bits int, the values
+      will each take 6 bits.
+
+   2. The type of dependence.  This supercedes the old-style REG_NOTE_KIND
+      values.  TODO: Use this field instead of DEP_TYPE, or make DEP_TYPE
+      extract the dependence type from here.
+
+	dep_type	:  4 => DEP_{TRUE|OUTPUT|ANTI|CONTROL}
+
+   3. Various flags:
+
+	HARD_DEP	:  1 =>	Set if an instruction has a non-speculative
+				dependence.  This is an instruction property
+				so this bit can only appear in the TODO_SPEC
+				field of an instruction.
+	DEP_POSTPONED	:  1 =>	Like HARD_DEP, but the hard dependence may
+				still be broken by adjusting the instruction.
+	DEP_CANCELLED	:  1 =>	Set if a dependency has been broken using
+				some form of speculation.
+	RESERVED	:  1 => Reserved for use in the delay slot scheduler.
+
    See also: check_dep_status () in sched-deps.c .  */
 
-/* We exclude sign bit.  */
-#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
+/* The number of bits per weakness probability.  There are 4 weakness types
+   and we need 8 bits for other data in a DS_T.  */
+#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 8) / 4)
 
-/* First '6' stands for 4 dep type bits and the HARD_DEP and DEP_CANCELLED
-   bits.
-   Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
-   dep weakness.  */
-#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 6) / 4)
-
 /* Mask of speculative weakness in dep_status.  */
 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
 
@@ -996,7 +1018,9 @@  extern vec<haifa_deps_insn_data_def> h_d_i_d;
 #define MIN_DEP_WEAK 1
 
 /* This constant represents 100% probability.
-   E.g. it is used to represent weakness of dependence, that doesn't exist.  */
+   E.g. it is used to represent weakness of dependence, that doesn't exist.
+   This value never appears in a ds_t, it is only used for computing the
+   weakness of a dependence.  */
 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
 
 /* Default weakness of speculative dependence.  Used when we can't say
@@ -1011,8 +1035,10 @@  enum SPEC_TYPES_OFFSETS {
   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
 };
 
-/* The following defines provide numerous constants used to distinguish between
-   different types of speculative dependencies.  */
+/* The following defines provide numerous constants used to distinguish
+   between different types of speculative dependencies.  They are also
+   used as masks to clear/preserve the bits corresponding to the type
+   of dependency weakness.  */
 
 /* Dependence can be overcome with generation of new data speculative
    instruction.  */
@@ -1058,15 +1084,24 @@  enum SPEC_TYPES_OFFSETS {
 
 /* Instruction has non-speculative dependence.  This bit represents the
    property of an instruction - not the one of a dependence.
-   Therefore, it can appear only in TODO_SPEC field of an instruction.  */
+   Therefore, it can appear only in the TODO_SPEC field of an instruction.  */
 #define HARD_DEP (DEP_CONTROL << 1)
 
-/* Set in the TODO_SPEC field of an instruction for which new_ready
-   has decided not to schedule it speculatively.  */
+/* Like HARD_DEP, but dependencies can perhaps be broken by modifying
+   the instructions.  This is used for example to change:
+
+   rn++		=>	rm=[rn + 4]
+   rm=[rn]		rn++
+
+   For instructions that have this bit set, one of the dependencies of
+   the instructions will have a non-NULL REPLACE field in its DEP_T.
+   Just like HARD_DEP, this bit is only ever set in TODO_SPEC.  */
 #define DEP_POSTPONED (HARD_DEP << 1)
 
+/* Set if a dependency is cancelled via speculation.  */
 #define DEP_CANCELLED (DEP_POSTPONED << 1)
 
+
 /* This represents the results of calling sched-deps.c functions,
    which modify dependencies.  */
 enum DEPS_ADJUST_RESULT {
@@ -1268,7 +1303,6 @@  extern void deps_analyze_insn (struct deps_desc *,
 extern void remove_from_deps (struct deps_desc *, rtx);
 extern void init_insn_reg_pressure_info (rtx);
 
-extern dw_t get_dep_weak_1 (ds_t, ds_t);
 extern dw_t get_dep_weak (ds_t, ds_t);
 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
 extern dw_t estimate_dep_weak (rtx, rtx);
Index: sched-deps.c
===================================================================
--- sched-deps.c	(revision 198799)
+++ sched-deps.c	(working copy)
@@ -4170,8 +4170,9 @@  add_dependence_1 (rtx insn, rtx elem, enum reg_not
     cur_insn = NULL;
 }
 
-/* Return weakness of speculative type TYPE in the dep_status DS.  */
-dw_t
+/* Return weakness of speculative type TYPE in the dep_status DS,
+   without checking to prevent ICEs on malformed input.  */
+static dw_t
 get_dep_weak_1 (ds_t ds, ds_t type)
 {
   ds = ds & type;
@@ -4188,6 +4189,7 @@  get_dep_weak_1 (ds_t ds, ds_t type)
   return (dw_t) ds;
 }
 
+/* Return weakness of speculative type TYPE in the dep_status DS.  */
 dw_t
 get_dep_weak (ds_t ds, ds_t type)
 {
Index: target.def
===================================================================
--- target.def	(revision 198799)
+++ target.def	(working copy)
@@ -780,7 +780,7 @@  DEFHOOK_UNDOC
  "Given the current cost, @var{cost}, of an insn, @var{insn}, calculate and\
  return a new cost based on its relationship to @var{dep_insn} through the\
  dependence of weakness @var{dw}.  The default is to make no adjustment.",
- int, (rtx insn, int dep_type1, rtx dep_insn, int cost, int dw), NULL)
+ int, (rtx insn, int dep_type1, rtx dep_insn, int cost, unsigned int dw), NULL)
 
 /* The following member value is a pointer to a function called
    by the insn scheduler. This hook is called to notify the backend
@@ -835,7 +835,7 @@  DEFHOOK
 DEFHOOK
 (speculate_insn,
  "",
- int, (rtx insn, int request, rtx *new_pat), NULL)
+ int, (rtx insn, unsigned int dep_status, rtx *new_pat), NULL)
 
 /* The following member value is a pointer to a function called
    by the insn scheduler.  It should return true if the check instruction
@@ -843,20 +843,19 @@  DEFHOOK
 DEFHOOK
 (needs_block_p,
  "",
- bool, (int dep_status), NULL)
+ bool, (unsigned int dep_status), NULL)
 
 /* The following member value is a pointer to a function called
    by the insn scheduler.  It should return a pattern for the check
    instruction.
    The first parameter is a speculative instruction, the second parameter
    is the label of the corresponding recovery block (or null, if it is a
-   simple check).  If the mutation of the check is requested (e.g. from
-   ld.c to chk.a), the third parameter is true - in this case the first
-   parameter is the previous check.  */
+   simple check).  The third parameter is the kind of speculation that
+   is being performed.  */
 DEFHOOK
 (gen_spec_check,
  "",
- rtx, (rtx insn, rtx label, int mutate_p), NULL)
+ rtx, (rtx insn, rtx label, unsigned int ds), NULL)
 
 /* The following member value is a pointer to a function controlling
    what insns from the ready insn queue will be considered for the
@@ -880,12 +879,12 @@  DEFHOOK
 DEFHOOK_UNDOC
 (get_insn_spec_ds,
  "Return speculation types of instruction @var{insn}.",
- int, (rtx insn), NULL)
+ unsigned int, (rtx insn), NULL)
 
 DEFHOOK_UNDOC
 (get_insn_checked_ds,
  "Return speculation types that are checked for instruction @var{insn}",
- int, (rtx insn), NULL)
+ unsigned int, (rtx insn), NULL)
 
 DEFHOOK_UNDOC
 (skip_rtx_p,
Index: doc/tm.texi
===================================================================
--- doc/tm.texi	(revision 198799)
+++ doc/tm.texi	(working copy)
@@ -6765,7 +6765,7 @@  Deallocate internal data in target scheduling cont
 Deallocate a store for target scheduling context pointed to by @var{tc}.
 @end deftypefn
 
-@deftypefn {Target Hook} int TARGET_SCHED_SPECULATE_INSN (rtx @var{insn}, int @var{request}, rtx *@var{new_pat})
+@deftypefn {Target Hook} int TARGET_SCHED_SPECULATE_INSN (rtx @var{insn}, unsigned int @var{dep_status}, rtx *@var{new_pat})
 This hook is called by the insn scheduler when @var{insn} has only
 speculative dependencies and therefore can be scheduled speculatively.
 The hook is used to check if the pattern of @var{insn} has a speculative
@@ -6776,13 +6776,13 @@  speculation.  If the return value equals 1 then @v
 the generated speculative pattern.
 @end deftypefn
 
-@deftypefn {Target Hook} bool TARGET_SCHED_NEEDS_BLOCK_P (int @var{dep_status})
+@deftypefn {Target Hook} bool TARGET_SCHED_NEEDS_BLOCK_P (unsigned int @var{dep_status})
 This hook is called by the insn scheduler during generation of recovery code
 for @var{insn}.  It should return @code{true}, if the corresponding check
 instruction should branch to recovery code, or @code{false} otherwise.
 @end deftypefn
 
-@deftypefn {Target Hook} rtx TARGET_SCHED_GEN_SPEC_CHECK (rtx @var{insn}, rtx @var{label}, int @var{mutate_p})
+@deftypefn {Target Hook} rtx TARGET_SCHED_GEN_SPEC_CHECK (rtx @var{insn}, rtx @var{label}, unsigned int @var{ds})
 This hook is called by the insn scheduler to generate a pattern for recovery
 check instruction.  If @var{mutate_p} is zero, then @var{insn} is a
 speculative instruction for which the check should be generated.
Index: config/ia64/ia64.c
===================================================================
--- config/ia64/ia64.c	(revision 198799)
+++ config/ia64/ia64.c	(working copy)
@@ -170,7 +170,7 @@  static ds_t ia64_get_insn_spec_ds (rtx);
 static ds_t ia64_get_insn_checked_ds (rtx);
 static bool ia64_skip_rtx_p (const_rtx);
 static int ia64_speculate_insn (rtx, ds_t, rtx *);
-static bool ia64_needs_block_p (int);
+static bool ia64_needs_block_p (ds_t);
 static rtx ia64_gen_spec_check (rtx, rtx, ds_t);
 static int ia64_spec_check_p (rtx);
 static int ia64_spec_check_src_p (rtx);
@@ -8341,9 +8341,7 @@  ia64_needs_block_p (ds_t ts)
   return !(mflag_sched_spec_control_ldc && mflag_sched_spec_ldc);
 }
 
-/* Generate (or regenerate, if (MUTATE_P)) recovery check for INSN.
-   If (LABEL != 0 || MUTATE_P), generate branchy recovery check.
-   Otherwise, generate a simple check.  */
+/* Generate (or regenerate) a recovery check for INSN.  */
 static rtx
 ia64_gen_spec_check (rtx insn, rtx label, ds_t ds)
 {