From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 88791 invoked by alias); 22 Mar 2018 12:27:42 -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 88767 invoked by uid 89); 22 Mar 2018 12:27:42 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.1 required=5.0 tests=AWL,BAYES_05,FREEMAIL_FROM,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=Their, H*f:sk:CAFiYyc, sebaspe97hotmailcom, sebaspe97@hotmail.com X-HELO: mail-lf0-f54.google.com Received: from mail-lf0-f54.google.com (HELO mail-lf0-f54.google.com) (209.85.215.54) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 22 Mar 2018 12:27:35 +0000 Received: by mail-lf0-f54.google.com with SMTP id z143-v6so12847997lff.3 for ; Thu, 22 Mar 2018 05:27:34 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=S1C5U9x01hUvurRJi2x226VdzmF+2sNP7EPQ3XDnh1A=; b=aYmpYQDcS9ZfBI/UOWz9kpSUySWglFrqwVZfFtmxOQ5ycQgFU4F+C1dSrHZ4WLQeKh d42FkMh1FivXjsW7RKwFXBPPkgxMrpXZHdNiNvwNA4ojpbulx6FWIscXl/M9s3HRLrQp RNSiu/EFeqmmTQcMv3r5Ih55YM7ZAxysK3Fv0wWsYHlmtrDm/UYp3LLSQgkV8+UaCIy2 X8pVrf7wg39UN3Uc88eXQIPB5nXWbpFacJ+wWJRcpy3s1hqsp6wZo+YJtdY0rTx4cbWF BBNuabm358D1BjPH4+9mwUS+2thHldASxO4mp6lvlq1H8UbSOrHz4Wlw2oevpDPkV3H6 G51w== X-Gm-Message-State: AElRT7ENtNOqJoG5YYhSJqvMBneNaTpvwBJtq0NEuiRRQOT1VCLbOfRP UT7SqNzXNyXlmPfJIx2ItON+c7HySXnPs8hjfos= X-Google-Smtp-Source: AG47ELuZpMKfhS0uEw48co4TCeaWjUK1HBRRm9aSvbVRUJGvnjCu/rAWUFWmn9V9RRRfvx0GBQyyU7TNQHCQ4+CDWsE= X-Received: by 10.46.154.145 with SMTP id p17mr7662233lji.28.1521721652350; Thu, 22 Mar 2018 05:27:32 -0700 (PDT) MIME-Version: 1.0 Received: by 10.46.145.197 with HTTP; Thu, 22 Mar 2018 05:27:31 -0700 (PDT) In-Reply-To: References: <2C17E153-DCDC-4E24-B9D3-64E0FF358758@gmail.com> <1521557360.5688.30.camel@redhat.com> From: Richard Biener Date: Thu, 22 Mar 2018 12:27:00 -0000 Message-ID: Subject: Re: GSOC Question about the parallelization project To: Sebastiaan Peters Cc: David Malcolm , Sebastiaan Peters , "gcc@gcc.gnu.org" Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2018-03/txt/msg00218.txt.bz2 On Wed, Mar 21, 2018 at 8:04 PM, Sebastiaan Peters wrote: >>On Wed, Mar 21, 2018 at 9:50 AM, Sebastiaan Peters >> wrote: >>>>On Tue, Mar 20, 2018 at 3:49 PM, David Malcolm wrote: >>>>> On Tue, 2018-03-20 at 14:02 +0100, Richard Biener wrote: >>>>>> On Mon, Mar 19, 2018 at 9:55 PM, Richard Biener >>>>>> wrote: >>>>>> > On March 19, 2018 8:09:32 PM GMT+01:00, Sebastiaan Peters >>>>> > 7@hotmail.com> wrote: >>>>>> > > > The goal should be to extend TU wise parallelism via make to >>>>>> > > > function >>>>>> > > >>>>>> > > wise parallelism within GCC. >>>>>> > > >>>>>> > > Could you please elaborate more on this? >>>>>> > >>>>>> > In the abstract sense you'd view the compilation process separated >>>>>> > into N stages, each function being processed by each. You'd assign >>>>>> > a thread to each stage and move the work items (the functions) >>>>>> > across the set of threads honoring constraints such as an IPA stage >>>>>> > needing all functions completed the previous stage. That allows you >>>>>> > to easier model the constraints due to shared state (like no pass >>>>>> > operating on two functions at the same time) compared to a model >>>>>> > where you assign a thread to each function. >>>>>> > >>>>>> > You'll figure that the easiest point in the pipeline to try this >>>>>> > 'pipelining' is after IPA has completed and until RTL is generated. >>>>>> > >>>>>> > Ideally the pipelining would start as early as the front ends >>>>>> > finished parsing a function and ideally we'd have multiple >>>>>> > functions in the RTL pipeline. >>>>>> > >>>>>> > The main obstacles will be the global state in the compiler of >>>>>> > which there is the least during the GIMPLE passes (mostly cfun and >>>>>> > current_function_decl plus globals in the individual passes which >>>>>> > is easiest dealt with by not allowing a single pass to run at the >>>>>> > same time in multiple threads). TLS can be used for some of the >>>>>> > global state plus of course some global data structures need >>>>>> > locking. >>> >>> This would mean that all the passes have to be individually analyzed for >>> which global state >>> they use, and lock/schedule them accordingly? >> >>Their private global state would be excempt by assuring that a pass never >>runs twice at the same time. >> >>The global state that remains should be the same for all passes we are talking >>about (during the late GIMPLE optimization phase which I'd tackle). >> >>> If this is the case, is there any documentation that describes the pre-reqs >>> for each pass? >>> I have looked at the internal documentation, however it seems that all of >>> this still has to be created? >> >>The prereqs are actually the same and not very well documented (if at all). >>There's the global GC memory pool where we allocate statements and >>stuff like that from (and luckyly statements themselves are function private). >>Then there's global trees like types ('int') where modification needs to be >>appropriately guarded. Note that "modification" means for example >>building a new type for the address of 'int' given that all different >>pointer types >>to 'int' are chained in a list rooted in the tree for 'int'. That >>means (a few?) >>tree building helpers need to be guarded with locks. I don't have a great >>idea how to identify those apart from knowing them in advance or running >>into races ... my gut feeling is that there's not a lot to guard but I may >>be wrong ;) > > What does it mean to be a node of a type tree? > Does it describe information about that type, > or does it keep a reference to where something > of that type has been declared? On the GIMPLE level we have two main kinds of data objects, one is 'gimple' (and derived clases) for statements and 'tree' for operands, types, declarations. 'tree's is also what GENERIC is represented in, the IL that gets produced by the frontends which is lowered to GIMPLE by the gimplifier. On GENERIC everything is a 'tree' (there's a class hierarchy of trees implemented in C ways via unions), types are, and so are decls and expressions (in GENERIC). You can look at tree.h (and tree-core.h for implementation details) and for example see #define TYPE_POINTER_TO(NODE) (TYPE_CHECK (NODE)->type_common.pointer_to) where tree.c:build_pointer_type_for_mode does /* First, if we already have a type for pointers to TO_TYPE and it's the proper mode, use it. */ for (t = TYPE_POINTER_TO (to_type); t; t = TYPE_NEXT_PTR_TO (t)) if (TYPE_MODE (t) == mode && TYPE_REF_CAN_ALIAS_ALL (t) == can_alias_all) return t; so if a pass builds a new pointer type that doesn't already exist we modify this list. This means an existing type tree is modified even if the type itself isn't modified. >>> As to how this would be implemented, it seems the easiest way would be to >>> extend the macros to >>> accept a pre-req pass. This would encourage more documentation since the >>> dependencies >>> become explicit instead of the current implicit ordering. >> >>Actually the order is quite explicit. Maybe I now understand your >>question - no, >>passes do not "communicate" between each other via global state, all such >>state is per function and the execution order of passes on a given function >>is hard-coded in passes.def. >> >>> Assuming the dependencies for the all the tree-ssa passes have to be >>> individually analyzed. >>> Currently I have this as my timeline: >>> - Parallelize the execution of the post-IPA pre-RTL, and a few tree-ssa >>> passes (mid-may - early june) >>> - Test for possible reproducibility issues for the binary/debug info >>> (early june - late june) >>> - Parallelize the rest of tree-ssa (late june - late july) >>> - Update documentation and test again for reproducibility issues (late >>> july - early august) >>> >>> Would this be acceptable? >> >>Sounds ambitious ;) But yes, it sounds reasonable. I don't exactly >>understand what "Parallelize the rest of tree-ssa" means though. If >>you want to tackle a tiny bit more I'd rather include "RTL" by treating >>the whole RTL part as a single "pass" (as said only one function can >>be in RTL right now). >> > > I was under the assumption that passes had to be indivdually analysed > when I wrote that. The timeline is now updated to include some extra > time in the beginning to familiarize myself a bit more with the project, > and added the RTL as an optional deliverable:) > > I added a draft of the proposal[0], any feedback would be highly appreciated. The poposal looks good to me! Thanks, Richard. >>>>>> Oh, and just to mention - there are a few things that may block >>>>>> adoption in the end >>>>>> like whether builds are still reproducible (we allocate things like >>>>>> DECL_UID from >>>>>> global pools and doing that somewhat randomly because of threading >>>>>> might - but not >>>>>> must - change code generation). Or that some diagnostics will appear >>>>>> in >>>>>> non-deterministic order, or that dump files are messed up (both >>>>>> issues could be >>>>>> solved by code dealing with the issue, like buffering and doing a re- >>>>>> play in >>>>>> program order). I guess reproducability is important when it comes >>>>>> down to >>>>>> debugging code-generation issues - I'd prefer to debug gcc when it >>>>>> doesn't run >>>>>> threaded but if that doesn't reproduce an issue that's bad. >>>>>> >>>>>> So the most important "milestone" of this project is to identify such >>>>>> issues and >>>>>> document them somewhere. >>>>> >>>>> One issue would be the garbage-collector: there are plenty of places in >>>>> GCC that have hidden assumptions that "a collection can't happen here" >>>>> (where we have temporaries that reference GC-managed objects, but which >>>>> aren't tracked by GC-roots). >>>>> >>>>> I had some patches for that back in 2014 that I think I managed to drop >>>>> on the floor (sorry): >>>>> https://gcc.gnu.org/ml/gcc-patches/2014-11/msg01300.html >>>>> https://gcc.gnu.org/ml/gcc-patches/2014-11/msg01340.html >>>>> https://gcc.gnu.org/ml/gcc-patches/2014-11/msg01510.html >>> >>> Would there be a way to easily create a static analyzer to find these >>> untracked temporaries? >> >>I don't think so. >> >>> A quick look at registered passes makes me count ~135 tree-ssa passes, >>> So your code on analyzing what globals are referenced where might come in >>> handy while analyzing if passes are easily parallelized. >> >>I think the "solution" to the garbage collecting issue is to simply keep >>that serialized. It's currently done on-demand anyway at certain >>safe collection points so the work scheduler can simply hold off >>scheduling more work when the collector would want to run, waiting for >>running jobs to complete. >> >>Richard. >> >>>>> The GC's allocator is used almost everywhere, and is probably not >>>>> thread-safe yet. >>>>Yes. There's also global tree modification like chaining new >>>>pointer types into TYPE_POINTER_TO and friends so some >>>>helpers in tree.c need to be guarded as well. >>>>> FWIW I gave a talk at Cauldron 2013 about global state in GCC. Beware: >>>>> it's five years out-of-date, but maybe is still relevant in places? >>>>> https://dmalcolm.fedorapeople.org/gcc/global-state/ >>>>> https://gcc.gnu.org/ml/gcc/2013-05/msg00015.html >>>>> (I tackled this for libgccjit by instead introducing a mutex, a "big >>>>> compiler lock", jit_mutex in gcc/jit/jit-playback.c, held by whichever >>>>> thread is calling into the rest of the compiler sources). >>>>> >>>>> Hope this is helpful >>>>> Dave >>>>> >>>>> > > [0] https://docs.google.com/document/d/1YkKYI3J-pKFfHLdxljWVoJ89l2oVGibxslIW3ikluz8/edit?usp=sharing