From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16555 invoked by alias); 21 Oct 2004 10:25:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 16535 invoked from network); 21 Oct 2004 10:25:55 -0000 Received: from unknown (HELO atrey.karlin.mff.cuni.cz) (195.113.31.123) by sourceware.org with SMTP; 21 Oct 2004 10:25:55 -0000 Received: by atrey.karlin.mff.cuni.cz (Postfix, from userid 29025) id 25A9A4B410A; Thu, 21 Oct 2004 12:25:55 +0200 (CEST) Date: Thu, 21 Oct 2004 10:53:00 -0000 From: Zdenek Dvorak To: Paolo Bonzini Cc: Andrew MacLeod , gcc-patches Subject: Re: [ssaupdate] Local dominance info Message-ID: <20041021102555.GA7330@atrey.karlin.mff.cuni.cz> References: <20041019215129.GA29721@atrey.karlin.mff.cuni.cz> <1098279112.5695.3918.camel@pain> <41778CA3.1050702@gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <41778CA3.1050702@gnu.org> User-Agent: Mutt/1.5.6i X-SW-Source: 2004-10/txt/msg01819.txt.bz2 Hello, > >I think trying to keep numbered order of stmts within blocks for the > >duration of SSA is a very bad idea since most optimizations do not care. > >So you have the overhead of making sure that you keep things kosher > >everytime you ever move anything. > > Zdenek, do you have an analysis of the amortized worst-case complexity > of bsi_insert_before and bsi_insert_after? no; the algorithm is quite ad-hoc and I believe that it behaves quite badly from the theoretic point of view. It should (and seems to) behave well under "normal" workload (i.e. relatively few insertions on single place), but it of course would be better to have here something for that some upper bound could be proved (I am fairly sure it would be possible, and probably the solution would not be much more complicated than the current one). Zdenek