Understanding tree_swap_operands_p wrt SSA name versions

Understanding tree_swap_operands_p wrt SSA name versions

[Michael Ploujnikov]

[-- Attachment #1.1: Type: text/plain, Size: 1167 bytes --]

Hi everyone,

(I hope this is the right place to ask, if not my apologies; please
point me in the right direction)

I'm trying to get a better understanding of the following part in
tree_swap_operands_p():

  /* It is preferable to swap two SSA_NAME to ensure a canonical form
     for commutative and comparison operators.  Ensuring a canonical
     form allows the optimizers to find additional redundancies without
     having to explicitly check for both orderings.  */
  if (TREE_CODE (arg0) == SSA_NAME
      && TREE_CODE (arg1) == SSA_NAME
      && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
    return 1;

My questions in no particular order: It looks like this was added in
2004. I couldn't find any info other than what's in the corresponding
commit (cc0bdf913) so I'm wondering if the canonical form/order still
relevant/needed today? Does the ordering have to be done based on the
name versions specifically? Or can it be based on something more
intrinsic to the input source code rather than a GCC internal value, eg:
would alphabetic sort order of the variable names be a reasonable
replacement?

Thanks,
- Michael


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Jeff Law]

On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
> Hi everyone,
> 
> (I hope this is the right place to ask, if not my apologies; please
> point me in the right direction)
> 
> I'm trying to get a better understanding of the following part in
> tree_swap_operands_p():
> 
>   /* It is preferable to swap two SSA_NAME to ensure a canonical form
>      for commutative and comparison operators.  Ensuring a canonical
>      form allows the optimizers to find additional redundancies without
>      having to explicitly check for both orderings.  */
>   if (TREE_CODE (arg0) == SSA_NAME
>       && TREE_CODE (arg1) == SSA_NAME
>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>     return 1;
> 
> My questions in no particular order: It looks like this was added in
> 2004. I couldn't find any info other than what's in the corresponding
> commit (cc0bdf913) so I'm wondering if the canonical form/order still
> relevant/needed today? Does the ordering have to be done based on the
> name versions specifically? Or can it be based on something more
> intrinsic to the input source code rather than a GCC internal value, eg:
> would alphabetic sort order of the variable names be a reasonable
> replacement?
Canonicalization is still important and useful.

However, canonicalizing on SSA_NAMEs is problematical due to the way we
recycle nodes and re-pack them.

I think defining additional rules for canonicalization prior to using
SSA_NAME_VERSION as the fallback would be looked upon favorably.

Note however, that many of the _DECL nodes referenced by SSA_NAMEs are
temporaries generated by the compiler and do not correspond to any
declared/defined object in the original source.  So you'll still need
the SSA_NAME_VERSION (or something as stable or better) canonicalization
to handle those cases.

Jeff

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Richard Biener]

On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>
> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
> > Hi everyone,
> >
> > (I hope this is the right place to ask, if not my apologies; please
> > point me in the right direction)
> >
> > I'm trying to get a better understanding of the following part in
> > tree_swap_operands_p():
> >
> >   /* It is preferable to swap two SSA_NAME to ensure a canonical form
> >      for commutative and comparison operators.  Ensuring a canonical
> >      form allows the optimizers to find additional redundancies without
> >      having to explicitly check for both orderings.  */
> >   if (TREE_CODE (arg0) == SSA_NAME
> >       && TREE_CODE (arg1) == SSA_NAME
> >       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
> >     return 1;
> >
> > My questions in no particular order: It looks like this was added in
> > 2004. I couldn't find any info other than what's in the corresponding
> > commit (cc0bdf913) so I'm wondering if the canonical form/order still
> > relevant/needed today? Does the ordering have to be done based on the
> > name versions specifically? Or can it be based on something more
> > intrinsic to the input source code rather than a GCC internal value, eg:
> > would alphabetic sort order of the variable names be a reasonable
> > replacement?
> Canonicalization is still important and useful.

Indeed.

> However, canonicalizing on SSA_NAMEs is problematical due to the way we
> recycle nodes and re-pack them.

In the past we made sure to not disrupt order - hopefully that didn't change
so the re-packing shoudln't invaidate previous canonicalization:

static void
release_free_names_and_compact_live_names (function *fun)
{
...
  /* And compact the SSA number space.  We make sure to not change the
     relative order of SSA versions.  */
  for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
    {


> I think defining additional rules for canonicalization prior to using
> SSA_NAME_VERSION as the fallback would be looked upon favorably.

I don't see a good reason to do that, it will be harder to spot canonicalization
issues and it will take extra compile-time.

> Note however, that many of the _DECL nodes referenced by SSA_NAMEs are
> temporaries generated by the compiler and do not correspond to any
> declared/defined object in the original source.  So you'll still need
> the SSA_NAME_VERSION (or something as stable or better) canonicalization
> to handle those cases.

And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE names).

Richard.

> Jeff

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Michael Ploujnikov]

[-- Attachment #1.1: Type: text/plain, Size: 3728 bytes --]

On 2018-06-20 04:23 AM, Richard Biener wrote:
> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>>
>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
>>> Hi everyone,
>>>
>>> (I hope this is the right place to ask, if not my apologies; please
>>> point me in the right direction)
>>>
>>> I'm trying to get a better understanding of the following part in
>>> tree_swap_operands_p():
>>>
>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical form
>>>      for commutative and comparison operators.  Ensuring a canonical
>>>      form allows the optimizers to find additional redundancies without
>>>      having to explicitly check for both orderings.  */
>>>   if (TREE_CODE (arg0) == SSA_NAME
>>>       && TREE_CODE (arg1) == SSA_NAME
>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>>>     return 1;
>>>
>>> My questions in no particular order: It looks like this was added in
>>> 2004. I couldn't find any info other than what's in the corresponding
>>> commit (cc0bdf913) so I'm wondering if the canonical form/order still
>>> relevant/needed today? Does the ordering have to be done based on the
>>> name versions specifically? Or can it be based on something more
>>> intrinsic to the input source code rather than a GCC internal value, eg:
>>> would alphabetic sort order of the variable names be a reasonable
>>> replacement?
>> Canonicalization is still important and useful.
> 
> Indeed.
> 
>> However, canonicalizing on SSA_NAMEs is problematical due to the way we
>> recycle nodes and re-pack them.
> 
> In the past we made sure to not disrupt order - hopefully that didn't change
> so the re-packing shoudln't invaidate previous canonicalization:
> 
> static void
> release_free_names_and_compact_live_names (function *fun)
> {
> ...
>   /* And compact the SSA number space.  We make sure to not change the
>      relative order of SSA versions.  */
>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
>     {
> 
> 
>> I think defining additional rules for canonicalization prior to using
>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
> 
> I don't see a good reason to do that, it will be harder to spot canonicalization
> issues and it will take extra compile-time.
> 
>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs are
>> temporaries generated by the compiler and do not correspond to any
>> declared/defined object in the original source.  So you'll still need
>> the SSA_NAME_VERSION (or something as stable or better) canonicalization
>> to handle those cases.
> 
> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE names).
> 
> Richard.
> 
>> Jeff

After a bit more digging I found that insert_phi_nodes inserts PHIs in
the order of UIDs, which indirectly affects the order of vars in
old_ssa_names, which in turn affects the order in which make_ssa_name_fn
is called to pick SSA versions from FREE_SSANAMES so in the end
ordering by SSA_NAME_VERSION's is more or less equivalent to ordering by
UIDs. I'm trying to figure out if there's a way to avoid depending on
UIDs being ordered in a certain way. So if tree_swap_operands_p stays
the same I'm wondering if there's some other info available at the point
of insert_phi_nodes that would be a good replacement for UID. From my
very limited experience with a very small source input, and if I
understand things correctly, all of the var_infos have a var which is
DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
general case? I don't fully understand what are all the things that
insert_phi_nodes iterates over.

- Michael


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Richard Biener]

On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
>On 2018-06-20 04:23 AM, Richard Biener wrote:
>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>>>
>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
>>>> Hi everyone,
>>>>
>>>> (I hope this is the right place to ask, if not my apologies; please
>>>> point me in the right direction)
>>>>
>>>> I'm trying to get a better understanding of the following part in
>>>> tree_swap_operands_p():
>>>>
>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
>form
>>>>      for commutative and comparison operators.  Ensuring a
>canonical
>>>>      form allows the optimizers to find additional redundancies
>without
>>>>      having to explicitly check for both orderings.  */
>>>>   if (TREE_CODE (arg0) == SSA_NAME
>>>>       && TREE_CODE (arg1) == SSA_NAME
>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>>>>     return 1;
>>>>
>>>> My questions in no particular order: It looks like this was added
>in
>>>> 2004. I couldn't find any info other than what's in the
>corresponding
>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
>still
>>>> relevant/needed today? Does the ordering have to be done based on
>the
>>>> name versions specifically? Or can it be based on something more
>>>> intrinsic to the input source code rather than a GCC internal
>value, eg:
>>>> would alphabetic sort order of the variable names be a reasonable
>>>> replacement?
>>> Canonicalization is still important and useful.
>> 
>> Indeed.
>> 
>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
>we
>>> recycle nodes and re-pack them.
>> 
>> In the past we made sure to not disrupt order - hopefully that didn't
>change
>> so the re-packing shoudln't invaidate previous canonicalization:
>> 
>> static void
>> release_free_names_and_compact_live_names (function *fun)
>> {
>> ...
>>   /* And compact the SSA number space.  We make sure to not change
>the
>>      relative order of SSA versions.  */
>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
>>     {
>> 
>> 
>>> I think defining additional rules for canonicalization prior to
>using
>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
>> 
>> I don't see a good reason to do that, it will be harder to spot
>canonicalization
>> issues and it will take extra compile-time.
>> 
>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
>are
>>> temporaries generated by the compiler and do not correspond to any
>>> declared/defined object in the original source.  So you'll still
>need
>>> the SSA_NAME_VERSION (or something as stable or better)
>canonicalization
>>> to handle those cases.
>> 
>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
>names).
>> 
>> Richard.
>> 
>>> Jeff
>
>After a bit more digging I found that insert_phi_nodes inserts PHIs in
>the order of UIDs, which indirectly affects the order of vars in
>old_ssa_names, which in turn affects the order in which
>make_ssa_name_fn
>is called to pick SSA versions from FREE_SSANAMES so in the end
>ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
>by
>UIDs. I'm trying to figure out if there's a way to avoid depending on
>UIDs being ordered in a certain way. So if tree_swap_operands_p stays
>the same I'm wondering if there's some other info available at the
>point
>of insert_phi_nodes that would be a good replacement for UID. From my
>very limited experience with a very small source input, and if I
>understand things correctly, all of the var_infos have a var which is
>DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
>general case? I don't fully understand what are all the things that
>insert_phi_nodes iterates over.

Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation... 

Richard. 

>- Michael

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Michael Ploujnikov]

[-- Attachment #1.1: Type: text/plain, Size: 4950 bytes --]

On 2018-07-03 12:46 PM, Richard Biener wrote:
> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
>> On 2018-06-20 04:23 AM, Richard Biener wrote:
>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>>>>
>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
>>>>> Hi everyone,
>>>>>
>>>>> (I hope this is the right place to ask, if not my apologies; please
>>>>> point me in the right direction)
>>>>>
>>>>> I'm trying to get a better understanding of the following part in
>>>>> tree_swap_operands_p():
>>>>>
>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
>> form
>>>>>      for commutative and comparison operators.  Ensuring a
>> canonical
>>>>>      form allows the optimizers to find additional redundancies
>> without
>>>>>      having to explicitly check for both orderings.  */
>>>>>   if (TREE_CODE (arg0) == SSA_NAME
>>>>>       && TREE_CODE (arg1) == SSA_NAME
>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>>>>>     return 1;
>>>>>
>>>>> My questions in no particular order: It looks like this was added
>> in
>>>>> 2004. I couldn't find any info other than what's in the
>> corresponding
>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
>> still
>>>>> relevant/needed today? Does the ordering have to be done based on
>> the
>>>>> name versions specifically? Or can it be based on something more
>>>>> intrinsic to the input source code rather than a GCC internal
>> value, eg:
>>>>> would alphabetic sort order of the variable names be a reasonable
>>>>> replacement?
>>>> Canonicalization is still important and useful.
>>>
>>> Indeed.
>>>
>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
>> we
>>>> recycle nodes and re-pack them.
>>>
>>> In the past we made sure to not disrupt order - hopefully that didn't
>> change
>>> so the re-packing shoudln't invaidate previous canonicalization:
>>>
>>> static void
>>> release_free_names_and_compact_live_names (function *fun)
>>> {
>>> ...
>>>   /* And compact the SSA number space.  We make sure to not change
>> the
>>>      relative order of SSA versions.  */
>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
>>>     {
>>>
>>>
>>>> I think defining additional rules for canonicalization prior to
>> using
>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
>>>
>>> I don't see a good reason to do that, it will be harder to spot
>> canonicalization
>>> issues and it will take extra compile-time.
>>>
>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
>> are
>>>> temporaries generated by the compiler and do not correspond to any
>>>> declared/defined object in the original source.  So you'll still
>> need
>>>> the SSA_NAME_VERSION (or something as stable or better)
>> canonicalization
>>>> to handle those cases.
>>>
>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
>> names).
>>>
>>> Richard.
>>>
>>>> Jeff
>>
>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
>> the order of UIDs, which indirectly affects the order of vars in
>> old_ssa_names, which in turn affects the order in which
>> make_ssa_name_fn
>> is called to pick SSA versions from FREE_SSANAMES so in the end
>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
>> by
>> UIDs. I'm trying to figure out if there's a way to avoid depending on
>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
>> the same I'm wondering if there's some other info available at the
>> point
>> of insert_phi_nodes that would be a good replacement for UID. From my
>> very limited experience with a very small source input, and if I
>> understand things correctly, all of the var_infos have a var which is
>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
>> general case? I don't fully understand what are all the things that
>> insert_phi_nodes iterates over.
> 
> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation... 
> 
> Richard. 
> 
>> - Michael
> 


Well, I'm working on a reduction of the number of changes seen with
binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
since current UID assignment is essentially tied to the order of things
in the input source code one function's changes can cascade to others
(even when they're unchanged). As you said UID dependence is quiet
pervasive, and although finding and improving individual cases (such as
tree_swap_operands_p) won't make it perfect, I think it will be a step
in the positive direction.

Also, I have some ideas for a UID assignment scheme that might improve
things overall, that I'll try to share after I get back from vacation.

- Michael


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Jeff Law]

On 07/03/2018 11:55 AM, Michael Ploujnikov wrote:
> On 2018-07-03 12:46 PM, Richard Biener wrote:
>> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
>>> On 2018-06-20 04:23 AM, Richard Biener wrote:
>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>>>>>
>>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
>>>>>> Hi everyone,
>>>>>>
>>>>>> (I hope this is the right place to ask, if not my apologies; please
>>>>>> point me in the right direction)
>>>>>>
>>>>>> I'm trying to get a better understanding of the following part in
>>>>>> tree_swap_operands_p():
>>>>>>
>>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
>>> form
>>>>>>      for commutative and comparison operators.  Ensuring a
>>> canonical
>>>>>>      form allows the optimizers to find additional redundancies
>>> without
>>>>>>      having to explicitly check for both orderings.  */
>>>>>>   if (TREE_CODE (arg0) == SSA_NAME
>>>>>>       && TREE_CODE (arg1) == SSA_NAME
>>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>>>>>>     return 1;
>>>>>>
>>>>>> My questions in no particular order: It looks like this was added
>>> in
>>>>>> 2004. I couldn't find any info other than what's in the
>>> corresponding
>>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
>>> still
>>>>>> relevant/needed today? Does the ordering have to be done based on
>>> the
>>>>>> name versions specifically? Or can it be based on something more
>>>>>> intrinsic to the input source code rather than a GCC internal
>>> value, eg:
>>>>>> would alphabetic sort order of the variable names be a reasonable
>>>>>> replacement?
>>>>> Canonicalization is still important and useful.
>>>>
>>>> Indeed.
>>>>
>>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
>>> we
>>>>> recycle nodes and re-pack them.
>>>>
>>>> In the past we made sure to not disrupt order - hopefully that didn't
>>> change
>>>> so the re-packing shoudln't invaidate previous canonicalization:
>>>>
>>>> static void
>>>> release_free_names_and_compact_live_names (function *fun)
>>>> {
>>>> ...
>>>>   /* And compact the SSA number space.  We make sure to not change
>>> the
>>>>      relative order of SSA versions.  */
>>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
>>>>     {
>>>>
>>>>
>>>>> I think defining additional rules for canonicalization prior to
>>> using
>>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
>>>>
>>>> I don't see a good reason to do that, it will be harder to spot
>>> canonicalization
>>>> issues and it will take extra compile-time.
>>>>
>>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
>>> are
>>>>> temporaries generated by the compiler and do not correspond to any
>>>>> declared/defined object in the original source.  So you'll still
>>> need
>>>>> the SSA_NAME_VERSION (or something as stable or better)
>>> canonicalization
>>>>> to handle those cases.
>>>>
>>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
>>> names).
>>>>
>>>> Richard.
>>>>
>>>>> Jeff
>>>
>>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
>>> the order of UIDs, which indirectly affects the order of vars in
>>> old_ssa_names, which in turn affects the order in which
>>> make_ssa_name_fn
>>> is called to pick SSA versions from FREE_SSANAMES so in the end
>>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
>>> by
>>> UIDs. I'm trying to figure out if there's a way to avoid depending on
>>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
>>> the same I'm wondering if there's some other info available at the
>>> point
>>> of insert_phi_nodes that would be a good replacement for UID. From my
>>> very limited experience with a very small source input, and if I
>>> understand things correctly, all of the var_infos have a var which is
>>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
>>> general case? I don't fully understand what are all the things that
>>> insert_phi_nodes iterates over.
>>
>> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation... 
>>
>> Richard. 
>>
>>> - Michael
>>
> 
> 
> Well, I'm working on a reduction of the number of changes seen with
> binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
> since current UID assignment is essentially tied to the order of things
> in the input source code one function's changes can cascade to others
> (even when they're unchanged). As you said UID dependence is quiet
> pervasive, and although finding and improving individual cases (such as
> tree_swap_operands_p) won't make it perfect, I think it will be a step
> in the positive direction.
> 
> Also, I have some ideas for a UID assignment scheme that might improve
> things overall, that I'll try to share after I get back from vacation.
I'm still not sure what the point is.  GIven the same input, you're
going to get the same output.  Using UIDs is deterministic.  If the
input changes, then, yea, sure the output is going to change, but that's
got to be expected.

Jeff
> 
> - Michael
> 

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Richard Biener]

On Tue, Jul 3, 2018 at 9:09 PM Jeff Law <law@redhat.com> wrote:
>
> On 07/03/2018 11:55 AM, Michael Ploujnikov wrote:
> > On 2018-07-03 12:46 PM, Richard Biener wrote:
> >> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
> >>> On 2018-06-20 04:23 AM, Richard Biener wrote:
> >>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
> >>>>>
> >>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
> >>>>>> Hi everyone,
> >>>>>>
> >>>>>> (I hope this is the right place to ask, if not my apologies; please
> >>>>>> point me in the right direction)
> >>>>>>
> >>>>>> I'm trying to get a better understanding of the following part in
> >>>>>> tree_swap_operands_p():
> >>>>>>
> >>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
> >>> form
> >>>>>>      for commutative and comparison operators.  Ensuring a
> >>> canonical
> >>>>>>      form allows the optimizers to find additional redundancies
> >>> without
> >>>>>>      having to explicitly check for both orderings.  */
> >>>>>>   if (TREE_CODE (arg0) == SSA_NAME
> >>>>>>       && TREE_CODE (arg1) == SSA_NAME
> >>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
> >>>>>>     return 1;
> >>>>>>
> >>>>>> My questions in no particular order: It looks like this was added
> >>> in
> >>>>>> 2004. I couldn't find any info other than what's in the
> >>> corresponding
> >>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
> >>> still
> >>>>>> relevant/needed today? Does the ordering have to be done based on
> >>> the
> >>>>>> name versions specifically? Or can it be based on something more
> >>>>>> intrinsic to the input source code rather than a GCC internal
> >>> value, eg:
> >>>>>> would alphabetic sort order of the variable names be a reasonable
> >>>>>> replacement?
> >>>>> Canonicalization is still important and useful.
> >>>>
> >>>> Indeed.
> >>>>
> >>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
> >>> we
> >>>>> recycle nodes and re-pack them.
> >>>>
> >>>> In the past we made sure to not disrupt order - hopefully that didn't
> >>> change
> >>>> so the re-packing shoudln't invaidate previous canonicalization:
> >>>>
> >>>> static void
> >>>> release_free_names_and_compact_live_names (function *fun)
> >>>> {
> >>>> ...
> >>>>   /* And compact the SSA number space.  We make sure to not change
> >>> the
> >>>>      relative order of SSA versions.  */
> >>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
> >>>>     {
> >>>>
> >>>>
> >>>>> I think defining additional rules for canonicalization prior to
> >>> using
> >>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
> >>>>
> >>>> I don't see a good reason to do that, it will be harder to spot
> >>> canonicalization
> >>>> issues and it will take extra compile-time.
> >>>>
> >>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
> >>> are
> >>>>> temporaries generated by the compiler and do not correspond to any
> >>>>> declared/defined object in the original source.  So you'll still
> >>> need
> >>>>> the SSA_NAME_VERSION (or something as stable or better)
> >>> canonicalization
> >>>>> to handle those cases.
> >>>>
> >>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
> >>> names).
> >>>>
> >>>> Richard.
> >>>>
> >>>>> Jeff
> >>>
> >>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
> >>> the order of UIDs, which indirectly affects the order of vars in
> >>> old_ssa_names, which in turn affects the order in which
> >>> make_ssa_name_fn
> >>> is called to pick SSA versions from FREE_SSANAMES so in the end
> >>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
> >>> by
> >>> UIDs. I'm trying to figure out if there's a way to avoid depending on
> >>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
> >>> the same I'm wondering if there's some other info available at the
> >>> point
> >>> of insert_phi_nodes that would be a good replacement for UID. From my
> >>> very limited experience with a very small source input, and if I
> >>> understand things correctly, all of the var_infos have a var which is
> >>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
> >>> general case? I don't fully understand what are all the things that
> >>> insert_phi_nodes iterates over.
> >>
> >> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation...
> >>
> >> Richard.
> >>
> >>> - Michael
> >>
> >
> >
> > Well, I'm working on a reduction of the number of changes seen with
> > binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
> > since current UID assignment is essentially tied to the order of things
> > in the input source code one function's changes can cascade to others
> > (even when they're unchanged). As you said UID dependence is quiet
> > pervasive, and although finding and improving individual cases (such as
> > tree_swap_operands_p) won't make it perfect, I think it will be a step
> > in the positive direction.
> >
> > Also, I have some ideas for a UID assignment scheme that might improve
> > things overall, that I'll try to share after I get back from vacation.
> I'm still not sure what the point is.  GIven the same input, you're
> going to get the same output.  Using UIDs is deterministic.  If the
> input changes, then, yea, sure the output is going to change, but that's
> got to be expected.

Yeah, UIDs are likely not the correct handle on this.  You might get
"less" code generation changes when you change sources by
using -fno-toplevel-reorder.

I also remember that at one point I facilitated debugging / testcase
reduction by "rounding" UIDs up when starting to process a different
function.

But note that changes in absolute values of UIDs should not affect
code generation but only changes in their relative order.

SSA version assignment is different in that regard given we
avoid compressing the SSA version space (to facilitate debugging)
and instead re-allocate freed SSA names.

Richard.

> Jeff
> >
> > - Michael
> >
>

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Michael Ploujnikov]

[-- Attachment #1.1.1: Type: text/plain, Size: 8342 bytes --]

On 2018-07-04 04:52 AM, Richard Biener wrote:
> On Tue, Jul 3, 2018 at 9:09 PM Jeff Law <law@redhat.com> wrote:
>>
>> On 07/03/2018 11:55 AM, Michael Ploujnikov wrote:
>>> On 2018-07-03 12:46 PM, Richard Biener wrote:
>>>> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
>>>>> On 2018-06-20 04:23 AM, Richard Biener wrote:
>>>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>>>>>>>
>>>>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
>>>>>>>> Hi everyone,
>>>>>>>>
>>>>>>>> (I hope this is the right place to ask, if not my apologies; please
>>>>>>>> point me in the right direction)
>>>>>>>>
>>>>>>>> I'm trying to get a better understanding of the following part in
>>>>>>>> tree_swap_operands_p():
>>>>>>>>
>>>>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
>>>>> form
>>>>>>>>      for commutative and comparison operators.  Ensuring a
>>>>> canonical
>>>>>>>>      form allows the optimizers to find additional redundancies
>>>>> without
>>>>>>>>      having to explicitly check for both orderings.  */
>>>>>>>>   if (TREE_CODE (arg0) == SSA_NAME
>>>>>>>>       && TREE_CODE (arg1) == SSA_NAME
>>>>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>>>>>>>>     return 1;
>>>>>>>>
>>>>>>>> My questions in no particular order: It looks like this was added
>>>>> in
>>>>>>>> 2004. I couldn't find any info other than what's in the
>>>>> corresponding
>>>>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
>>>>> still
>>>>>>>> relevant/needed today? Does the ordering have to be done based on
>>>>> the
>>>>>>>> name versions specifically? Or can it be based on something more
>>>>>>>> intrinsic to the input source code rather than a GCC internal
>>>>> value, eg:
>>>>>>>> would alphabetic sort order of the variable names be a reasonable
>>>>>>>> replacement?
>>>>>>> Canonicalization is still important and useful.
>>>>>>
>>>>>> Indeed.
>>>>>>
>>>>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
>>>>> we
>>>>>>> recycle nodes and re-pack them.
>>>>>>
>>>>>> In the past we made sure to not disrupt order - hopefully that didn't
>>>>> change
>>>>>> so the re-packing shoudln't invaidate previous canonicalization:
>>>>>>
>>>>>> static void
>>>>>> release_free_names_and_compact_live_names (function *fun)
>>>>>> {
>>>>>> ...
>>>>>>   /* And compact the SSA number space.  We make sure to not change
>>>>> the
>>>>>>      relative order of SSA versions.  */
>>>>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
>>>>>>     {
>>>>>>
>>>>>>
>>>>>>> I think defining additional rules for canonicalization prior to
>>>>> using
>>>>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
>>>>>>
>>>>>> I don't see a good reason to do that, it will be harder to spot
>>>>> canonicalization
>>>>>> issues and it will take extra compile-time.
>>>>>>
>>>>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
>>>>> are
>>>>>>> temporaries generated by the compiler and do not correspond to any
>>>>>>> declared/defined object in the original source.  So you'll still
>>>>> need
>>>>>>> the SSA_NAME_VERSION (or something as stable or better)
>>>>> canonicalization
>>>>>>> to handle those cases.
>>>>>>
>>>>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
>>>>> names).
>>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> Jeff
>>>>>
>>>>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
>>>>> the order of UIDs, which indirectly affects the order of vars in
>>>>> old_ssa_names, which in turn affects the order in which
>>>>> make_ssa_name_fn
>>>>> is called to pick SSA versions from FREE_SSANAMES so in the end
>>>>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
>>>>> by
>>>>> UIDs. I'm trying to figure out if there's a way to avoid depending on
>>>>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
>>>>> the same I'm wondering if there's some other info available at the
>>>>> point
>>>>> of insert_phi_nodes that would be a good replacement for UID. From my
>>>>> very limited experience with a very small source input, and if I
>>>>> understand things correctly, all of the var_infos have a var which is
>>>>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
>>>>> general case? I don't fully understand what are all the things that
>>>>> insert_phi_nodes iterates over.
>>>>
>>>> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation...
>>>>
>>>> Richard.
>>>>
>>>>> - Michael
>>>>
>>>
>>>
>>> Well, I'm working on a reduction of the number of changes seen with
>>> binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
>>> since current UID assignment is essentially tied to the order of things
>>> in the input source code one function's changes can cascade to others
>>> (even when they're unchanged). As you said UID dependence is quiet
>>> pervasive, and although finding and improving individual cases (such as
>>> tree_swap_operands_p) won't make it perfect, I think it will be a step
>>> in the positive direction.
>>>
>>> Also, I have some ideas for a UID assignment scheme that might improve
>>> things overall, that I'll try to share after I get back from vacation.
>> I'm still not sure what the point is.  GIven the same input, you're
>> going to get the same output.  Using UIDs is deterministic.  If the
>> input changes, then, yea, sure the output is going to change, but that's
>> got to be expected.

Just wanted to say thanks for taking the time to answer my questions.

My main goal is to make each function's codegen as independent from one
another as possible. In other words, source changes to function A
shouldn't result in assembly changes for any of the other functions.
Example attached.

I have a prototype of a UID assignment scheme that handles a lot of
cases; I'm just waiting for legal approval before I can share the actual
code.

In the meantime I'm trying to understand the problem from the bottom up
and came across this tree_swap_operands_p case. I'm asking for your
expertise as to whether my conclusion (that PHI node UID order dictates
the SSA version assignment) is correct.

> Yeah, UIDs are likely not the correct handle on this.> You might get
> "less" code generation changes when you change sources by
> using -fno-toplevel-reorder.

Using no-toplevel-reorder didn't help, plus my situation is so general
that I can't control the enabled flags.

> 
> I also remember that at one point I facilitated debugging / testcase
> reduction by "rounding" UIDs up when starting to process a different
> function.

Is there a thread about this that you can point me to? I'm curious about
the details.


P.S. The attached sources can compiled with:
gcc-7.3.1 -fno-toplevel-reorder -nostdinc -isystem
/usr/lib/gcc/i686-redhat-linux/4.4.6/include
-I/builddir/build/BUILD/kernel-2.6.39/linux-2.6.39.i686/arch/x86/include
-Iarch/x86/include/generated -Iinclude -include
include/generated/autoconf.h -D__KERNEL__ -Wall -Wundef
-Wstrict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common
-Werror-implicit-function-declaration -Wno-format-security
-fno-delete-null-pointer-checks -Os -m32 -msoft-float -mregparm=3
-freg-struct-return -mpreferred-stack-boundary=2 -march=i686
-mtune=generic -maccumulate-outgoing-args -ffreestanding
-fstack-protector -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1
-DCONFIG_AS_CFI_SECTIONS=1 -pipe -Wno-sign-compare
-fno-asynchronous-unwind-tables -mno-sse -mno-mmx -mno-sse2 -mno-3dnow
-Wframe-larger-than=1024 -Wno-unused-but-set-variable
-fno-omit-frame-pointer -fno-optimize-sibling-calls -g
-femit-struct-debug-baseonly -pg -fno-inline-functions-called-once
-Wdeclaration-after-statement -Wno-pointer-sign -fno-strict-overflow
-fconserve-stack -DCC_HAVE_ASM_GOTO -ftest-coverage -ffunction-sections
-fdata-sections -D__DATE__="<{DATE...}>" -D__TIME__="<{TIME}>"
'-DKBUILD_STR(s)=#s' '-DKBUILD_BASENAME=KBUILD_STR(hrtimer)'
'-DKBUILD_MODNAME=KBUILD_STR(hrtimer)' -c -o /tmp/pre.o /tmp/pre.i


- Michael

[-- Attachment #1.1.2: pre.i --]
[-- Type: text/plain, Size: 1428 bytes --]

typedef signed long long s64;
union ktime {
 s64 tv64;
};
typedef union ktime ktime_t;

struct timer_list {
 unsigned long expires;
 void (*function)(unsigned long);
 unsigned long data;
 int slack;
};

extern unsigned long volatile __attribute__((section(".data"))) jiffies;
extern int mod_timer(struct timer_list *timer, unsigned long expires);
extern void timerfd_clock_was_set(void);
int on_each_cpu(void *func, void *info, int wait);

void clock_was_set(void)
{
 on_each_cpu(((void *)0), ((void *)0), 1);
 timerfd_clock_was_set();
}

enum {
 false = 0,
 true = 1
};
typedef _Bool bool;

enum debug_obj_state {
 ODEBUG_STATE_ACTIVE,
 ODEBUG_STATE_NOTAVAILABLE,
};
extern void warn_slowpath_null(const char *file, const int line);
int hrtimer_fixup_activate(void *addr, enum debug_obj_state state)
{
 switch (state) {

 case ODEBUG_STATE_NOTAVAILABLE:
  ({ static bool __warned; int __ret_warn_once = !!(1); if (__builtin_expect(!!(__ret_warn_once), 0)) if (({ int __ret_warn_on = !!(!__warned); if (__builtin_expect(!!(__ret_warn_on), 0)) warn_slowpath_null("kernel/hrtimer.c", 386); __builtin_expect(!!(__ret_warn_on), 0); })) __warned = true; __builtin_expect(!!(__ret_warn_once), 0); });
  return 0;

 case ODEBUG_STATE_ACTIVE:
  ({ int __ret_warn_on = !!(1); if (__builtin_expect(!!(__ret_warn_on), 0)) warn_slowpath_null("kernel/hrtimer.c", 390); __builtin_expect(!!(__ret_warn_on), 0); });

 default:
  return 0;
 }
}

[-- Attachment #1.1.3: post.i --]
[-- Type: text/plain, Size: 2080 bytes --]

typedef signed long long s64;
union ktime {
 s64 tv64;
};
typedef union ktime ktime_t;

struct timer_list {
 unsigned long expires;
 void (*function)(unsigned long);
 unsigned long data;
 int slack;
};

extern unsigned long volatile __attribute__((section(".data"))) jiffies;
extern int mod_timer(struct timer_list *timer, unsigned long expires);
extern void timerfd_clock_was_set(void);
int on_each_cpu(void *func, void *info, int wait);

extern void ktime_get_and_real_and_sleep_offset(ktime_t *monotonic,
      ktime_t *real_offset,
      ktime_t *sleep_offset);

static void do_clock_was_set(unsigned long data)
{
 on_each_cpu(((void *)0), ((void *)0), 1);
 timerfd_clock_was_set();
}

static struct timer_list clock_was_set_timer = { .expires = (0), .function = (do_clock_was_set), .data = (0), .slack = -1};

void clock_was_set(void)
{
 if (({ unsigned long _flags; do { ({ unsigned long __dummy; typeof(_flags) __dummy2; (void)(&__dummy == &__dummy2); 1; }); _flags = 1; } while (0); ({ ({ unsigned long __dummy; typeof(_flags) __dummy2; (void)(&__dummy == &__dummy2); 1; }); !(_flags & 0x00000200); }); }))
  mod_timer(&clock_was_set_timer, jiffies);
 else
  do_clock_was_set(0);
}

enum {
 false = 0,
 true = 1
};
typedef _Bool bool;

enum debug_obj_state {
 ODEBUG_STATE_ACTIVE,
 ODEBUG_STATE_NOTAVAILABLE,
};
extern void warn_slowpath_null(const char *file, const int line);
int hrtimer_fixup_activate(void *addr, enum debug_obj_state state)
{
 switch (state) {

 case ODEBUG_STATE_NOTAVAILABLE:
  ({ static bool __warned; int __ret_warn_once = !!(1); if (__builtin_expect(!!(__ret_warn_once), 0)) if (({ int __ret_warn_on = !!(!__warned); if (__builtin_expect(!!(__ret_warn_on), 0)) warn_slowpath_null("kernel/hrtimer.c", 386); __builtin_expect(!!(__ret_warn_on), 0); })) __warned = true; __builtin_expect(!!(__ret_warn_once), 0); });
  return 0;

 case ODEBUG_STATE_ACTIVE:
  ({ int __ret_warn_on = !!(1); if (__builtin_expect(!!(__ret_warn_on), 0)) warn_slowpath_null("kernel/hrtimer.c", 390); __builtin_expect(!!(__ret_warn_on), 0); });

 default:
  return 0;
 }
}

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Richard Biener]

On Mon, Jul 16, 2018 at 12:19 AM Michael Ploujnikov
<michael.ploujnikov@oracle.com> wrote:
>
> On 2018-07-04 04:52 AM, Richard Biener wrote:
> > On Tue, Jul 3, 2018 at 9:09 PM Jeff Law <law@redhat.com> wrote:
> >>
> >> On 07/03/2018 11:55 AM, Michael Ploujnikov wrote:
> >>> On 2018-07-03 12:46 PM, Richard Biener wrote:
> >>>> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
> >>>>> On 2018-06-20 04:23 AM, Richard Biener wrote:
> >>>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
> >>>>>>>
> >>>>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
> >>>>>>>> Hi everyone,
> >>>>>>>>
> >>>>>>>> (I hope this is the right place to ask, if not my apologies; please
> >>>>>>>> point me in the right direction)
> >>>>>>>>
> >>>>>>>> I'm trying to get a better understanding of the following part in
> >>>>>>>> tree_swap_operands_p():
> >>>>>>>>
> >>>>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
> >>>>> form
> >>>>>>>>      for commutative and comparison operators.  Ensuring a
> >>>>> canonical
> >>>>>>>>      form allows the optimizers to find additional redundancies
> >>>>> without
> >>>>>>>>      having to explicitly check for both orderings.  */
> >>>>>>>>   if (TREE_CODE (arg0) == SSA_NAME
> >>>>>>>>       && TREE_CODE (arg1) == SSA_NAME
> >>>>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
> >>>>>>>>     return 1;
> >>>>>>>>
> >>>>>>>> My questions in no particular order: It looks like this was added
> >>>>> in
> >>>>>>>> 2004. I couldn't find any info other than what's in the
> >>>>> corresponding
> >>>>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
> >>>>> still
> >>>>>>>> relevant/needed today? Does the ordering have to be done based on
> >>>>> the
> >>>>>>>> name versions specifically? Or can it be based on something more
> >>>>>>>> intrinsic to the input source code rather than a GCC internal
> >>>>> value, eg:
> >>>>>>>> would alphabetic sort order of the variable names be a reasonable
> >>>>>>>> replacement?
> >>>>>>> Canonicalization is still important and useful.
> >>>>>>
> >>>>>> Indeed.
> >>>>>>
> >>>>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
> >>>>> we
> >>>>>>> recycle nodes and re-pack them.
> >>>>>>
> >>>>>> In the past we made sure to not disrupt order - hopefully that didn't
> >>>>> change
> >>>>>> so the re-packing shoudln't invaidate previous canonicalization:
> >>>>>>
> >>>>>> static void
> >>>>>> release_free_names_and_compact_live_names (function *fun)
> >>>>>> {
> >>>>>> ...
> >>>>>>   /* And compact the SSA number space.  We make sure to not change
> >>>>> the
> >>>>>>      relative order of SSA versions.  */
> >>>>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
> >>>>>>     {
> >>>>>>
> >>>>>>
> >>>>>>> I think defining additional rules for canonicalization prior to
> >>>>> using
> >>>>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
> >>>>>>
> >>>>>> I don't see a good reason to do that, it will be harder to spot
> >>>>> canonicalization
> >>>>>> issues and it will take extra compile-time.
> >>>>>>
> >>>>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
> >>>>> are
> >>>>>>> temporaries generated by the compiler and do not correspond to any
> >>>>>>> declared/defined object in the original source.  So you'll still
> >>>>> need
> >>>>>>> the SSA_NAME_VERSION (or something as stable or better)
> >>>>> canonicalization
> >>>>>>> to handle those cases.
> >>>>>>
> >>>>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
> >>>>> names).
> >>>>>>
> >>>>>> Richard.
> >>>>>>
> >>>>>>> Jeff
> >>>>>
> >>>>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
> >>>>> the order of UIDs, which indirectly affects the order of vars in
> >>>>> old_ssa_names, which in turn affects the order in which
> >>>>> make_ssa_name_fn
> >>>>> is called to pick SSA versions from FREE_SSANAMES so in the end
> >>>>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
> >>>>> by
> >>>>> UIDs. I'm trying to figure out if there's a way to avoid depending on
> >>>>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
> >>>>> the same I'm wondering if there's some other info available at the
> >>>>> point
> >>>>> of insert_phi_nodes that would be a good replacement for UID. From my
> >>>>> very limited experience with a very small source input, and if I
> >>>>> understand things correctly, all of the var_infos have a var which is
> >>>>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
> >>>>> general case? I don't fully understand what are all the things that
> >>>>> insert_phi_nodes iterates over.
> >>>>
> >>>> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation...
> >>>>
> >>>> Richard.
> >>>>
> >>>>> - Michael
> >>>>
> >>>
> >>>
> >>> Well, I'm working on a reduction of the number of changes seen with
> >>> binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
> >>> since current UID assignment is essentially tied to the order of things
> >>> in the input source code one function's changes can cascade to others
> >>> (even when they're unchanged). As you said UID dependence is quiet
> >>> pervasive, and although finding and improving individual cases (such as
> >>> tree_swap_operands_p) won't make it perfect, I think it will be a step
> >>> in the positive direction.
> >>>
> >>> Also, I have some ideas for a UID assignment scheme that might improve
> >>> things overall, that I'll try to share after I get back from vacation.
> >> I'm still not sure what the point is.  GIven the same input, you're
> >> going to get the same output.  Using UIDs is deterministic.  If the
> >> input changes, then, yea, sure the output is going to change, but that's
> >> got to be expected.
>
> Just wanted to say thanks for taking the time to answer my questions.
>
> My main goal is to make each function's codegen as independent from one
> another as possible. In other words, source changes to function A
> shouldn't result in assembly changes for any of the other functions.

I see.  The main issue is that we "work" on functions multiple times
and intermediate work on other functions can influence code-generation
via IPA mechanisms.  Assigning UIDs should _not_ have an effect
as long as the order of assignment for the function itself doesn't change.

>
> Example attached.
>
> I have a prototype of a UID assignment scheme that handles a lot of
> cases; I'm just waiting for legal approval before I can share the actual
> code.
>
> In the meantime I'm trying to understand the problem from the bottom up
> and came across this tree_swap_operands_p case. I'm asking for your
> expertise as to whether my conclusion (that PHI node UID order dictates
> the SSA version assignment) is correct.

Well, kind-of.  We do

  auto_vec<var_info *> vars (var_infos->elements ());
  FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
    if (info->info.need_phi_state != NEED_PHI_STATE_NO)
      vars.quick_push (info);

  /* Do two stages to avoid code generation differences for UID
     differences but no UID ordering differences.  */
  vars.qsort (insert_phi_nodes_compare_var_infos);

which means we make sure to process PHI insertion in UID _order_
to avoid code-generation differences when another function gets UIDs
allocated.  The actual assignment of UIDs should happen by the
frontend or at gimplification time which happens in-order.

But PHIs do not get UIDs, their underlying variables do.

> > Yeah, UIDs are likely not the correct handle on this.> You might get
> > "less" code generation changes when you change sources by
> > using -fno-toplevel-reorder.
>
> Using no-toplevel-reorder didn't help, plus my situation is so general
> that I can't control the enabled flags.
>
> >
> > I also remember that at one point I facilitated debugging / testcase
> > reduction by "rounding" UIDs up when starting to process a different
> > function.
>
> Is there a thread about this that you can point me to? I'm curious about
> the details.

ISTR I wanted to minimize differences in -uid dumps so I basically
rouded up the last assigned uid at certain points.

Richard.

>
> P.S. The attached sources can compiled with:
> gcc-7.3.1 -fno-toplevel-reorder -nostdinc -isystem
> /usr/lib/gcc/i686-redhat-linux/4.4.6/include
> -I/builddir/build/BUILD/kernel-2.6.39/linux-2.6.39.i686/arch/x86/include
> -Iarch/x86/include/generated -Iinclude -include
> include/generated/autoconf.h -D__KERNEL__ -Wall -Wundef
> -Wstrict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common
> -Werror-implicit-function-declaration -Wno-format-security
> -fno-delete-null-pointer-checks -Os -m32 -msoft-float -mregparm=3
> -freg-struct-return -mpreferred-stack-boundary=2 -march=i686
> -mtune=generic -maccumulate-outgoing-args -ffreestanding
> -fstack-protector -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1
> -DCONFIG_AS_CFI_SECTIONS=1 -pipe -Wno-sign-compare
> -fno-asynchronous-unwind-tables -mno-sse -mno-mmx -mno-sse2 -mno-3dnow
> -Wframe-larger-than=1024 -Wno-unused-but-set-variable
> -fno-omit-frame-pointer -fno-optimize-sibling-calls -g
> -femit-struct-debug-baseonly -pg -fno-inline-functions-called-once
> -Wdeclaration-after-statement -Wno-pointer-sign -fno-strict-overflow
> -fconserve-stack -DCC_HAVE_ASM_GOTO -ftest-coverage -ffunction-sections
> -fdata-sections -D__DATE__="<{DATE...}>" -D__TIME__="<{TIME}>"
> '-DKBUILD_STR(s)=#s' '-DKBUILD_BASENAME=KBUILD_STR(hrtimer)'
> '-DKBUILD_MODNAME=KBUILD_STR(hrtimer)' -c -o /tmp/pre.o /tmp/pre.i
>
>
> - Michael

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Michael Ploujnikov]

[-- Attachment #1.1: Type: text/plain, Size: 11174 bytes --]

On 2018-07-16 04:30 AM, Richard Biener wrote:
> On Mon, Jul 16, 2018 at 12:19 AM Michael Ploujnikov
> <michael.ploujnikov@oracle.com> wrote:
>>
>> On 2018-07-04 04:52 AM, Richard Biener wrote:
>>> On Tue, Jul 3, 2018 at 9:09 PM Jeff Law <law@redhat.com> wrote:
>>>>
>>>> On 07/03/2018 11:55 AM, Michael Ploujnikov wrote:
>>>>> On 2018-07-03 12:46 PM, Richard Biener wrote:
>>>>>> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
>>>>>>> On 2018-06-20 04:23 AM, Richard Biener wrote:
>>>>>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
>>>>>>>>>
>>>>>>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
>>>>>>>>>> Hi everyone,
>>>>>>>>>>
>>>>>>>>>> (I hope this is the right place to ask, if not my apologies; please
>>>>>>>>>> point me in the right direction)
>>>>>>>>>>
>>>>>>>>>> I'm trying to get a better understanding of the following part in
>>>>>>>>>> tree_swap_operands_p():
>>>>>>>>>>
>>>>>>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
>>>>>>> form
>>>>>>>>>>      for commutative and comparison operators.  Ensuring a
>>>>>>> canonical
>>>>>>>>>>      form allows the optimizers to find additional redundancies
>>>>>>> without
>>>>>>>>>>      having to explicitly check for both orderings.  */
>>>>>>>>>>   if (TREE_CODE (arg0) == SSA_NAME
>>>>>>>>>>       && TREE_CODE (arg1) == SSA_NAME
>>>>>>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
>>>>>>>>>>     return 1;
>>>>>>>>>>
>>>>>>>>>> My questions in no particular order: It looks like this was added
>>>>>>> in
>>>>>>>>>> 2004. I couldn't find any info other than what's in the
>>>>>>> corresponding
>>>>>>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
>>>>>>> still
>>>>>>>>>> relevant/needed today? Does the ordering have to be done based on
>>>>>>> the
>>>>>>>>>> name versions specifically? Or can it be based on something more
>>>>>>>>>> intrinsic to the input source code rather than a GCC internal
>>>>>>> value, eg:
>>>>>>>>>> would alphabetic sort order of the variable names be a reasonable
>>>>>>>>>> replacement?
>>>>>>>>> Canonicalization is still important and useful.
>>>>>>>>
>>>>>>>> Indeed.
>>>>>>>>
>>>>>>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
>>>>>>> we
>>>>>>>>> recycle nodes and re-pack them.
>>>>>>>>
>>>>>>>> In the past we made sure to not disrupt order - hopefully that didn't
>>>>>>> change
>>>>>>>> so the re-packing shoudln't invaidate previous canonicalization:
>>>>>>>>
>>>>>>>> static void
>>>>>>>> release_free_names_and_compact_live_names (function *fun)
>>>>>>>> {
>>>>>>>> ...
>>>>>>>>   /* And compact the SSA number space.  We make sure to not change
>>>>>>> the
>>>>>>>>      relative order of SSA versions.  */
>>>>>>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
>>>>>>>>     {
>>>>>>>>
>>>>>>>>
>>>>>>>>> I think defining additional rules for canonicalization prior to
>>>>>>> using
>>>>>>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
>>>>>>>>
>>>>>>>> I don't see a good reason to do that, it will be harder to spot
>>>>>>> canonicalization
>>>>>>>> issues and it will take extra compile-time.
>>>>>>>>
>>>>>>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
>>>>>>> are
>>>>>>>>> temporaries generated by the compiler and do not correspond to any
>>>>>>>>> declared/defined object in the original source.  So you'll still
>>>>>>> need
>>>>>>>>> the SSA_NAME_VERSION (or something as stable or better)
>>>>>>> canonicalization
>>>>>>>>> to handle those cases.
>>>>>>>>
>>>>>>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
>>>>>>> names).
>>>>>>>>
>>>>>>>> Richard.
>>>>>>>>
>>>>>>>>> Jeff
>>>>>>>
>>>>>>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
>>>>>>> the order of UIDs, which indirectly affects the order of vars in
>>>>>>> old_ssa_names, which in turn affects the order in which
>>>>>>> make_ssa_name_fn
>>>>>>> is called to pick SSA versions from FREE_SSANAMES so in the end
>>>>>>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
>>>>>>> by
>>>>>>> UIDs. I'm trying to figure out if there's a way to avoid depending on
>>>>>>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
>>>>>>> the same I'm wondering if there's some other info available at the
>>>>>>> point
>>>>>>> of insert_phi_nodes that would be a good replacement for UID. From my
>>>>>>> very limited experience with a very small source input, and if I
>>>>>>> understand things correctly, all of the var_infos have a var which is
>>>>>>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
>>>>>>> general case? I don't fully understand what are all the things that
>>>>>>> insert_phi_nodes iterates over.
>>>>>>
>>>>>> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation...
>>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> - Michael
>>>>>>
>>>>>
>>>>>
>>>>> Well, I'm working on a reduction of the number of changes seen with
>>>>> binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
>>>>> since current UID assignment is essentially tied to the order of things
>>>>> in the input source code one function's changes can cascade to others
>>>>> (even when they're unchanged). As you said UID dependence is quiet
>>>>> pervasive, and although finding and improving individual cases (such as
>>>>> tree_swap_operands_p) won't make it perfect, I think it will be a step
>>>>> in the positive direction.
>>>>>
>>>>> Also, I have some ideas for a UID assignment scheme that might improve
>>>>> things overall, that I'll try to share after I get back from vacation.
>>>> I'm still not sure what the point is.  GIven the same input, you're
>>>> going to get the same output.  Using UIDs is deterministic.  If the
>>>> input changes, then, yea, sure the output is going to change, but that's
>>>> got to be expected.
>>
>> Just wanted to say thanks for taking the time to answer my questions.
>>
>> My main goal is to make each function's codegen as independent from one
>> another as possible. In other words, source changes to function A
>> shouldn't result in assembly changes for any of the other functions.
> 
> I see.  The main issue is that we "work" on functions multiple times
> and intermediate work on other functions can influence code-generation
> via IPA mechanisms.  Assigning UIDs should _not_ have an effect
> as long as the order of assignment for the function itself doesn't change.
> 
>>
>> Example attached.
>>
>> I have a prototype of a UID assignment scheme that handles a lot of
>> cases; I'm just waiting for legal approval before I can share the actual
>> code.
>>
>> In the meantime I'm trying to understand the problem from the bottom up
>> and came across this tree_swap_operands_p case. I'm asking for your
>> expertise as to whether my conclusion (that PHI node UID order dictates
>> the SSA version assignment) is correct.
> 
> Well, kind-of.  We do
> 
>   auto_vec<var_info *> vars (var_infos->elements ());
>   FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
>     if (info->info.need_phi_state != NEED_PHI_STATE_NO)
>       vars.quick_push (info);
> 
>   /* Do two stages to avoid code generation differences for UID
>      differences but no UID ordering differences.  */
>   vars.qsort (insert_phi_nodes_compare_var_infos);
> 
> which means we make sure to process PHI insertion in UID _order_
> to avoid code-generation differences when another function gets UIDs
> allocated.  The actual assignment of UIDs should happen by the
> frontend or at gimplification time which happens in-order.
> 
> But PHIs do not get UIDs, their underlying variables do.

Right, sorry, I wasn't being very precise. This is all it took to fix my test cases:

 insert_phi_nodes_compare_var_infos (const void *a, const void *b)
 {
   const var_info *defa = *(var_info * const *)a;
   const var_info *defb = *(var_info * const *)b;
+  if (DECL_NAME (defa->var) && DECL_NAME (defb->var)) {
+    int name_order = strcmp( IDENTIFIER_POINTER (DECL_NAME (defa->var)),
+                            IDENTIFIER_POINTER (DECL_NAME (defb->var)));
+    if (name_order != 0)
+      return name_order;
+  }
   if (DECL_UID (defa->var) < DECL_UID (defb->var))
     return -1;
   else
     return 1;
 }

I'm wondering:
 1) if this is valid in all possible cases because it assumes that defa and defb are DECL_P
 2) if it's ever possible to be comparing two variables of the same name at that point (perhaps two ".MEM"s?). Because it would be really nice to completely remove dependence on the DECL_UID in this function
 3) if there's anything else I should change before submitting this as a patch

- Michael


> 
>>> Yeah, UIDs are likely not the correct handle on this.> You might get
>>> "less" code generation changes when you change sources by
>>> using -fno-toplevel-reorder.
>>
>> Using no-toplevel-reorder didn't help, plus my situation is so general
>> that I can't control the enabled flags.
>>
>>>
>>> I also remember that at one point I facilitated debugging / testcase
>>> reduction by "rounding" UIDs up when starting to process a different
>>> function.
>>
>> Is there a thread about this that you can point me to? I'm curious about
>> the details.
> 
> ISTR I wanted to minimize differences in -uid dumps so I basically
> rouded up the last assigned uid at certain points.
> 
> Richard.
> 
>>
>> P.S. The attached sources can compiled with:
>> gcc-7.3.1 -fno-toplevel-reorder -nostdinc -isystem
>> /usr/lib/gcc/i686-redhat-linux/4.4.6/include
>> -I/builddir/build/BUILD/kernel-2.6.39/linux-2.6.39.i686/arch/x86/include
>> -Iarch/x86/include/generated -Iinclude -include
>> include/generated/autoconf.h -D__KERNEL__ -Wall -Wundef
>> -Wstrict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common
>> -Werror-implicit-function-declaration -Wno-format-security
>> -fno-delete-null-pointer-checks -Os -m32 -msoft-float -mregparm=3
>> -freg-struct-return -mpreferred-stack-boundary=2 -march=i686
>> -mtune=generic -maccumulate-outgoing-args -ffreestanding
>> -fstack-protector -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1
>> -DCONFIG_AS_CFI_SECTIONS=1 -pipe -Wno-sign-compare
>> -fno-asynchronous-unwind-tables -mno-sse -mno-mmx -mno-sse2 -mno-3dnow
>> -Wframe-larger-than=1024 -Wno-unused-but-set-variable
>> -fno-omit-frame-pointer -fno-optimize-sibling-calls -g
>> -femit-struct-debug-baseonly -pg -fno-inline-functions-called-once
>> -Wdeclaration-after-statement -Wno-pointer-sign -fno-strict-overflow
>> -fconserve-stack -DCC_HAVE_ASM_GOTO -ftest-coverage -ffunction-sections
>> -fdata-sections -D__DATE__="<{DATE...}>" -D__TIME__="<{TIME}>"
>> '-DKBUILD_STR(s)=#s' '-DKBUILD_BASENAME=KBUILD_STR(hrtimer)'
>> '-DKBUILD_MODNAME=KBUILD_STR(hrtimer)' -c -o /tmp/pre.o /tmp/pre.i
>>
>>
>> - Michael



[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: Understanding tree_swap_operands_p wrt SSA name versions

[Richard Biener]

On Tue, Jul 17, 2018 at 5:20 AM Michael Ploujnikov
<michael.ploujnikov@oracle.com> wrote:
>
> On 2018-07-16 04:30 AM, Richard Biener wrote:
> > On Mon, Jul 16, 2018 at 12:19 AM Michael Ploujnikov
> > <michael.ploujnikov@oracle.com> wrote:
> >>
> >> On 2018-07-04 04:52 AM, Richard Biener wrote:
> >>> On Tue, Jul 3, 2018 at 9:09 PM Jeff Law <law@redhat.com> wrote:
> >>>>
> >>>> On 07/03/2018 11:55 AM, Michael Ploujnikov wrote:
> >>>>> On 2018-07-03 12:46 PM, Richard Biener wrote:
> >>>>>> On July 3, 2018 4:56:57 PM GMT+02:00, Michael Ploujnikov <michael.ploujnikov@oracle.com> wrote:
> >>>>>>> On 2018-06-20 04:23 AM, Richard Biener wrote:
> >>>>>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <law@redhat.com> wrote:
> >>>>>>>>>
> >>>>>>>>> On 06/19/2018 12:30 PM, Michael Ploujnikov wrote:
> >>>>>>>>>> Hi everyone,
> >>>>>>>>>>
> >>>>>>>>>> (I hope this is the right place to ask, if not my apologies; please
> >>>>>>>>>> point me in the right direction)
> >>>>>>>>>>
> >>>>>>>>>> I'm trying to get a better understanding of the following part in
> >>>>>>>>>> tree_swap_operands_p():
> >>>>>>>>>>
> >>>>>>>>>>   /* It is preferable to swap two SSA_NAME to ensure a canonical
> >>>>>>> form
> >>>>>>>>>>      for commutative and comparison operators.  Ensuring a
> >>>>>>> canonical
> >>>>>>>>>>      form allows the optimizers to find additional redundancies
> >>>>>>> without
> >>>>>>>>>>      having to explicitly check for both orderings.  */
> >>>>>>>>>>   if (TREE_CODE (arg0) == SSA_NAME
> >>>>>>>>>>       && TREE_CODE (arg1) == SSA_NAME
> >>>>>>>>>>       && SSA_NAME_VERSION (arg0) > SSA_NAME_VERSION (arg1))
> >>>>>>>>>>     return 1;
> >>>>>>>>>>
> >>>>>>>>>> My questions in no particular order: It looks like this was added
> >>>>>>> in
> >>>>>>>>>> 2004. I couldn't find any info other than what's in the
> >>>>>>> corresponding
> >>>>>>>>>> commit (cc0bdf913) so I'm wondering if the canonical form/order
> >>>>>>> still
> >>>>>>>>>> relevant/needed today? Does the ordering have to be done based on
> >>>>>>> the
> >>>>>>>>>> name versions specifically? Or can it be based on something more
> >>>>>>>>>> intrinsic to the input source code rather than a GCC internal
> >>>>>>> value, eg:
> >>>>>>>>>> would alphabetic sort order of the variable names be a reasonable
> >>>>>>>>>> replacement?
> >>>>>>>>> Canonicalization is still important and useful.
> >>>>>>>>
> >>>>>>>> Indeed.
> >>>>>>>>
> >>>>>>>>> However, canonicalizing on SSA_NAMEs is problematical due to the way
> >>>>>>> we
> >>>>>>>>> recycle nodes and re-pack them.
> >>>>>>>>
> >>>>>>>> In the past we made sure to not disrupt order - hopefully that didn't
> >>>>>>> change
> >>>>>>>> so the re-packing shoudln't invaidate previous canonicalization:
> >>>>>>>>
> >>>>>>>> static void
> >>>>>>>> release_free_names_and_compact_live_names (function *fun)
> >>>>>>>> {
> >>>>>>>> ...
> >>>>>>>>   /* And compact the SSA number space.  We make sure to not change
> >>>>>>> the
> >>>>>>>>      relative order of SSA versions.  */
> >>>>>>>>   for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i)
> >>>>>>>>     {
> >>>>>>>>
> >>>>>>>>
> >>>>>>>>> I think defining additional rules for canonicalization prior to
> >>>>>>> using
> >>>>>>>>> SSA_NAME_VERSION as the fallback would be looked upon favorably.
> >>>>>>>>
> >>>>>>>> I don't see a good reason to do that, it will be harder to spot
> >>>>>>> canonicalization
> >>>>>>>> issues and it will take extra compile-time.
> >>>>>>>>
> >>>>>>>>> Note however, that many of the _DECL nodes referenced by SSA_NAMEs
> >>>>>>> are
> >>>>>>>>> temporaries generated by the compiler and do not correspond to any
> >>>>>>>>> declared/defined object in the original source.  So you'll still
> >>>>>>> need
> >>>>>>>>> the SSA_NAME_VERSION (or something as stable or better)
> >>>>>>> canonicalization
> >>>>>>>>> to handle those cases.
> >>>>>>>>
> >>>>>>>> And not all SSA_NAMEs have underlying _DECL nodes (or IDENTIFIER_NODE
> >>>>>>> names).
> >>>>>>>>
> >>>>>>>> Richard.
> >>>>>>>>
> >>>>>>>>> Jeff
> >>>>>>>
> >>>>>>> After a bit more digging I found that insert_phi_nodes inserts PHIs in
> >>>>>>> the order of UIDs, which indirectly affects the order of vars in
> >>>>>>> old_ssa_names, which in turn affects the order in which
> >>>>>>> make_ssa_name_fn
> >>>>>>> is called to pick SSA versions from FREE_SSANAMES so in the end
> >>>>>>> ordering by SSA_NAME_VERSION's is more or less equivalent to ordering
> >>>>>>> by
> >>>>>>> UIDs. I'm trying to figure out if there's a way to avoid depending on
> >>>>>>> UIDs being ordered in a certain way. So if tree_swap_operands_p stays
> >>>>>>> the same I'm wondering if there's some other info available at the
> >>>>>>> point
> >>>>>>> of insert_phi_nodes that would be a good replacement for UID. From my
> >>>>>>> very limited experience with a very small source input, and if I
> >>>>>>> understand things correctly, all of the var_infos have a var which is
> >>>>>>> DECL_P and thus should have an IDENTIFIER_NODE. Is that true in the
> >>>>>>> general case? I don't fully understand what are all the things that
> >>>>>>> insert_phi_nodes iterates over.
> >>>>>>
> >>>>>> Why do you want to remove the dependence on UID ordering? It's pervasive throughout the whole compilation...
> >>>>>>
> >>>>>> Richard.
> >>>>>>
> >>>>>>> - Michael
> >>>>>>
> >>>>>
> >>>>>
> >>>>> Well, I'm working on a reduction of the number of changes seen with
> >>>>> binary diffing (a la https://wiki.debian.org/ReproducibleBuilds) and
> >>>>> since current UID assignment is essentially tied to the order of things
> >>>>> in the input source code one function's changes can cascade to others
> >>>>> (even when they're unchanged). As you said UID dependence is quiet
> >>>>> pervasive, and although finding and improving individual cases (such as
> >>>>> tree_swap_operands_p) won't make it perfect, I think it will be a step
> >>>>> in the positive direction.
> >>>>>
> >>>>> Also, I have some ideas for a UID assignment scheme that might improve
> >>>>> things overall, that I'll try to share after I get back from vacation.
> >>>> I'm still not sure what the point is.  GIven the same input, you're
> >>>> going to get the same output.  Using UIDs is deterministic.  If the
> >>>> input changes, then, yea, sure the output is going to change, but that's
> >>>> got to be expected.
> >>
> >> Just wanted to say thanks for taking the time to answer my questions.
> >>
> >> My main goal is to make each function's codegen as independent from one
> >> another as possible. In other words, source changes to function A
> >> shouldn't result in assembly changes for any of the other functions.
> >
> > I see.  The main issue is that we "work" on functions multiple times
> > and intermediate work on other functions can influence code-generation
> > via IPA mechanisms.  Assigning UIDs should _not_ have an effect
> > as long as the order of assignment for the function itself doesn't change.
> >
> >>
> >> Example attached.
> >>
> >> I have a prototype of a UID assignment scheme that handles a lot of
> >> cases; I'm just waiting for legal approval before I can share the actual
> >> code.
> >>
> >> In the meantime I'm trying to understand the problem from the bottom up
> >> and came across this tree_swap_operands_p case. I'm asking for your
> >> expertise as to whether my conclusion (that PHI node UID order dictates
> >> the SSA version assignment) is correct.
> >
> > Well, kind-of.  We do
> >
> >   auto_vec<var_info *> vars (var_infos->elements ());
> >   FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
> >     if (info->info.need_phi_state != NEED_PHI_STATE_NO)
> >       vars.quick_push (info);
> >
> >   /* Do two stages to avoid code generation differences for UID
> >      differences but no UID ordering differences.  */
> >   vars.qsort (insert_phi_nodes_compare_var_infos);
> >
> > which means we make sure to process PHI insertion in UID _order_
> > to avoid code-generation differences when another function gets UIDs
> > allocated.  The actual assignment of UIDs should happen by the
> > frontend or at gimplification time which happens in-order.
> >
> > But PHIs do not get UIDs, their underlying variables do.
>
> Right, sorry, I wasn't being very precise. This is all it took to fix my test cases:
>
>  insert_phi_nodes_compare_var_infos (const void *a, const void *b)
>  {
>    const var_info *defa = *(var_info * const *)a;
>    const var_info *defb = *(var_info * const *)b;
> +  if (DECL_NAME (defa->var) && DECL_NAME (defb->var)) {
> +    int name_order = strcmp( IDENTIFIER_POINTER (DECL_NAME (defa->var)),
> +                            IDENTIFIER_POINTER (DECL_NAME (defb->var)));
> +    if (name_order != 0)
> +      return name_order;
> +  }
>    if (DECL_UID (defa->var) < DECL_UID (defb->var))
>      return -1;
>    else
>      return 1;
>  }
>
> I'm wondering:
>  1) if this is valid in all possible cases because it assumes that defa and defb are DECL_P
>  2) if it's ever possible to be comparing two variables of the same name at that point (perhaps two ".MEM"s?). Because it would be really nice to completely remove dependence on the DECL_UID in this function
>  3) if there's anything else I should change before submitting this as a patch

Well, _I_ wonder why the DECL_UIDs for the respective vars are not
assigned in the same order when
you change an unrelated function.  DECL_UIDs are generally assigned
during parsing.  And as you
see from the sorting above all that matters is the _order_ they get
their UID assiged.

Can you explain that?

Thanks,
Richard.

> - Michael
>
>
> >
> >>> Yeah, UIDs are likely not the correct handle on this.> You might get
> >>> "less" code generation changes when you change sources by
> >>> using -fno-toplevel-reorder.
> >>
> >> Using no-toplevel-reorder didn't help, plus my situation is so general
> >> that I can't control the enabled flags.
> >>
> >>>
> >>> I also remember that at one point I facilitated debugging / testcase
> >>> reduction by "rounding" UIDs up when starting to process a different
> >>> function.
> >>
> >> Is there a thread about this that you can point me to? I'm curious about
> >> the details.
> >
> > ISTR I wanted to minimize differences in -uid dumps so I basically
> > rouded up the last assigned uid at certain points.
> >
> > Richard.
> >
> >>
> >> P.S. The attached sources can compiled with:
> >> gcc-7.3.1 -fno-toplevel-reorder -nostdinc -isystem
> >> /usr/lib/gcc/i686-redhat-linux/4.4.6/include
> >> -I/builddir/build/BUILD/kernel-2.6.39/linux-2.6.39.i686/arch/x86/include
> >> -Iarch/x86/include/generated -Iinclude -include
> >> include/generated/autoconf.h -D__KERNEL__ -Wall -Wundef
> >> -Wstrict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common
> >> -Werror-implicit-function-declaration -Wno-format-security
> >> -fno-delete-null-pointer-checks -Os -m32 -msoft-float -mregparm=3
> >> -freg-struct-return -mpreferred-stack-boundary=2 -march=i686
> >> -mtune=generic -maccumulate-outgoing-args -ffreestanding
> >> -fstack-protector -DCONFIG_AS_CFI=1 -DCONFIG_AS_CFI_SIGNAL_FRAME=1
> >> -DCONFIG_AS_CFI_SECTIONS=1 -pipe -Wno-sign-compare
> >> -fno-asynchronous-unwind-tables -mno-sse -mno-mmx -mno-sse2 -mno-3dnow
> >> -Wframe-larger-than=1024 -Wno-unused-but-set-variable
> >> -fno-omit-frame-pointer -fno-optimize-sibling-calls -g
> >> -femit-struct-debug-baseonly -pg -fno-inline-functions-called-once
> >> -Wdeclaration-after-statement -Wno-pointer-sign -fno-strict-overflow
> >> -fconserve-stack -DCC_HAVE_ASM_GOTO -ftest-coverage -ffunction-sections
> >> -fdata-sections -D__DATE__="<{DATE...}>" -D__TIME__="<{TIME}>"
> >> '-DKBUILD_STR(s)=#s' '-DKBUILD_BASENAME=KBUILD_STR(hrtimer)'
> >> '-DKBUILD_MODNAME=KBUILD_STR(hrtimer)' -c -o /tmp/pre.o /tmp/pre.i
> >>
> >>
> >> - Michael
>
>