[Bug rtl-optimization/102147] New: IRA dependent on 32-bit vs 64-bit register size

[Bug rtl-optimization/102147] New: IRA dependent on 32-bit vs 64-bit register size

[dje at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

            Bug ID: 102147
           Summary: IRA dependent on 32-bit vs 64-bit register size
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dje at gcc dot gnu.org
  Target Milestone: ---

IRA heuristics chooses different data structure encodings based on the register
size, and this produces different register allocation results.

This was discovered by a GCC bootstrap comparison failure of tree-vect-slp.c
when using a 32 bit compiler to bootstrap a 64 bit compiler.

A difference occurs in ira-conflicts.c: build_object_conflicts(), for
the same object with the same properties (i.e., min, max and px are the same),
the function ira_conflict_vector_profitable_p() will return 1 by
stage1-gcc and 0 by stage2-gcc.

stage1-gcc: build_object_conflict obj140(a140) px=4 min=3 max=139
profitable_p=1
stage2-gcc: build_object_conflict obj140(a140) px=4 min=3 max=139
profitable_p=0

That's because the size of ira_object_t being a pointer is different
in stage1-gcc (which is 32bit) and stage2-gcc (which is 64bit).

My colleagues at ATOS and I aren't completely certain how this difference
causes different conflict / allocation behavior because it seems that it should
be an
optimization.

Should the data structure choice / algorithm choice depend on pointer size? 
Are the two algorithms supposed to generate the same results?

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit register size

[dje at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

David Edelsohn <dje at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
                 CC|                            |bergner at gcc dot gnu.org,
                   |                            |vmakarov at gcc dot gnu.org
   Last reconfirmed|                            |2021-08-31

--- Comment #1 from David Edelsohn <dje at gcc dot gnu.org> ---
Confirmed.

This was discovered when bootstrapping 64 bit GCC on AIX using 32 bit GCC.

It seems that this should be reproduceable on any system and architecture by
overriding the conflicts data structure encoding choice.

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit register size

[dje at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #2 from David Edelsohn <dje at gcc dot gnu.org> ---
Created attachment 51389
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=51389&action=edit
Pre-processed subset of tree-vect-slp.c

$ gcc -O2 -fno-exceptions

produces different conflicts and register allocation choices if GCC (IRA) is
built as 32 bit vs 64 bit compiler.

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Well, ira_conflict_vector_profitable_p is dependent on sizeof (ira_object_t)
but it's a decision about the representation of conflicts.  The question is now
whether at any point processing of the two representations can yield different
answers.  That might happen if we somewhere iterate over conflicts?

I suppose the simplest fix for the actual bootstrap issue is to make
ira_conflict_vector_profitable_p independent of sizeof (ira_object_t)
and sizeof (IRA_INT_TYPE) and simplify

  return (2 * sizeof (ira_object_t) * (num + 1)
          < 3 * nw * sizeof (IRA_INT_TYPE));

for example to

  return (2 * (num + 1) < 3 * nw);

(note 'nw' is also rounded up to IRA_INT_BITS).

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
btw, using bootstrap4 might be another solution.

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[dje at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #5 from David Edelsohn <dje at gcc dot gnu.org> ---
Vlad privately commented: "I suspect order of processing conflicts might depend
on their representation."

The two representations may produce different results and the heuristics to
choose the representation depend on the pointer size.

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[vmakarov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #6 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
(In reply to David Edelsohn from comment #5)
> Vlad privately commented: "I suspect order of processing conflicts might
> depend on their representation."
> 
> The two representations may produce different results and the heuristics to
> choose the representation depend on the pointer size.

Yes.

I'll be working on the PR.  It is an interesting type of problem.  I think GCC
output should be the same independently what type of compiler (64-bit or 32-bit
one) we use for building GCC.

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[vmakarov at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #7 from Vladimir Makarov <vmakarov at gcc dot gnu.org> ---
I've been thinking about ways to fix this problem but only come to the
following patch.  The patch results in working mostly the same for 64-bit
targets and different for 32-bit targets. In any case the profitability is only
an estimation so I think the patch is ok.  Avoiding 4 stage bootstrap is more
important than a bit slower RA on 32-bit targets (which is questionable) on few
border cases.

I am going to commit the patch this Friday.

--- a/gcc/ira-build.c
+++ b/gcc/ira-build.c
@@ -629,7 +629,7 @@ ior_hard_reg_conflicts (ira_allocno_t a, const_hard_reg_set
set)
 bool
 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
 {
-  int nw;
+  int nbytes;
   int max = OBJECT_MAX (obj);
   int min = OBJECT_MIN (obj);

@@ -638,9 +638,14 @@ ira_conflict_vector_profitable_p (ira_object_t obj, int
num)
        in allocation.  */
     return false;

-  nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
-  return (2 * sizeof (ira_object_t) * (num + 1)
-         < 3 * nw * sizeof (IRA_INT_TYPE));
+  nbytes = (max - min) / 8 + 1;
+  STATIC_ASSERT (sizeof (ira_object_t) <= 8);
+  /* Don't use sizeof (ira_object_t), use constant 8.  Size of ira_object_t (a
+     pointer) is different on 32-bit and 64-bit targets.  Usage sizeof
+     (ira_object_t) can result in different code generation by GCC built as
32-
+     and 64-bit program.  In any case the profitability is just an estimation
+     and border cases are rare.  */
+  return (2 * 8 /* sizeof (ira_object_t) */ * (num + 1) < 3 * nbytes);
 }

 /* Allocates and initialize the conflict vector of OBJ for NUM

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #8 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Vladimir Makarov <vmakarov@gcc.gnu.org>:

https://gcc.gnu.org/g:51ca05031959d3accffe873e87d4bc4fbd22e9e9

commit r12-3881-g51ca05031959d3accffe873e87d4bc4fbd22e9e9
Author: Vladimir N. Makarov <vmakarov@redhat.com>
Date:   Fri Sep 24 10:06:45 2021 -0400

    Make profitability calculation of RA conflict presentations independent of
host compiler type sizes. [PR102147]

    gcc/ChangeLog:

    2021-09-24  Vladimir Makarov  <vmakarov@redhat.com>

            PR rtl-optimization/102147
            * ira-build.c (ira_conflict_vector_profitable_p): Make
            profitability calculation independent of host compiler pointer and
            IRA_INT_BITS sizes.

[Bug rtl-optimization/102147] IRA dependent on 32-bit vs 64-bit pointer size

[bergner at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102147

--- Comment #9 from Peter Bergner <bergner at gcc dot gnu.org> ---
(In reply to CVS Commits from comment #8)
> The master branch has been updated by Vladimir Makarov
> <vmakarov@gcc.gnu.org>:
> 
> https://gcc.gnu.org/g:51ca05031959d3accffe873e87d4bc4fbd22e9e9
> 
> commit r12-3881-g51ca05031959d3accffe873e87d4bc4fbd22e9e9
> Author: Vladimir N. Makarov <vmakarov@redhat.com>
> Date:   Fri Sep 24 10:06:45 2021 -0400
> 
>     Make profitability calculation of RA conflict presentations independent
> of host compiler type sizes. [PR102147]
>     
>     gcc/ChangeLog:
>     
>     2021-09-24  Vladimir Makarov  <vmakarov@redhat.com>
>     
>             PR rtl-optimization/102147
>             * ira-build.c (ira_conflict_vector_profitable_p): Make
>             profitability calculation independent of host compiler pointer
> and
>             IRA_INT_BITS sizes.

Can we mark this as RESOLVED / FIXED now?