From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 71317 invoked by alias); 9 Sep 2016 20:24:54 -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 71302 invoked by uid 89); 9 Sep 2016 20:24:53 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.1 required=5.0 tests=AWL,BAYES_00,RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=exponential, linear, calculating X-HELO: gate.crashing.org Received: from gate.crashing.org (HELO gate.crashing.org) (63.228.1.57) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 09 Sep 2016 20:24:52 +0000 Received: from gate.crashing.org (localhost.localdomain [127.0.0.1]) by gate.crashing.org (8.14.1/8.13.8) with ESMTP id u89KOmol024063; Fri, 9 Sep 2016 15:24:48 -0500 Received: (from segher@localhost) by gate.crashing.org (8.14.1/8.14.1/Submit) id u89KOloB024062; Fri, 9 Sep 2016 15:24:47 -0500 Date: Fri, 09 Sep 2016 20:29:00 -0000 From: Segher Boessenkool To: Jeff Law Cc: Michael Matz , Bernd Schmidt , gcc-patches@gcc.gnu.org Subject: Re: [PATCH v2 0/9] Separate shrink-wrapping Message-ID: <20160909202447.GA21356@gate.crashing.org> References: <81710c02-05bf-fb65-dedc-8ba389c0d8e8@redhat.com> <20160826145001.GA21746@gate.crashing.org> <41fe31e4-81a0-da9e-619a-4c503f7f1051@redhat.com> <20160909061919.GA24532@gate.crashing.org> <20160909154002.GE28260@gate.crashing.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.4.2.3i X-IsSubscribed: yes X-SW-Source: 2016-09/txt/msg00539.txt.bz2 On Fri, Sep 09, 2016 at 12:19:03PM -0600, Jeff Law wrote: > >>Does this impact the compile time computation complexity issue that was > >>raised elsewhere? > > > >I'm not sure what you mean here either, sorry. It is all O(NM) with N > >the number of BBs and M the number of components (and assuming dom > >lookups are constant time, as usual). > You said in a different message that computing optimal placement points > for prologue/epilogue components was not computationally feasible. I'm > just trying to figure out if the switch to utilizing block frequencies > is a part of what makes solving that problem infeasible. Ah, I see. Allowing multiple prologues (and epilogues) is what makes it infeasible. If there is just (at most) one prologue (per component), calculating the optimal placement is of course linear in # BBs, given that the cost function is O(1) (or sort of kind of; linear in # edges really, if you have to insist :-) ) If you allow multiple prologues, i.e. allow any combination of blocks to run with or without some component "active", you get an exponential number of possible way to place things, and the cost for those combinations is *not* an ordered function: if all predecessors of a block have some component active, then this block itself does not need a prologue. I get around that by making the cost function ordered, that is, possibly overestimating the cost of nodes that are the dest of a cross-jump; in the first version of the patch, by always using the execution frequency of a node (so, not considering that a prologue there does not cost anything for edges where the predecessor already has that component active); and in the second version of the patch, that, but do subtract the cost from backedges (which makes it clearer that loops are handled correctly, because the loop header generally has lower cost than the nodes in the loop body). Segher