Re: [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills

[Jeff Law]

On 07/15/2017 02:47 PM, Alexander Monakov wrote:
> The reload_pseudo_compare_func comparator, when used from assign_by_spills,
> can be non-transitive, indicating A < B < C < A if both A and C satisfy
> !bitmap_bit_p (_reload_pseudos, rAC), but B does not.
> 
> This function was originally a proper comparator, and the problematic
> clause was added to fix PR 57878:
> https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html
> 
> That the comparator is invalid implies that that PR, if it still exists,
> can reappear (but probably under more complicated circumstances).
> 
> This looks like a sensitive area, so disabling checking is the only
> obvious approach.
> 
>   * lra-assigns.c (reload_pseudo_compare_func): Add a FIXME.
> (assign_by_spills): Use non-checking qsort.
This is OK once the final comparator consistency checking patch is approved.

jeff

Re: [PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills

[Yuri Gribov]

On Sat, Jul 15, 2017 at 9:47 PM, Alexander Monakov  wrote:
> The reload_pseudo_compare_func comparator, when used from assign_by_spills,
> can be non-transitive, indicating A < B < C < A if both A and C satisfy
> !bitmap_bit_p (_reload_pseudos, rAC), but B does not.
>
> This function was originally a proper comparator, and the problematic
> clause was added to fix PR 57878:
> https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html
>
> That the comparator is invalid implies that that PR, if it still exists,
> can reappear (but probably under more complicated circumstances).
>
> This looks like a sensitive area, so disabling checking is the only
> obvious approach.

May make sense to add PR rtl-optimization/68988 annotation to changelog.

> * lra-assigns.c (reload_pseudo_compare_func): Add a FIXME.
> (assign_by_spills): Use non-checking qsort.
> ---
>  gcc/lra-assigns.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
> index 2aadeef..a67d1a6 100644
> --- a/gcc/lra-assigns.c
> +++ b/gcc/lra-assigns.c
> @@ -217,6 +217,7 @@ reload_pseudo_compare_func (const void *v1p, const void 
> *v2p)
>/* The code below executes rarely as nregs == 1 in most cases.
>  So we should not worry about using faster data structures to
>  check reload pseudos.  */
> +  /* FIXME this makes comparator non-transitive and thus invalid.  */
>&& ! bitmap_bit_p (_reload_pseudos, r1)
>&& ! bitmap_bit_p (_reload_pseudos, r2))
>  return diff;
> @@ -1384,7 +1385,7 @@ assign_by_spills (void)
>bitmap_ior_into (_reload_pseudos, _optional_reload_pseudos);
>for (iter = 0; iter <= 1; iter++)
>  {
> -  qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
> +  qsort_nochk (sorted_pseudos, n, sizeof (int), 
> reload_pseudo_compare_func);
>nfails = 0;
>for (i = 0; i < n; i++)
> {
> --
> 1.8.3.1
>

[PATCH 4/6] lra-assigns.c: give up on qsort checking in assign_by_spills

[Alexander Monakov]

The reload_pseudo_compare_func comparator, when used from assign_by_spills,
can be non-transitive, indicating A < B < C < A if both A and C satisfy
!bitmap_bit_p (_reload_pseudos, rAC), but B does not.

This function was originally a proper comparator, and the problematic
clause was added to fix PR 57878:
https://gcc.gnu.org/ml/gcc-patches/2013-07/msg00732.html

That the comparator is invalid implies that that PR, if it still exists,
can reappear (but probably under more complicated circumstances).

This looks like a sensitive area, so disabling checking is the only
obvious approach.

* lra-assigns.c (reload_pseudo_compare_func): Add a FIXME.
(assign_by_spills): Use non-checking qsort.
---
 gcc/lra-assigns.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/gcc/lra-assigns.c b/gcc/lra-assigns.c
index 2aadeef..a67d1a6 100644
--- a/gcc/lra-assigns.c
+++ b/gcc/lra-assigns.c
@@ -217,6 +217,7 @@ reload_pseudo_compare_func (const void *v1p, const void 
*v2p)
   /* The code below executes rarely as nregs == 1 in most cases.
 So we should not worry about using faster data structures to
 check reload pseudos.  */
+  /* FIXME this makes comparator non-transitive and thus invalid.  */
   && ! bitmap_bit_p (_reload_pseudos, r1)
   && ! bitmap_bit_p (_reload_pseudos, r2))
 return diff;
@@ -1384,7 +1385,7 @@ assign_by_spills (void)
   bitmap_ior_into (_reload_pseudos, _optional_reload_pseudos);
   for (iter = 0; iter <= 1; iter++)
 {
-  qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
+  qsort_nochk (sorted_pseudos, n, sizeof (int), 
reload_pseudo_compare_func);
   nfails = 0;
   for (i = 0; i < n; i++)
{
-- 
1.8.3.1