From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 57260 invoked by alias); 3 Nov 2016 08:29:21 -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 56526 invoked by uid 89); 3 Nov 2016 08:29:20 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.4 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=no version=3.3.2 spammy=gigantic, ATM, atm X-HELO: mail-wm0-f51.google.com Received: from mail-wm0-f51.google.com (HELO mail-wm0-f51.google.com) (74.125.82.51) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 03 Nov 2016 08:29:10 +0000 Received: by mail-wm0-f51.google.com with SMTP id a197so188703327wmd.0 for ; Thu, 03 Nov 2016 01:29:09 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=NbBp2Wl1TY/XRioBbh1JgvXbVnRIQWUEaD8FzoWJHUo=; b=MdcJGCFihKeQM3gKWDQtfGtex6MY1awKAP7FYQF+6s1XFQ9PHfRZthIAaZRnetot2a pwCt9SdvvQOV/ngUbX1Majvzpb2stEPtT/UuX+jzy5ew6RTLSdegbx5FgEUW7TX/Xmox vSXIIKO6lvZrtXHJwv8oSszAht796hf2YGGRUf+mqx+e1PbEllkN7rhLj19TfHcVJs5Z zSnxOgeiip9qbN64mFsKlgX2/AC2QkGu2HeeywAo287JRX3xrby2V92O5oigoxN6GsdS 7cm/Qu5HerZyJ6pMPLxtFjVsUkQrjbt3dVibAkUFxBO68hVuKJ2k36AHor3GKvip8It7 Os+Q== X-Gm-Message-State: ABUngvf6bpXCyPRDO4dRmrhF/4YgQX0k2mbuNXMw+/0LJsB/fTcGoHr8ADTjHxK1Xcn2iVCL4nHsywuc8F9L6g== X-Received: by 10.28.55.213 with SMTP id e204mr6694718wma.92.1478161748128; Thu, 03 Nov 2016 01:29:08 -0700 (PDT) MIME-Version: 1.0 Received: by 10.28.73.215 with HTTP; Thu, 3 Nov 2016 01:29:07 -0700 (PDT) In-Reply-To: <20161102152722.GA4800@gate.crashing.org> References: <3d8d886a7e9d7bcf5bee9867e2f4849a210fd976.1477843149.git.segher@kernel.crashing.org> <20161031153504.GA3328@gate.crashing.org> <20161102134059.GA28264@gate.crashing.org> <20161102152722.GA4800@gate.crashing.org> From: Richard Biener Date: Thu, 03 Nov 2016 08:29:00 -0000 Message-ID: Subject: Re: [PATCH] bb-reorder: Improve compgotos pass (PR71785) To: Segher Boessenkool Cc: Steven Bosscher , GCC Patches Content-Type: text/plain; charset=UTF-8 X-IsSubscribed: yes X-SW-Source: 2016-11/txt/msg00258.txt.bz2 On Wed, Nov 2, 2016 at 4:27 PM, Segher Boessenkool wrote: > On Wed, Nov 02, 2016 at 02:51:41PM +0100, Richard Biener wrote: >> >> I don't believe it needs a cleanup on every iteration. One cleanup at >> >> the end should work fine. >> > >> > But as the comment there says: >> > >> > /* Merge the duplicated blocks into predecessors, when possible. */ >> > cleanup_cfg (0); >> > >> > (this is not a new comment), and without merging blocks this whole >> > patch does zilch. >> > >> > There is no need to create new basic blocks at all (can replace the >> > final branch in a block with a copy of the whole block it jumps to, >> > instead); and then it is painfully obvious that switching to layout >> > mode here is pointless, too. >> > >> > Do you want me to do that? >> > >> > Btw, this isn't quadratic anyway; it is a constant number (the maximal >> > length allowed of the block to copy) linear. Unless there are unboundedly >> > many forwarder blocks, which there shouldn't be, but I cannot prove that. >> >> Well, you iterate calling functions (find candidates, merge, cleanup-cfg) that >> walk the whole function. So unless the number of iterations is bound >> with a constant I call this quadratic (in function size). > > It is bounded (with that caveat above): new candidates will be bigger than > the block merged into it, so there won't be more than > PARAM_MAX_GOTO_DUPLICATION_INSNS passes. > > But I can make it all work simpler, in non-layout mode, if you prefer. Iteration is fine but we should restrict where we look for new candidates. Likewise block merging opportunities should be easier to exploit than by running cfg-cleanup... I'm just thinking of those gigantic machine-generated state machines where we ATM do quite well (at least at -O1 ...) with respect to compile-time. Richard. > > Segher