From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <rguenther@suse.de>
Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29])
 by sourceware.org (Postfix) with ESMTPS id 0D419385841A
 for <gcc-patches@gcc.gnu.org>; Mon,  3 Jan 2022 13:16:07 +0000 (GMT)
DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 0D419385841A
Received: from relay2.suse.de (relay2.suse.de [149.44.160.134])
 by smtp-out2.suse.de (Postfix) with ESMTP id EDB311F39F;
 Mon,  3 Jan 2022 13:16:05 +0000 (UTC)
Received: from murzim.suse.de (murzim.suse.de [10.160.4.192])
 (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
 (No client certificate requested)
 by relay2.suse.de (Postfix) with ESMTPS id E45F2A3B84;
 Mon,  3 Jan 2022 13:16:05 +0000 (UTC)
Date: Mon, 3 Jan 2022 14:16:05 +0100 (CET)
From: Richard Biener <rguenther@suse.de>
To: Segher Boessenkool <segher@kernel.crashing.org>
cc: Jakub Jelinek <jakub@redhat.com>, Jeff Law <jeffreyalaw@gmail.com>, 
 gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] shrink-wrapping: Don't call can_get_prologue unnecessarily
 [PR103860]
In-Reply-To: <20220103131245.GP614@gate.crashing.org>
Message-ID: <s4355ps-9qop-2893-3s98-80621p86p919@fhfr.qr>
References: <20211230094332.GZ2646553@tucnak>
 <20211230100825.GL614@gate.crashing.org> <20220103110010.GT2646553@tucnak>
 <20220103131245.GP614@gate.crashing.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
X-Spam-Status: No, score=-5.0 required=5.0 tests=BAYES_00, DKIM_SIGNED,
 DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, SPF_HELO_NONE, SPF_PASS,
 TXREP autolearn=ham autolearn_force=no version=3.4.4
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on
 server2.sourceware.org
X-BeenThere: gcc-patches@gcc.gnu.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Gcc-patches mailing list <gcc-patches.gcc.gnu.org>
List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>,
 <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe>
List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/>
List-Post: <mailto:gcc-patches@gcc.gnu.org>
List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help>
List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>,
 <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe>
X-List-Received-Date: Mon, 03 Jan 2022 13:16:09 -0000

On Mon, 3 Jan 2022, Segher Boessenkool wrote:

> Hi!
> 
> On Mon, Jan 03, 2022 at 12:00:10PM +0100, Jakub Jelinek wrote:
> > On Thu, Dec 30, 2021 at 04:08:25AM -0600, Segher Boessenkool wrote:
> > > > The following simple patch makes sure we call can_get_prologue even after
> > > > the last former iteration when vec is already empty and only break from
> > > > the loop afterwards (and only if the updating of pro done because of
> > > > !can_get_prologue didn't push anything into vec again).
> > 
> > During the development of the above patch I've noticed that in many cases
> > we call can_get_prologue often on the same pro again and again and again,
> > we can have many basic blocks pushed into vec and if most of those don't
> > require pro updates, i.e.
> >       basic_block bb = vec.pop ();
> >       if (!can_dup_for_shrink_wrapping (bb, pro, max_grow_size))
> >         while (!dominated_by_p (CDI_DOMINATORS, bb, pro))
> > isn't true, then pro is can_get_prologue checked for each bb in the vec.
> > 
> > The following simple patch just remembers which bb we've verified already
> > and verifies again only when pro changes.  Most of the patch is just
> > reindentation.
> 
> I'd like it better if the code structure was changed so you do not need
> this workaround.  That will probably result in much clearer code.
> 
> But it does look correct :-)
> 
> This should make things O(n) again here.  Thanks for fixing this!

Btw, you can take that as approval.

Richard.