In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.
Message ID | 20230529105120.1703-1-jinma@linux.alibaba.com |
---|---|
State | New |
Headers |
Return-Path: <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A35A8384646E for <patchwork@sourceware.org>; Mon, 29 May 2023 10:52:11 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A35A8384646E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1685357531; bh=FghtuD1slhKgrR5UFKa5FKmJptZu188J7OTEBijAYkw=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=l/bj54DhJMqqPPtp1MCf4BpLcWWsg2bG6DukhqQ77Rq0GJwLs3ruC/aKUygdEd3YH Se3JzRpkniNu6fGaWUDnlsOiujX0bWAzFWpftfYYh8uSTvjER0XJOx4zxPI+DTO6gC N/bm8cNxTSYZfGOoAcM4E0Rmsf975N9PgXtlTa/o= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from out30-100.freemail.mail.aliyun.com (out30-100.freemail.mail.aliyun.com [115.124.30.100]) by sourceware.org (Postfix) with ESMTPS id 7C3723858C78 for <gcc-patches@gcc.gnu.org>; Mon, 29 May 2023 10:51:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7C3723858C78 X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R621e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=ay29a033018046056; MF=jinma@linux.alibaba.com; NM=1; PH=DS; RN=7; SR=0; TI=SMTPD_---0VjlpVmM_1685357492; Received: from localhost.localdomain(mailfrom:jinma@linux.alibaba.com fp:SMTPD_---0VjlpVmM_1685357492) by smtp.aliyun-inc.com; Mon, 29 May 2023 18:51:35 +0800 To: gcc-patches@gcc.gnu.org Cc: jeffreyalaw@gmail.com, richard.sandiford@arm.com, kito.cheng@gmail.com, christoph.muellner@vrull.eu, jinma.contrib@gmail.com, Jin Ma <jinma@linux.alibaba.com> Subject: [PATCH] In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range. Date: Mon, 29 May 2023 18:51:20 +0800 Message-Id: <20230529105120.1703-1-jinma@linux.alibaba.com> X-Mailer: git-send-email 2.38.1.windows.1 In-Reply-To: <b86699b5-3eae-ff52-3e52-f54bbd6f5a40@gmail.com> References: <b86699b5-3eae-ff52-3e52-f54bbd6f5a40@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-21.0 required=5.0 tests=BAYES_00, ENV_AND_HDR_SPF_MATCH, GIT_PATCH_0, KAM_DMARC_STATUS, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, UNPARSEABLE_RELAY, USER_IN_DEF_SPF_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list <gcc-patches.gcc.gnu.org> List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> From: Jin Ma via Gcc-patches <gcc-patches@gcc.gnu.org> Reply-To: Jin Ma <jinma@linux.alibaba.com> Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> |
Series |
In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.
|
|
Commit Message
Jin Ma
May 29, 2023, 10:51 a.m. UTC
Unrecog insns (such as CLOBBER, USE) does not represent real instructions, but in the process of pipeline optimization, they will wait for transmission in ready list like other insns, without considering resource conflicts and cycles. This results in a multi-issue CPU architecture that can be issued at any time if other regular insns have resource conflicts or cannot be launched for other reasons. As a result, its position is advanced in the generated insns sequence, which will affect register allocation and often lead to more redundant mov instructions. A simple example: https://github.com/majin2020/gcc-test/blob/master/test.c This is a function in the dhrystone benchmark. https://github.com/majin2020/gcc-test/blob/0b08c1a13de9663d7d9aba7539b960ec0607ca24/test.c.299r.sched1 This is a log of the pass 'sched1' When issue_rate == 2. Among them, insn 13 and 14 are much ahead of schedule, which risks generating redundant mov instructions, which seems unreasonable. Therefore, I submit patch again on the basis of the last review opinions to try to solve this problem. This is the new log of shed1 after patch is added. https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd gcc/ChangeLog: * haifa-sched.cc (unrecog_insn_for_forw_only_p): New. (prune_ready_list): UNRECOG INSN is not executed in advance if it starts a live range. --- gcc/haifa-sched.cc | 44 +++++++++++++++++++++++++++++++++++++++----- 1 file changed, 39 insertions(+), 5 deletions(-)
Comments
ping: https://gcc.gnu.org/pipermail/gcc-patches/2023-May/619951.html Ref: http://patchwork.ozlabs.org/project/gcc/patch/20230323080734.423-1-jinma@linux.alibaba.com/
On 5/29/23 04:51, Jin Ma wrote: > Unrecog insns (such as CLOBBER, USE) does not represent real instructions, but in the > process of pipeline optimization, they will wait for transmission in ready list like > other insns, without considering resource conflicts and cycles. This results in a > multi-issue CPU architecture that can be issued at any time if other regular insns > have resource conflicts or cannot be launched for other reasons. As a result, its > position is advanced in the generated insns sequence, which will affect register > allocation and often lead to more redundant mov instructions. > > A simple example: > https://github.com/majin2020/gcc-test/blob/master/test.c > This is a function in the dhrystone benchmark. > > https://github.com/majin2020/gcc-test/blob/0b08c1a13de9663d7d9aba7539b960ec0607ca24/test.c.299r.sched1 > This is a log of the pass 'sched1' When issue_rate == 2. Among them, insn 13 and 14 are > much ahead of schedule, which risks generating redundant mov instructions, which seems > unreasonable. > > Therefore, I submit patch again on the basis of the last review opinions to try to solve > this problem. > > This is the new log of shed1 after patch is added. > https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd > > gcc/ChangeLog: > > * haifa-sched.cc (unrecog_insn_for_forw_only_p): New. > (prune_ready_list): UNRECOG INSN is not executed in advance if it starts a > live range. > --- > gcc/haifa-sched.cc | 44 +++++++++++++++++++++++++++++++++++++++----- > 1 file changed, 39 insertions(+), 5 deletions(-) > > diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc > index 2c881ede0ec..205680a4936 100644 > --- a/gcc/haifa-sched.cc > +++ b/gcc/haifa-sched.cc > @@ -765,6 +765,23 @@ real_insn_for_shadow (rtx_insn *insn) > return pair->i1; > } > > +/* Return true if INSN is unrecog that starts a live range. */ I would rewrite this as /* Return TRUE if INSN (a USE or CLOBBER) starts a new live range, FALSE otherwise. */ > + > +static bool > +unrecog_insn_for_forw_only_p (rtx_insn *insn) I would call this "use_or_clobber_starts_range_p" or something like that. > +{ > + if (insn && !INSN_P (insn) && recog_memoized (insn) >= 0) > + return false; I would drop the test that INSN is not NULL in this test. There's no way it can ever be NULL here. If you really want to check that, then I'd do something like gcc_assert (INSN); Instead of checking it in that condition. > @@ -6320,11 +6337,28 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p, > } > else if (recog_memoized (insn) < 0) > { > - if (!first_cycle_insn_p > - && (GET_CODE (PATTERN (insn)) == ASM_INPUT > - || asm_noperands (PATTERN (insn)) >= 0)) > - cost = 1; > - reason = "asm"; > + if (GET_CODE (PATTERN (insn)) == ASM_INPUT > + || asm_noperands (PATTERN (insn)) >= 0) > + { > + reason = "asm"; > + if (!first_cycle_insn_p) > + cost = 1; > + } > + else if (unrecog_insn_for_forw_only_p (insn)) > + { > + reason = "unrecog insn"; > + if (!first_cycle_insn_p) > + cost = 1; > + else > + { > + int j = i; > + while (n > ++j) > + if (!unrecog_insn_for_forw_only_p (ready_element (&ready, j))) > + break; > + > + cost = (j == n) ? 0 : 1; > + } Why do you need a different cost based on what's in the ready list? Isn't the only property we're looking for whether or not the USE/CLOBBER opens a live range? Jeff
> On 5/29/23 04:51, Jin Ma wrote: > > Unrecog insns (such as CLOBBER, USE) does not represent real instructions, but in the > > process of pipeline optimization, they will wait for transmission in ready list like > > other insns, without considering resource conflicts and cycles. This results in a > > multi-issue CPU architecture that can be issued at any time if other regular insns > > have resource conflicts or cannot be launched for other reasons. As a result, its > > position is advanced in the generated insns sequence, which will affect register > > allocation and often lead to more redundant mov instructions. > > > > A simple example: > > https://github.com/majin2020/gcc-test/blob/master/test.c > > This is a function in the dhrystone benchmark. > > > > https://github.com/majin2020/gcc-test/blob/0b08c1a13de9663d7d9aba7539b960ec0607ca24/test.c.299r.sched1 > > This is a log of the pass 'sched1' When issue_rate == 2. Among them, insn 13 and 14 are > > much ahead of schedule, which risks generating redundant mov instructions, which seems > > unreasonable. > > > > Therefore, I submit patch again on the basis of the last review opinions to try to solve > > this problem. > > > > This is the new log of shed1 after patch is added. > > https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd > > > > gcc/ChangeLog: > > > > * haifa-sched.cc (unrecog_insn_for_forw_only_p): New. > > (prune_ready_list): UNRECOG INSN is not executed in advance if it starts a > > live range. > > --- > > gcc/haifa-sched.cc | 44 +++++++++++++++++++++++++++++++++++++++----- > > 1 file changed, 39 insertions(+), 5 deletions(-) > > > > diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc > > index 2c881ede0ec..205680a4936 100644 > > --- a/gcc/haifa-sched.cc > > +++ b/gcc/haifa-sched.cc > > @@ -765,6 +765,23 @@ real_insn_for_shadow (rtx_insn *insn) > > return pair->i1; > > } > > > > +/* Return true if INSN is unrecog that starts a live range. */ > I would rewrite this as > > /* Return TRUE if INSN (a USE or CLOBBER) starts a new live > range, FALSE otherwise. */ Ok. > > + > > +static bool > > +unrecog_insn_for_forw_only_p (rtx_insn *insn) > I would call this "use_or_clobber_starts_range_p" or something like that. Ok. > > +{ > > + if (insn && !INSN_P (insn) && recog_memoized (insn) >= 0) > > + return false; > I would drop the test that INSN is not NULL in this test. There's no > way it can ever be NULL here. > > If you really want to check that, then I'd do something like > > gcc_assert (INSN); > > Instead of checking it in that condition. Ok. > > @@ -6320,11 +6337,28 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p, > > } > > else if (recog_memoized (insn) < 0) > > { > > - if (!first_cycle_insn_p > > - && (GET_CODE (PATTERN (insn)) == ASM_INPUT > > - || asm_noperands (PATTERN (insn)) >= 0)) > > - cost = 1; > > - reason = "asm"; > > + if (GET_CODE (PATTERN (insn)) == ASM_INPUT > > + || asm_noperands (PATTERN (insn)) >= 0) > > + { > > + reason = "asm"; > > + if (!first_cycle_insn_p) > > + cost = 1; > > + } > > + else if (unrecog_insn_for_forw_only_p (insn)) > > + { > > + reason = "unrecog insn"; > > + if (!first_cycle_insn_p) > > + cost = 1; > > + else > > + { > > + int j = i; > > + while (n > ++j) > > + if (!unrecog_insn_for_forw_only_p (ready_element (&ready, j))) > > + break; > > + > > + cost = (j == n) ? 0 : 1; > > + } > Why do you need a different cost based on what's in the ready list? > Isn't the only property we're looking for whether or not the USE/CLOBBER > opens a live range? > > Jeff For this, I found that if I only look for the USE/CLOBBER that opens a live range, when there is only the USE/CLOBBERs left in the ready list, there will be an infinite loop, because we will always postpone it to the next cycle(cost = 1), causing it to never be emitted and always be in the ready list. So I think (may not be correct) when there is only the USE/CLOBBERs left in the ready list, the cost should be set to 0, and the USE/CLOBBER can be emitted immediately. Maybe there's a better way?
On 6/11/23 21:38, Jin Ma wrote: >> Why do you need a different cost based on what's in the ready list? >> Isn't the only property we're looking for whether or not the USE/CLOBBER >> opens a live range? >> >> Jeff > > For this, I found that if I only look for the USE/CLOBBER that opens a live range, > when there is only the USE/CLOBBERs left in the ready list, there will be an infinite > loop, because we will always postpone it to the next cycle(cost = 1), causing it to > never be emitted and always be in the ready list. > > So I think (may not be correct) when there is only the USE/CLOBBERs left in the ready > list, the cost should be set to 0, and the USE/CLOBBER can be emitted immediately. > > Maybe there's a better way? Yea, I guess this makes sense. Let me take a look at your V2 with that in mind. Sorry for the long delays here. jeff
diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc index 2c881ede0ec..205680a4936 100644 --- a/gcc/haifa-sched.cc +++ b/gcc/haifa-sched.cc @@ -765,6 +765,23 @@ real_insn_for_shadow (rtx_insn *insn) return pair->i1; } +/* Return true if INSN is unrecog that starts a live range. */ + +static bool +unrecog_insn_for_forw_only_p (rtx_insn *insn) +{ + if (insn && !INSN_P (insn) && recog_memoized (insn) >= 0) + return false; + + if ((GET_CODE (PATTERN (insn)) == CLOBBER + || GET_CODE (PATTERN (insn)) == USE) + && !sd_lists_empty_p (insn, SD_LIST_FORW) + && sd_lists_empty_p (insn, SD_LIST_BACK)) + return true; + + return false; +} + /* For a pair P of insns, return the fixed distance in cycles from the first insn after which the second must be scheduled. */ static int @@ -6320,11 +6337,28 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p, } else if (recog_memoized (insn) < 0) { - if (!first_cycle_insn_p - && (GET_CODE (PATTERN (insn)) == ASM_INPUT - || asm_noperands (PATTERN (insn)) >= 0)) - cost = 1; - reason = "asm"; + if (GET_CODE (PATTERN (insn)) == ASM_INPUT + || asm_noperands (PATTERN (insn)) >= 0) + { + reason = "asm"; + if (!first_cycle_insn_p) + cost = 1; + } + else if (unrecog_insn_for_forw_only_p (insn)) + { + reason = "unrecog insn"; + if (!first_cycle_insn_p) + cost = 1; + else + { + int j = i; + while (n > ++j) + if (!unrecog_insn_for_forw_only_p (ready_element (&ready, j))) + break; + + cost = (j == n) ? 0 : 1; + } + } } else if (sched_pressure != SCHED_PRESSURE_NONE) {