Re: Understanding tree_swap_operands_p wrt SSA name versions

[Michael Ploujnikov <michael dot ploujnikov at oracle dot com>]

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: pre.i
Description: Text document

Attachment: post.i
Description: Text document

Attachment: signature.asc
Description: OpenPGP digital signature