From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 100187 invoked by alias); 16 Jul 2018 08:31:35 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 99624 invoked by uid 89); 16 Jul 2018 08:31:03 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-2.5 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=HX-Received:Mon X-HELO: mail-lj1-f195.google.com Received: from mail-lj1-f195.google.com (HELO mail-lj1-f195.google.com) (209.85.208.195) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 16 Jul 2018 08:30:56 +0000 Received: by mail-lj1-f195.google.com with SMTP id u7-v6so26548402lji.3 for ; Mon, 16 Jul 2018 01:30:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=SzVhqPqt9ppaD9hTXxokBbgh+TJgGD5p3IilIste/6A=; b=W5kBaiOo3nqhs797KoKGz/HOkFJJxSPY6Q7aw/+IB/XugXFLtJH2SgU72F12WqzMWj d9EsmtuQBQTTCf+puQYxrdFJBUw0PPinXk2myxlmWDvOgc3mtNpcrmOpG440tGtTau09 6vBbE6kiWVs3ZRxglWoub+6oSPogO5sWBxBszbHTIo2Zg19xdChOWvfLl1iv95DJN/4b Slz0ucXmeU1zwPW0/4dYUtAAHokaMW500f+YTC4372j9D/mHFRCQanb905pQytIPmAXf 79wcEX8hEvzy/34rGz3TkHZMuBEjmjEytQzADX4Jt0+XFBgKFYugVAhqIwTQaoF01Lao Ndsg== MIME-Version: 1.0 References: <5b1a8e4b-c0c5-69f7-1800-605e0b844acb@oracle.com> <226ee5ff-ac66-e8a4-7a67-a07a92eaebbb@redhat.com> <165C3FA6-E1CC-454D-8A2A-9DA9348301D8@gmail.com> <80a30b2c-8b23-f4ed-aa8c-275a554ec9ff@oracle.com> <23cf65ef-2312-b13b-5696-604ca15c7d8e@redhat.com> <45e0a278-9323-b7f4-26d6-1270d369e7b2@oracle.com> In-Reply-To: <45e0a278-9323-b7f4-26d6-1270d369e7b2@oracle.com> From: Richard Biener Date: Mon, 16 Jul 2018 08:31:00 -0000 Message-ID: Subject: Re: Understanding tree_swap_operands_p wrt SSA name versions To: Michael Ploujnikov Cc: Jeff Law , GCC Development Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2018-07/txt/msg00216.txt.bz2 On Mon, Jul 16, 2018 at 12:19 AM Michael Ploujnikov wrote: > > On 2018-07-04 04:52 AM, Richard Biener wrote: > > On Tue, Jul 3, 2018 at 9:09 PM Jeff Law 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 wrote: > >>>>> On 2018-06-20 04:23 AM, Richard Biener wrote: > >>>>>> On Wed, Jun 20, 2018 at 7:31 AM Jeff Law 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 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