On Tue, Jul 17, 2018 at 5:20 AM Michael Ploujnikov
<michael.ploujni...@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.ploujni...@oracle.com> wrote:
> >>
> >> On 2018-07-04 04:52 AM, Richard Biener wrote:
> >>> On Tue, Jul 3, 2018 at 9:09 PM Jeff Law <l...@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.ploujni...@oracle.com> wrote:
> >>>>>>> On 2018-06-20 04:23 AM, Richard Biener wrote:
> >>>>>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law <l...@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
>
>
