From patchwork Sun May 12 15:45:14 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Steven Bosscher X-Patchwork-Id: 243188 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 6F4712C0085 for ; Mon, 13 May 2013 01:46:06 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:cc:content-type; q=dns; s=default; b=k3+WNJFGwAin27HqGmAtl1O3og8V5821NostQuQT+3q ydwpVFmZTPslAbzirgB0o3s1xnJzmn8KJrwTfYJtLfwyCCo/U1LAt2yGXloceDr9 by7XhcY78ScuSpvbh4JvzbOd9LH4zEDDcyy2bq0vVO9tpXd3zsXeH6VEUMQPy4Z8 = DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:cc:content-type; s=default; bh=kj4gj8QRJsji0vq3cBHDyYYY330=; b=J425hvQeyew17s8UA 5UMBDRIA4ElRcdwoBe/2rVyO+hnIO7yqeWQ5iNUjudBdxxCNBulEwfHZLgOMHEVP PXQkiThjjTLUnKrxc3dnPaJLdFbLj/OvHsTs6pgYp18EjyCTVakjB2b8puIZsHAL hf5/9yuA4TJNQfMtbud1JW8qfs= Received: (qmail 15104 invoked by alias); 12 May 2013 15:45:59 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 15094 invoked by uid 89); 12 May 2013 15:45:58 -0000 X-Spam-SWARE-Status: No, score=-2.7 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, SPF_PASS autolearn=ham version=3.3.1 Received: from mail-ve0-f169.google.com (HELO mail-ve0-f169.google.com) (209.85.128.169) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Sun, 12 May 2013 15:45:56 +0000 Received: by mail-ve0-f169.google.com with SMTP id jz10so5063510veb.14 for ; Sun, 12 May 2013 08:45:54 -0700 (PDT) X-Received: by 10.220.173.6 with SMTP id n6mr16125946vcz.52.1368373554763; Sun, 12 May 2013 08:45:54 -0700 (PDT) MIME-Version: 1.0 Received: by 10.58.50.40 with HTTP; Sun, 12 May 2013 08:45:14 -0700 (PDT) From: Steven Bosscher Date: Sun, 12 May 2013 17:45:14 +0200 Message-ID: Subject: [patch] Fix sched-deps DEP_POSTPONED, ds_t documentation To: GCC Patches Cc: Bernd Schmidt X-Virus-Found: No 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): 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 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 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) {