From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 12880 invoked by alias); 24 Aug 2011 11:12:35 -0000 Received: (qmail 12870 invoked by uid 22791); 24 Aug 2011 11:12:34 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_LOW X-Spam-Check-By: sourceware.org Received: from mail-fx0-f47.google.com (HELO mail-fx0-f47.google.com) (209.85.161.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 24 Aug 2011 11:12:15 +0000 Received: by fxg11 with SMTP id 11so960702fxg.20 for ; Wed, 24 Aug 2011 04:12:14 -0700 (PDT) Received: by 10.223.44.89 with SMTP id z25mr7160527fae.28.1314184334510; Wed, 24 Aug 2011 04:12:14 -0700 (PDT) Received: from richards-thinkpad.stglab.manchester.uk.ibm.com (gbibp9ph1--blueice3n2.emea.ibm.com [195.212.29.84]) by mx.google.com with ESMTPS id q1sm320725faa.1.2011.08.24.04.12.12 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 24 Aug 2011 04:12:13 -0700 (PDT) From: Richard Sandiford To: Bernd Schmidt Mail-Followup-To: Bernd Schmidt ,GCC Patches , richard.sandiford@linaro.org Cc: GCC Patches Subject: Re: Rename across basic block boundaries References: <4E00A296.4000306@codesourcery.com> Date: Wed, 24 Aug 2011 12:50:00 -0000 In-Reply-To: <4E00A296.4000306@codesourcery.com> (Bernd Schmidt's message of "Tue, 21 Jun 2011 15:54:30 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii 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 X-SW-Source: 2011-08/txt/msg01985.txt.bz2 Sorry, I'm find this a bit tough to review. Could you provide some overview comments somewhere to say what the new algorithm is? The comment at the head of regrename.c still describes the current bb-local algorithm. One thing though: Bernd Schmidt writes: > @@ -215,8 +306,9 @@ merge_overlapping_regs (HARD_REG_SET *ps > IOR_HARD_REG_SET (*pset, head->hard_conflicts); > EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi) > { > - du_head_p other = VEC_index (du_head_p, id_to_chain, i); > + du_head_p other = chain_from_id (i); > unsigned j = other->nregs; > + gcc_assert (other != head); > while (j-- > 0) > SET_HARD_REG_BIT (*pset, other->regno + j); > } Is this effectively cubic in the number of chains? There are O(chains) calls to merge_overlapping_regs, O(chains) nodes in the conflicts bitmap, and chain_from_id chases O(chains) merges. I realise this probably isn't a problem in practice. Just looking for reassurance. :-) Richard