From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31249 invoked by alias); 21 Oct 2004 10:53:38 -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 31236 invoked from network); 21 Oct 2004 10:53:36 -0000 Received: from unknown (HELO polimi.it) (131.175.12.3) by sourceware.org with SMTP; 21 Oct 2004 10:53:36 -0000 Received: from gnu.org (paride.rett.polimi.it [131.175.65.135]) by polimi.it (8.13.1/8.13.1) with ESMTP id i9LArY1q007872; Thu, 21 Oct 2004 12:53:35 +0200 Message-ID: <4177967C.9050709@gnu.org> Date: Thu, 21 Oct 2004 10:54:00 -0000 From: Paolo Bonzini User-Agent: Mozilla Thunderbird 0.5 (Windows/20040207) MIME-Version: 1.0 To: Zdenek Dvorak CC: Andrew MacLeod , gcc-patches Subject: Re: [ssaupdate] Local dominance info References: <20041019215129.GA29721@atrey.karlin.mff.cuni.cz> <1098279112.5695.3918.camel@pain> <41778CA3.1050702@gnu.org> <20041021102555.GA7330@atrey.karlin.mff.cuni.cz> In-Reply-To: <20041021102555.GA7330@atrey.karlin.mff.cuni.cz> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-PMX-Version: 4.7.0.111621, Antispam-Engine: 2.0.1.0, Antispam-Data: 2004.10.20.7 X-PerlMx-Spam: Gauge=, Probability=10%, Report='LINES_OF_YELLING_3 0.671, __CT 0, __CTE 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __LINES_OF_YELLING 0, __MIME_VERSION 0, __SANE_MSGID 0' X-SW-Source: 2004-10/txt/msg01820.txt.bz2 > 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). I'm thinking about some kind of local algorithm that only looks at a few neighbors and spaces them irregularly, such as S1:10 S1:10 S1:10 S1: 5 S8:11 S2:20 S2:18 S2:18 S2:18 S3:30 S3:24 S3:23 S3:23 => S6:30 => S6:28 => S6:28 S7:33 S7:33 S4:40 S4:36 S4:42 S4:42 S5:50 S5:50 S5:50 S5:50 The algorithm could iterate until it guarantees a spacing of at least a few units between two instructions (2 is enough of course, but I think it gives bad behavior). Graph layout algorithms usually work by simulating spring forces between nodes. Something similar can probably be done in this case quite efficiently. Paolo