[PATCH] In the ready lists of pipeline, put unrecog insns (such as CLOBBER,USE) at the latest to issue.

[PATCH] In the ready lists of pipeline, put unrecog insns (such as CLOBBER,USE) at the latest to issue.

[Jin Ma]

  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.

gcc/ChangeLog:

	* haifa-sched.cc (prune_ready_list): Consider unrecog insns(CLOBBER and USE)
	in pruning ready lists.
---
 gcc/haifa-sched.cc | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc
index 48b53776fa9..72c4c44da76 100644
--- a/gcc/haifa-sched.cc
+++ b/gcc/haifa-sched.cc
@@ -6318,6 +6318,14 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
 	      cost = 1;
 	      reason = "not a shadow";
 	    }
+	  else if (recog_memoized (insn) < 0
+		  && (GET_CODE (PATTERN (insn)) == CLOBBER
+		  || GET_CODE (PATTERN (insn)) == USE))
+	    {
+	      if (!first_cycle_insn_p)
+		cost = 1;
+	      reason = "unrecog insn";
+	    }
 	  else if (recog_memoized (insn) < 0)
 	    {
 	      if (!first_cycle_insn_p
-- 
2.17.1

Re: [PATCH] In the ready lists of pipeline, put unrecog insns (such as CLOBBER, USE) at the latest to issue.

[Richard Sandiford]

Jin Ma via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
>   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.

Is it the clobber rather than the use case that is causing problems?
I would expect that scheduling a use ASAP would be better for register
pressure, since it might close off the associated live range and so
reduce the number of conflicts.

I.e. is the problem that, when a live range starts with a clobber,
the current code will tend to move the clobber up and so extend
the associated live range?  If so, that sounds like something we
should address more directly, for two reasons:

(1) We should try to prevent clobbers that start a live range from being
    moved up even if first_cycle_insn_p.

(2) Clobbers can also be used to close off a live range, which is useful
    if a pseudo is only written to in parts.  The current behaviour is
    probably better for those clobbers.

In general, if you're hitting register pressure problems with scheduling,
have you tried enabling -fsched-pressure by default, possibly with
--param=sched-pressure-algorithm=2 (but try with the default algo too)?

Thanks,
Richard

>
> gcc/ChangeLog:
>
> 	* haifa-sched.cc (prune_ready_list): Consider unrecog insns(CLOBBER and USE)
> 	in pruning ready lists.

> ---
>  gcc/haifa-sched.cc | 8 ++++++++
>  1 file changed, 8 insertions(+)
>
> diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc
> index 48b53776fa9..72c4c44da76 100644
> --- a/gcc/haifa-sched.cc
> +++ b/gcc/haifa-sched.cc
> @@ -6318,6 +6318,14 @@ prune_ready_list (state_t temp_state, bool first_cycle_insn_p,
>  	      cost = 1;
>  	      reason = "not a shadow";
>  	    }
> +	  else if (recog_memoized (insn) < 0
> +		  && (GET_CODE (PATTERN (insn)) == CLOBBER
> +		  || GET_CODE (PATTERN (insn)) == USE))
> +	    {
> +	      if (!first_cycle_insn_p)
> +		cost = 1;
> +	      reason = "unrecog insn";
> +	    }
>  	  else if (recog_memoized (insn) < 0)
>  	    {
>  	      if (!first_cycle_insn_p

Re: [PATCH] In the ready lists of pipeline, put unrecog insns (such as CLOBBER, USE) at the latest to issue.

[Jeff Law]

On 3/27/23 11:01, Richard Sandiford wrote:
> Jin Ma via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
>>    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.
> 
> Is it the clobber rather than the use case that is causing problems?
> I would expect that scheduling a use ASAP would be better for register
> pressure, since it might close off the associated live range and so
> reduce the number of conflicts.
Agreed.  Issuing USES as soon as possible seems advisable from a 
register pressure standpoint.

A clobber can close off a range as well, but I suspect that is the 
exception rather than the norm.

> 
> I.e. is the problem that, when a live range starts with a clobber,
> the current code will tend to move the clobber up and so extend
> the associated live range?  If so, that sounds like something we
> should address more directly, for two reasons:
Agreed as well.  I would expect the normal case for clobbers is that 
deferring them as late as possible is best as I would expect they 
typically open a live range.

> 
> (1) We should try to prevent clobbers that start a live range from being
>      moved up even if first_cycle_insn_p.
Yes.

> 
> (2) Clobbers can also be used to close off a live range, which is useful
>      if a pseudo is only written to in parts.  The current behaviour is
>      probably better for those clobbers.
I thought these sequences started with a clobber, then the component 
sets.  In which case the clobber isn't closing a live range, but opening 
one and deferring it is advisable.

jeff

[PATCH] In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.

[Jin Ma]

  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.  */
+
+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)
 	    {
-- 
2.17.1

Re: [PATCH] In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.

[Jin Ma]

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/

Re: [PATCH] In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.

[Jeff Law]

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

Re: [PATCH] In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.

[Jin Ma]

> 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?

Re: [PATCH] In the pipeline, UNRECOG INSN is not executed in advance if it starts a live range.

[Jeff Law]

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

[PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Jin Ma]

CLOBBER and 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 -mtune=rocket but issue_rate == 2.

The pipeline is:
;; | insn | prio |
;; |  17  |  3   | r142=a0 alu
;; |  14  |  0   | clobber r136 nothing
;; |  13  |  0   | clobber a0 nothing
;; |  18  |  2   | r143=a1 alu
...
;; |  12  |  0   | a0=r136 alu
;; |  15  |  0   | use a0 nothing

In this log, 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.

https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd#diff-805031b1be5092a2322852a248d0b0f92eef7cad5784a8209f4dfc6221407457L189
This is the diff log of shed1 after patch is added.

The new pipeline is:
;; | insn | prio |
;; |  17  |  3   | r142=a0 alu
...
;; |  10  |  0   | [r144]=r141 alu
;; |  13  |  0   | clobber a0 nothing
;; |  14  |  0   | clobber r136 nothing
;; |  12  |  0   | a0=r136 alu
;; |  15  |  0   | use a0 nothing

gcc/ChangeLog:
	* haifa-sched.cc (use_or_clobber_starts_range_p): New.
	(prune_ready_list): USE or CLOBBER should delay execution
	if it starts a new live range.
---
 gcc/haifa-sched.cc | 55 +++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 50 insertions(+), 5 deletions(-)

diff --git a/gcc/haifa-sched.cc b/gcc/haifa-sched.cc
index 8e8add709b3..47ad09457c7 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 (a USE or CLOBBER) starts a new live
+    range, FALSE otherwise.  */
+
+static bool
+use_or_clobber_starts_range_p (rtx_insn *insn)
+{
+  gcc_assert (insn);
+
+  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,39 @@ 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 (use_or_clobber_starts_range_p (insn))
+		{
+		  /* If USE or CLOBBER opens an active range, its execution should
+		     be delayed so as to be closer to the relevant instructions and
+		     avoid the generation of some redundant mov instructions.
+		     Otherwise, it should be executed as soon as possible.  */
+		  reason = "unrecog insn";
+		  if (!first_cycle_insn_p)
+		    /* If USE or CLOBBER is not in the first cycle, simply delay it
+		       by one cycle.  */
+		    cost = 1;
+		  else
+		    {
+		      /* If the USE or CLOBBER is in the first cycle and there are no
+			 other non-USE or non-CLOBBER instructions after it, we need
+			 to execute it immediately, otherwise we need to execute the
+			 non-USE or non-CLOBBER instructions first and postpone the
+			 execution of the USE or CLOBBER instructions.  */
+		      int j = i;
+		      while (n > ++j)
+			if (!use_or_clobber_starts_range_p (ready_element (&ready, j)))
+			  break;
+
+		      cost = (j == n) ? 0 : 1;
+		    }
+		}
 	    }
 	  else if (sched_pressure != SCHED_PRESSURE_NONE)
 	    {

base-commit: c944ded09595946290778a26794074e69cc65f3e
-- 
2.17.1

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Jin Ma]

ping

Ref:
https://gcc.gnu.org/pipermail/gcc-patches/2023-August/627341.html
https://gcc.gnu.org/pipermail/gcc-patches/2023-June/621296.html

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Jeff Law]

On 8/14/23 05:22, Jin Ma wrote:
> CLOBBER and 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 -mtune=rocket but issue_rate == 2.
> 
> The pipeline is:
> ;; | insn | prio |
> ;; |  17  |  3   | r142=a0 alu
> ;; |  14  |  0   | clobber r136 nothing
> ;; |  13  |  0   | clobber a0 nothing
> ;; |  18  |  2   | r143=a1 alu
> ...
> ;; |  12  |  0   | a0=r136 alu
> ;; |  15  |  0   | use a0 nothing
> 
> In this log, 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.
> 
> https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd#diff-805031b1be5092a2322852a248d0b0f92eef7cad5784a8209f4dfc6221407457L189
> This is the diff log of shed1 after patch is added.
> 
> The new pipeline is:
> ;; | insn | prio |
> ;; |  17  |  3   | r142=a0 alu
> ...
> ;; |  10  |  0   | [r144]=r141 alu
> ;; |  13  |  0   | clobber a0 nothing
> ;; |  14  |  0   | clobber r136 nothing
> ;; |  12  |  0   | a0=r136 alu
> ;; |  15  |  0   | use a0 nothing
> 
> gcc/ChangeLog:
> 	* haifa-sched.cc (use_or_clobber_starts_range_p): New.
> 	(prune_ready_list): USE or CLOBBER should delay execution
> 	if it starts a new live range.
OK for the trunk.  It doesn't look like you have write access and I 
don't see anything about what testing was done.  Standard practice is to 
do a bootstrap and regression test on a primary platform such as x86, 
aarch64, ppc64.

I went ahead and did a bootstrap and regression test on x86_64, then 
pushed this to the trunk.

Thanks for your patience,

jeff

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Xi Ruoyao]

On Sat, 2023-11-11 at 13:12 -0700, Jeff Law wrote:
> 
> 
> On 8/14/23 05:22, Jin Ma wrote:
> > CLOBBER and 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 -mtune=rocket but issue_rate
> > == 2.
> > 
> > The pipeline is:
> > ;; | insn | prio |
> > ;; |  17  |  3   | r142=a0 alu
> > ;; |  14  |  0   | clobber r136 nothing
> > ;; |  13  |  0   | clobber a0 nothing
> > ;; |  18  |  2   | r143=a1 alu
> > ...
> > ;; |  12  |  0   | a0=r136 alu
> > ;; |  15  |  0   | use a0 nothing
> > 
> > In this log, 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.
> > 
> > https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd#diff-805031b1be5092a2322852a248d0b0f92eef7cad5784a8209f4dfc6221407457L189
> > This is the diff log of shed1 after patch is added.
> > 
> > The new pipeline is:
> > ;; | insn | prio |
> > ;; |  17  |  3   | r142=a0 alu
> > ...
> > ;; |  10  |  0   | [r144]=r141 alu
> > ;; |  13  |  0   | clobber a0 nothing
> > ;; |  14  |  0   | clobber r136 nothing
> > ;; |  12  |  0   | a0=r136 alu
> > ;; |  15  |  0   | use a0 nothing
> > 
> > gcc/ChangeLog:
> > 	* haifa-sched.cc (use_or_clobber_starts_range_p): New.
> > 	(prune_ready_list): USE or CLOBBER should delay execution
> > 	if it starts a new live range.
> OK for the trunk.  It doesn't look like you have write access and I 
> don't see anything about what testing was done.  Standard practice is
> to 
> do a bootstrap and regression test on a primary platform such as x86, 
> aarch64, ppc64.
> 
> I went ahead and did a bootstrap and regression test on x86_64, then 
> pushed this to the trunk.

Unfortunately this patch has triggered a bootstrap comparison failure on
loongarch64-linux-gnu: https://gcc.gnu.org/PR112497.

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Jeff Law]

On 11/12/23 10:41, Xi Ruoyao wrote:
> On Sat, 2023-11-11 at 13:12 -0700, Jeff Law wrote:
>>
>>
>> On 8/14/23 05:22, Jin Ma wrote:
>>> CLOBBER and 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 -mtune=rocket but issue_rate
>>> == 2.
>>>
>>> The pipeline is:
>>> ;; | insn | prio |
>>> ;; |  17  |  3   | r142=a0 alu
>>> ;; |  14  |  0   | clobber r136 nothing
>>> ;; |  13  |  0   | clobber a0 nothing
>>> ;; |  18  |  2   | r143=a1 alu
>>> ...
>>> ;; |  12  |  0   | a0=r136 alu
>>> ;; |  15  |  0   | use a0 nothing
>>>
>>> In this log, 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.
>>>
>>> https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd#diff-805031b1be5092a2322852a248d0b0f92eef7cad5784a8209f4dfc6221407457L189
>>> This is the diff log of shed1 after patch is added.
>>>
>>> The new pipeline is:
>>> ;; | insn | prio |
>>> ;; |  17  |  3   | r142=a0 alu
>>> ...
>>> ;; |  10  |  0   | [r144]=r141 alu
>>> ;; |  13  |  0   | clobber a0 nothing
>>> ;; |  14  |  0   | clobber r136 nothing
>>> ;; |  12  |  0   | a0=r136 alu
>>> ;; |  15  |  0   | use a0 nothing
>>>
>>> gcc/ChangeLog:
>>> 	* haifa-sched.cc (use_or_clobber_starts_range_p): New.
>>> 	(prune_ready_list): USE or CLOBBER should delay execution
>>> 	if it starts a new live range.
>> OK for the trunk.  It doesn't look like you have write access and I
>> don't see anything about what testing was done.  Standard practice is
>> to
>> do a bootstrap and regression test on a primary platform such as x86,
>> aarch64, ppc64.
>>
>> I went ahead and did a bootstrap and regression test on x86_64, then
>> pushed this to the trunk.
> 
> Unfortunately this patch has triggered a bootstrap comparison failure on
> loongarch64-linux-gnu: https://gcc.gnu.org/PR112497.
It's also causing simple build failures on other targets.  For example 
c6x-elf aborts when compiling gcc.c-torture/execute/pr82210 (and others) 
with -O2 with that patch applied.

I've reverted it for now.  I'm not going to have time to investigate 
this week.

Jeff
> 

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Xi Ruoyao]

On Sun, 2023-11-12 at 11:02 -0700, Jeff Law wrote:
> 
> 
> On 11/12/23 10:41, Xi Ruoyao wrote:
> > On Sat, 2023-11-11 at 13:12 -0700, Jeff Law wrote:
> > > 
> > > 
> > > On 8/14/23 05:22, Jin Ma wrote:
> > > > CLOBBER and 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 -mtune=rocket but
> > > > issue_rate
> > > > == 2.
> > > > 
> > > > The pipeline is:
> > > > ;; | insn | prio |
> > > > ;; |  17  |  3   | r142=a0 alu
> > > > ;; |  14  |  0   | clobber r136 nothing
> > > > ;; |  13  |  0   | clobber a0 nothing
> > > > ;; |  18  |  2   | r143=a1 alu
> > > > ...
> > > > ;; |  12  |  0   | a0=r136 alu
> > > > ;; |  15  |  0   | use a0 nothing
> > > > 
> > > > In this log, 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.
> > > > 
> > > > https://github.com/majin2020/gcc-test/commit/efcb43e3369e771bde702955048bfe3f501263dd#diff-805031b1be5092a2322852a248d0b0f92eef7cad5784a8209f4dfc6221407457L189
> > > > This is the diff log of shed1 after patch is added.
> > > > 
> > > > The new pipeline is:
> > > > ;; | insn | prio |
> > > > ;; |  17  |  3   | r142=a0 alu
> > > > ...
> > > > ;; |  10  |  0   | [r144]=r141 alu
> > > > ;; |  13  |  0   | clobber a0 nothing
> > > > ;; |  14  |  0   | clobber r136 nothing
> > > > ;; |  12  |  0   | a0=r136 alu
> > > > ;; |  15  |  0   | use a0 nothing
> > > > 
> > > > gcc/ChangeLog:
> > > > 	* haifa-sched.cc (use_or_clobber_starts_range_p): New.
> > > > 	(prune_ready_list): USE or CLOBBER should delay
> > > > execution
> > > > 	if it starts a new live range.
> > > OK for the trunk.  It doesn't look like you have write access and
> > > I
> > > don't see anything about what testing was done.  Standard practice
> > > is
> > > to
> > > do a bootstrap and regression test on a primary platform such as
> > > x86,
> > > aarch64, ppc64.
> > > 
> > > I went ahead and did a bootstrap and regression test on x86_64,
> > > then
> > > pushed this to the trunk.
> > 
> > Unfortunately this patch has triggered a bootstrap comparison
> > failure on
> > loongarch64-linux-gnu: https://gcc.gnu.org/PR112497.
> It's also causing simple build failures on other targets.  For example
> c6x-elf aborts when compiling gcc.c-torture/execute/pr82210 (and
> others) 
> with -O2 with that patch applied.
> 
> I've reverted it for now.  I'm not going to have time to investigate 
> this week.

So I'm marking the PR fixed.  Please CC me when iterating this patch for
another round so I can test it on loongarch64-linux-gnu.

-- 
Xi Ruoyao <xry111@xry111.site>
School of Aerospace Science and Technology, Xidian University

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Jin Ma]

> > 
> > Unfortunately this patch has triggered a bootstrap comparison failure on
> > loongarch64-linux-gnu: https://gcc.gnu.org/PR112497.
> It's also causing simple build failures on other targets.  For example 
> c6x-elf aborts when compiling gcc.c-torture/execute/pr82210 (and others) 
> with -O2 with that patch applied.
> 
> I've reverted it for now.  I'm not going to have time to investigate 
> this week.

I'm sorry to have caused this and had a bad effect. This patch has
been a long time since I verified it, so I don't know what happened, I
will check it out :)

BR
Jin

> Jeff
> >

Re: [PATCH v2] In the pipeline, USE or CLOBBER should delay execution if it starts a new live range.

[Jeff Law]

On 11/12/23 19:16, Jin Ma wrote:
>>>
>>> Unfortunately this patch has triggered a bootstrap comparison failure on
>>> loongarch64-linux-gnu: https://gcc.gnu.org/PR112497.
>> It's also causing simple build failures on other targets.  For example
>> c6x-elf aborts when compiling gcc.c-torture/execute/pr82210 (and others)
>> with -O2 with that patch applied.
>>
>> I've reverted it for now.  I'm not going to have time to investigate
>> this week.
> 
> I'm sorry to have caused this and had a bad effect. This patch has
> been a long time since I verified it, so I don't know what happened, I
> will check it out :)
It happens to all of us.  It's been reverted, so it's not causing anyone 
problems anymore.   We also know that various ports have sensitivity to 
the patch, so we can do deeper testing on it once you think it's ready 
to go again.

Jeff