From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 123218 invoked by alias); 27 Nov 2019 08:29:42 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 123209 invoked by uid 89); 27 Nov 2019 08:29:42 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_50,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.1 spammy=disregard, combine2, fwprop.c, hardreg X-HELO: mail-lj1-f180.google.com Received: from mail-lj1-f180.google.com (HELO mail-lj1-f180.google.com) (209.85.208.180) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 27 Nov 2019 08:29:40 +0000 Received: by mail-lj1-f180.google.com with SMTP id k15so23452439lja.3 for ; Wed, 27 Nov 2019 00:29:40 -0800 (PST) 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=Zs+aQuojCSv2iT/yO9h2NoEVceRHBigmbgmhteSlw+A=; b=iizzr+MHJUSPPZQmwwbJGXEbW8fg4PX1S2+iL4BkHY8BSBIFNvNWfho4q99BHBXNON aEoccEOMK7bMsvCUHhSngCYT8slyfsYq95rQGiomY8bJz7sEp7APJMJsTk2+DxhgbF28 woGQ0+n+3liVT/fFqA+eibgEBa1JibghrT7YIxX9RhOa/issY7TOzrOBVgaYcAgf1RX3 2d+NaeepoBvrVg/1FJcjy2fvBqMOEMyWkfOp76VwAWp8n6Il/ZpHk/okdUQxWkuudSOo xgSxYd86v2Z0Yg5Y+yiFzyKCBEE438eKT0YfEtKffp0DrfT871T9z8N6R5KaFQG54eqK NwEQ== MIME-Version: 1.0 References: <20191118235659.GO16031@gate.crashing.org> <20191119203932.GC16031@gate.crashing.org> <20191120204556.GP16031@gate.crashing.org> <20191122163911.GE9491@gate.crashing.org> <20191125221350.GW9491@gate.crashing.org> <20191126014247.GC9491@gate.crashing.org> In-Reply-To: <20191126014247.GC9491@gate.crashing.org> From: Richard Biener Date: Wed, 27 Nov 2019 08:32:00 -0000 Message-ID: Subject: Re: Add a new combine pass To: Segher Boessenkool Cc: GCC Patches , Nicholas Krause , Richard Sandiford Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2019-11/txt/msg02479.txt.bz2 On Tue, Nov 26, 2019 at 2:42 AM Segher Boessenkool wrote: > > On Mon, Nov 25, 2019 at 11:08:47PM +0000, Richard Sandiford wrote: > > Segher Boessenkool writes: > > > On Mon, Nov 25, 2019 at 09:16:52PM +0000, Richard Sandiford wrote: > > >> Segher Boessenkool writes: > > >> > I am wondering the other way around :-) Is what you do for combine2 > > >> > something that would be more generally applicable/useful? That's what > > >> > I'm trying to find out :-) > > >> > > > >> > What combine does could use some improvement, if you want to hear a > > >> > more direct motivations. LOG_LINKS just skip references we cannot > > >> > handle (and some more), so we always have to do modified_between etc., > > >> > which hurts. > > >> > > >> The trade-offs behind the choice of representation are very specific > > >> to the pass. > > > > > > Yes, but hopefully not so specific that every pass needs a completely > > > different representation ;-) > > > > Well, it depends. Most passes make do with df (without DU/UD-chains). > > But since DU/UD-chains are naturally quadratic in the general case, > > and are expensive to keep up to date, each DU/UD pass is going to have > > make some compromises. It doesn't seem too bad that passes make > > different compromises based on what they're trying to do. (combine: > > single use per definition; fwprop.c: track all uses, but for dominating > > definitions only; sched: fudged via a param; regrename: single > > definition/multiple use chains optimised for renmaing; combine2: full > > live range information, but limited use list; etc.) > > combine actually *calculates* DU chains almost completely, it just throws > away most of that information (it wants to have LOG_LINKS, as it did ages > ago). The only thing stopping us from doing that right now is that not > all uses are counted (some are skipped). > > Since combine works only within BBs, DU chains are linear to compute, and > UD chains are trivial (and just linear to compute). quadraticness appears for RTL DU/UD chains because of partial definitions, that doesn't change for BBs so even there computing is them is quadratic (because recording them is). The situation is simply having N partial defs all reaching M uses which gives you a chain of size N * M. Now - for combine you don't want partial defs, so for simplicity we could choose to _not_ record DU/UD chains whenever we see a partial def for a pseudo (and mark those as "bad"). Or, slightly enhanced, we can handle DU/UD chains for regions where there is no partial definition and add a "fake" D denoting (there are [multiple] defs beyond that might be partial). Depending on the use-case that should suffice and make the problem linear. I think you want to ask sth like "is REG changed [partially] between its use in insn A and the def in insn B" and you want to answer that by using REGs UD chain for that. If you only ever reached the def in insn B via the "pruned" chain then this would work, likewise for the chain we do not compute any UD chain for REG. > Updating is quadratic in general, sure. Luckily in most realistic cases > it is cheap (most, sigh) (insns aren't combined to very far away). Updating is linear as well if you can disregard partial defs. Updating cannot be quadratic if compute is linear ;) > > So yeah, if passes want to make roughly the same compromises, it would > > obviously be good if they shared a representation. But since each pass > > does something different, I don't think it's a bad sign that they make > > different compromises and use different representations. > > > > So I don't think a new pass with a new representation is in itself a > > sign of failure. > > Oh, I don't think so either. I just wonder if it would be useful more > generically :-) > > > >> >> >> Target Tests Delta Best Worst Median > > >> >> >> avr-elf 1341 -111401 -13824 680 -10 > > >> >> > > > >> >> > Things like this are kind of suspicious :-) > > >> >> > > >> >> Yeah. This mostly seems to come from mopping up the extra moves created > > >> >> by make_more_copies. So we have combinations like: > > >> >> > > >> >> 58: r70:SF=r94:SF > > >> >> REG_DEAD r94:SF > > >> >> 60: r22:SF=r70:SF > > >> >> REG_DEAD r70:SF > > >> > > > >> > Why didn't combine do this? A target problem? > > >> > > >> Seems to be because combine rejects hard-reg destinations whose classes > > >> are likely spilled (cant_combine_insn_p). > > > > > > Ah, okay. And that is required to prevent ICEs, in combine2 as well > > > then -- ICEs in RA. > > > > Not in this case though. The final instruction is a hardreg<-pseudo move > > whatever happens. There's nothing special about r70 compared to r94. > > So the target hook could be improved? Or, this doesn't matter anyway, > the extra register move does not prevent any combinations, and RA should > get rid of it when that is beneficial. > > But you see smaller code in the end, hrm. > > > Segher