[PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Wilco Dijkstra]

The comparison order for SCHED_PRESSURE_MODEL is incorrect.  If either
instruction is not in target_bb, the ordering is not well defined.  To fix
this, give all instructions in target_bb the highest priority and sort all
other instructions behind it.  This way instructions in target_bb will be
sorted using the pressure model, and instructions outside it will use
RFS_DEP_COUNT and/or RFS_TIE for their order.

Bootstrap OK on AArch64, OK for commit?

ChangeLog:
2018-01-31  Wilco Dijkstra  <wdijkstr@arm.com>

	PR rlt-optimization/84068
	* haifa-sched.c (rank_for_schedule): Fix SCHED_PRESSURE_MODEL sorting.

	PR rlt-optimization/84068
	* gcc.dg/pr84068.c: New test.
--

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index ebdec46bf04f1ba07e8b70607602a3bc9e7ec7de..2c9dd87426930ee99b2a4c0950cadea96f9553bc 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -2783,12 +2783,18 @@ rank_for_schedule (const void *x, const void *y)
     }
 
   /* Prefer instructions that occur earlier in the model schedule.  */
-  if (sched_pressure == SCHED_PRESSURE_MODEL
-      && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
+  if (sched_pressure == SCHED_PRESSURE_MODEL)
     {
-      diff = model_index (tmp) - model_index (tmp2);
-      gcc_assert (diff != 0);
-      return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
+      if (INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
+	{
+	  diff = model_index (tmp) - model_index (tmp2);
+	  gcc_assert (diff != 0);
+	  return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
+	}
+      else if (INSN_BB (tmp) == target_bb)
+	return rfs_result (RFS_PRESSURE_INDEX, -1, tmp, tmp2);
+      else if (INSN_BB (tmp2) == target_bb)
+	return rfs_result (RFS_PRESSURE_INDEX, 1, tmp, tmp2);
     }
 
   /* Prefer the insn which has more later insns that depend on it.
diff --git a/gcc/testsuite/gcc.dg/pr84068.c b/gcc/testsuite/gcc.dg/pr84068.c
new file mode 100644
index 0000000000000000000000000000000000000000..13110d84455f20edfc50f09efe4074721bd6a7d0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr84068.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-sched-critical-path-heuristic -fno-sched-rank-heuristic --param=max-sched-extend-regions-iters=5 --param sched-pressure-algorithm=2" } */
+
+#ifdef __SIZEOF_INT128__
+typedef __int128 largeint;
+#else
+typedef long long largeint;
+#endif
+
+largeint a;
+int b;
+
+largeint
+foo (char d, short e, int f)
+{
+  b = __builtin_sub_overflow_p (b, 1, (unsigned long)0);
+  return a + f;
+}

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Alexander Monakov]

On Wed, 31 Jan 2018, Wilco Dijkstra wrote:

> The comparison order for SCHED_PRESSURE_MODEL is incorrect.  If either
> instruction is not in target_bb, the ordering is not well defined.  To fix
> this, give all instructions in target_bb the highest priority and sort all
> other instructions behind it.  This way instructions in target_bb will be
> sorted using the pressure model, and instructions outside it will use
> RFS_DEP_COUNT and/or RFS_TIE for their order.

This appears to be the same issue as PR 83459; please add rtl-optimization/83459
to ChangeLog if approved.

> 	PR rlt-optimization/84068
> 	* haifa-sched.c (rank_for_schedule): Fix SCHED_PRESSURE_MODEL sorting.
> 
> 	PR rlt-optimization/84068

Note typos in category name (s/rlt/rtl).

Alexander

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Alexander Monakov]

> On Wed, 31 Jan 2018, Wilco Dijkstra wrote:
> 
> > The comparison order for SCHED_PRESSURE_MODEL is incorrect.  If either
> > instruction is not in target_bb, the ordering is not well defined.  To fix
> > this, give all instructions in target_bb the highest priority and sort all
> > other instructions behind it.  This way instructions in target_bb will be
> > sorted using the pressure model, and instructions outside it will use
> > RFS_DEP_COUNT and/or RFS_TIE for their order.
> 
> This appears to be the same issue as PR 83459; please add rtl-optimization/83459
> to ChangeLog if approved.
> 
> > 	PR rlt-optimization/84068
> > 	* haifa-sched.c (rank_for_schedule): Fix SCHED_PRESSURE_MODEL sorting.
> > 
> > 	PR rlt-optimization/84068
> 
> Note typos in category name (s/rlt/rtl).

This and the previous point applies to v2 as well.

Thanks.
Alexander

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Richard Sandiford]

Wilco Dijkstra <Wilco.Dijkstra@arm.com> writes:
> The comparison order for SCHED_PRESSURE_MODEL is incorrect.  If either
> instruction is not in target_bb, the ordering is not well defined.  To fix
> this, give all instructions in target_bb the highest priority and sort all
> other instructions behind it.  This way instructions in target_bb will be
> sorted using the pressure model, and instructions outside it will use
> RFS_DEP_COUNT and/or RFS_TIE for their order.
>
> Bootstrap OK on AArch64, OK for commit?
>
> ChangeLog:
> 2018-01-31  Wilco Dijkstra  <wdijkstr@arm.com>
>
> 	PR rlt-optimization/84068
> 	* haifa-sched.c (rank_for_schedule): Fix SCHED_PRESSURE_MODEL sorting.
>
> 	PR rlt-optimization/84068
> 	* gcc.dg/pr84068.c: New test.
> --
>
> diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
> index ebdec46bf04f1ba07e8b70607602a3bc9e7ec7de..2c9dd87426930ee99b2a4c0950cadea96f9553bc 100644
> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -2783,12 +2783,18 @@ rank_for_schedule (const void *x, const void *y)
>      }
>  
>    /* Prefer instructions that occur earlier in the model schedule.  */
> -  if (sched_pressure == SCHED_PRESSURE_MODEL
> -      && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
> +  if (sched_pressure == SCHED_PRESSURE_MODEL)
>      {
> -      diff = model_index (tmp) - model_index (tmp2);
> -      gcc_assert (diff != 0);
> -      return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
> +      if (INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
> +	{
> +	  diff = model_index (tmp) - model_index (tmp2);
> +	  gcc_assert (diff != 0);
> +	  return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
> +	}
> +      else if (INSN_BB (tmp) == target_bb)
> +	return rfs_result (RFS_PRESSURE_INDEX, -1, tmp, tmp2);
> +      else if (INSN_BB (tmp2) == target_bb)
> +	return rfs_result (RFS_PRESSURE_INDEX, 1, tmp, tmp2);
>      }

This was the original intent, but was changed in r213708.  TBH I'm not
sure what the second hunk in that revision fixed, since model_index is
supposed to return an index greater than all valid indices when passed
an instruction outside the current block.  Maxim, do you remember?

Thanks,
Richard

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Wilco Dijkstra]

Richard Sandiford wrote:

> This was the original intent, but was changed in r213708.  TBH I'm not
> sure what the second hunk in that revision fixed, since model_index is
> supposed to return an index greater than all valid indices when passed
> an instruction outside the current block.  Maxim, do you remember?

See https://gcc.gnu.org/ml/gcc-patches/2014-07/msg00932.html, it says:

"The second one is to account for the fact that model_index() of two instructions
is meaningful only when both instructions are in the current basic block."

Unless something has changed, I'm assuming that's still true today. Maybe
the underlying idea was to allow interleaving of instructions outside the
current block, but that isn't feasible if you want a well-defined sort ordering.

Wilco

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Maxim Kuvyrkov]

> On Jan 31, 2018, at 4:33 PM, Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
> 
> Richard Sandiford wrote:
> 
>> This was the original intent, but was changed in r213708.  TBH I'm not
>> sure what the second hunk in that revision fixed, since model_index is
>> supposed to return an index greater than all valid indices when passed
>> an instruction outside the current block.  Maxim, do you remember?
> 
> See https://gcc.gnu.org/ml/gcc-patches/2014-07/msg00932.html, it says:
> 
> "The second one is to account for the fact that model_index() of two instructions
> is meaningful only when both instructions are in the current basic block."
> 
> Unless something has changed, I'm assuming that's still true today. Maybe
> the underlying idea was to allow interleaving of instructions outside the
> current block,

Yes.

> but that isn't feasible if you want a well-defined sort ordering.

Agree.

Wilco, your patch looks good.  Thanks for fixing this!

--
Maxim Kuvyrkov
www.linaro.org

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Richard Sandiford]

Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org> writes:
>> On Jan 31, 2018, at 4:33 PM, Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
>> 
>> Richard Sandiford wrote:
>> 
>>> This was the original intent, but was changed in r213708.  TBH I'm not
>>> sure what the second hunk in that revision fixed, since model_index is
>>> supposed to return an index greater than all valid indices when passed
>>> an instruction outside the current block.  Maxim, do you remember?
>> 
>> See https://gcc.gnu.org/ml/gcc-patches/2014-07/msg00932.html, it says:
>> 
>> "The second one is to account for the fact that model_index() of two
>> instructions
>> is meaningful only when both instructions are in the current basic block."
>> 
>> Unless something has changed, I'm assuming that's still true today. Maybe
>> the underlying idea was to allow interleaving of instructions outside the
>> current block,
>
> Yes.

But why wasn't the index 0 as expected for the insns outside of the block?

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Wilco Dijkstra]

Richard Sandiford wrote:

> But why wasn't the index 0 as expected for the insns outside of the block?

Well it seems it checks for index 0 and sets the model_index as the current
maximum model_index count.  This means the target_bb check isn't
strictly required - I build all of SPECINT2017 using the options from PR84068,
and all 577k instances of instruction from another bb would sort correctly.

So it looks we can remove the target_bb check.

Wilco

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Richard Sandiford]

Wilco Dijkstra <Wilco.Dijkstra@arm.com> writes:
> Richard Sandiford wrote:
>
>> But why wasn't the index 0 as expected for the insns outside of the block?
>
> Well it seems it checks for index 0 and sets the model_index as the current
> maximum model_index count.  This means the target_bb check isn't
> strictly required - I build all of SPECINT2017 using the options from PR84068,
> and all 577k instances of instruction from another bb would sort correctly.
>
> So it looks we can remove the target_bb check.

Thanks for testing that.  Removing the check would be my preference,
since model_index was supposed to cope with insns outside the model
schedule, and I think other callers relied on that too.

If we do end up finding cases in which INSN_MODEL_INDEX is nonzero
for insns in other blocks, I think it would better to fix that,
either by forcing it to zero at an appropriate place, or by checking
the block in model_index itself.

Richard

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Wilco Dijkstra]

Right, so here is version 2 which ends up much simpler:

The comparison function for SCHED_PRESSURE_MODEL is incorrect.  If either
instruction is not in target_bb, the ordering is not well defined.  
Since all instructions outside the target_bb get the highest model_index,
all we need to do is sort on model_index.  If the model_index is the same
we defer to RFS_DEP_COUNT and/or RFS_TIE.

Bootstrap OK, OK for commit?

ChangeLog:
2018-02-02  Wilco Dijkstra  <wdijkstr@arm.com>

	PR rlt-optimization/84068
	* haifa-sched.c (rank_for_schedule): Fix SCHED_PRESSURE_MODEL sorting.

	PR rlt-optimization/84068
	* gcc.dg/pr84068.c: New test.
--

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index ebdec46bf04f1ba07e8b70607602a3bc9e7ec7de..4a899b56173dd7d67db084ed86d24ad865ccadcd 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -2783,12 +2783,11 @@ rank_for_schedule (const void *x, const void *y)
     }
 
   /* Prefer instructions that occur earlier in the model schedule.  */
-  if (sched_pressure == SCHED_PRESSURE_MODEL
-      && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
+  if (sched_pressure == SCHED_PRESSURE_MODEL)
     {
       diff = model_index (tmp) - model_index (tmp2);
-      gcc_assert (diff != 0);
-      return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
+      if (diff != 0)
+	return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
     }
 
   /* Prefer the insn which has more later insns that depend on it.
diff --git a/gcc/testsuite/gcc.dg/pr84068.c b/gcc/testsuite/gcc.dg/pr84068.c
new file mode 100644
index 0000000000000000000000000000000000000000..13110d84455f20edfc50f09efe4074721bd6a7d0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr84068.c
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-sched-critical-path-heuristic -fno-sched-rank-heuristic --param=max-sched-extend-regions-iters=5 --param sched-pressure-algorithm=2" } */
+
+#ifdef __SIZEOF_INT128__
+typedef __int128 largeint;
+#else
+typedef long long largeint;
+#endif
+
+largeint a;
+int b;
+
+largeint
+foo (char d, short e, int f)
+{
+  b = __builtin_sub_overflow_p (b, 1, (unsigned long)0);
+  return a + f;
+}
    

Re: [PATCH] PR84068: Fix sort order of SCHED_PRESSURE_MODEL

[Maxim Kuvyrkov]

> On Feb 2, 2018, at 7:40 PM, Wilco Dijkstra <Wilco.Dijkstra@arm.com> wrote:
> 
> Right, so here is version 2 which ends up much simpler:
> 
> The comparison function for SCHED_PRESSURE_MODEL is incorrect.  If either
> instruction is not in target_bb, the ordering is not well defined.  
> Since all instructions outside the target_bb get the highest model_index,
> all we need to do is sort on model_index.  If the model_index is the same
> we defer to RFS_DEP_COUNT and/or RFS_TIE.
> 
> Bootstrap OK, OK for commit?

Looks good to me.

--
Maxim Kuvyrkov
www.linaro.org

> 
> ChangeLog:
> 2018-02-02  Wilco Dijkstra  <wdijkstr@arm.com>
> 
> 	PR rlt-optimization/84068
> 	* haifa-sched.c (rank_for_schedule): Fix SCHED_PRESSURE_MODEL sorting.
> 
> 	PR rlt-optimization/84068
> 	* gcc.dg/pr84068.c: New test.
> --
> 
> diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
> index ebdec46bf04f1ba07e8b70607602a3bc9e7ec7de..4a899b56173dd7d67db084ed86d24ad865ccadcd 100644
> --- a/gcc/haifa-sched.c
> +++ b/gcc/haifa-sched.c
> @@ -2783,12 +2783,11 @@ rank_for_schedule (const void *x, const void *y)
>     }
> 
>   /* Prefer instructions that occur earlier in the model schedule.  */
> -  if (sched_pressure == SCHED_PRESSURE_MODEL
> -      && INSN_BB (tmp) == target_bb && INSN_BB (tmp2) == target_bb)
> +  if (sched_pressure == SCHED_PRESSURE_MODEL)
>     {
>       diff = model_index (tmp) - model_index (tmp2);
> -      gcc_assert (diff != 0);
> -      return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
> +      if (diff != 0)
> +	return rfs_result (RFS_PRESSURE_INDEX, diff, tmp, tmp2);
>     }
> 
>   /* Prefer the insn which has more later insns that depend on it.
> diff --git a/gcc/testsuite/gcc.dg/pr84068.c b/gcc/testsuite/gcc.dg/pr84068.c
> new file mode 100644
> index 0000000000000000000000000000000000000000..13110d84455f20edfc50f09efe4074721bd6a7d0
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/pr84068.c
> @@ -0,0 +1,18 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fno-sched-critical-path-heuristic -fno-sched-rank-heuristic --param=max-sched-extend-regions-iters=5 --param sched-pressure-algorithm=2" } */
> +
> +#ifdef __SIZEOF_INT128__
> +typedef __int128 largeint;
> +#else
> +typedef long long largeint;
> +#endif
> +
> +largeint a;
> +int b;
> +
> +largeint
> +foo (char d, short e, int f)
> +{
> +  b = __builtin_sub_overflow_p (b, 1, (unsigned long)0);
> +  return a + f;
> +}