From patchwork Tue Aug 7 08:31:32 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 175535 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id B2CF42C008D for ; Tue, 7 Aug 2012 18:31:51 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1344933113; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:In-Reply-To:References:Date: Message-ID:Subject:From:To:Cc:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=KYs/LtwCU1oncLOqCDjZeN3AsFI=; b=K8vPj4KvD8mHmzes2iAO5i217WlMAJO7L7EaC3vEvlOm7hAV6BdRu9oDYmor7W IoUvpoq8w7k1win6L3kNZyU1T+0eHpCR/U0qips5ORXyD98gxxwGOEa6fSMfnHlT 6UI15Cdr4A8pVC2/9KTv2CoQWI+F5JJqWaxECA99PU70Q= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:MIME-Version:Received:Received:In-Reply-To:References:Date:Message-ID:Subject:From:To:Cc:Content-Type:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=QrVl0d8HpL30J1+7l4ktwaVaFdUTYoppABkXwFtlOqQ+ZqYoBHIsJsKYjf8kQC sciIwgQmUCUrv397+HNLmuUj4bRfmR913A32JerpWmG+HjHNBj+doGVUGL/4As1r v+4BBgHT6IPsBZeUc8Krv6mdCH9N+Ws25KXCkdQjvObFA=; Received: (qmail 4127 invoked by alias); 7 Aug 2012 08:31:47 -0000 Received: (qmail 4111 invoked by uid 22791); 7 Aug 2012 08:31:46 -0000 X-SWARE-Spam-Status: No, hits=-4.9 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, KHOP_RCVD_TRUST, KHOP_THREADED, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE X-Spam-Check-By: sourceware.org Received: from mail-ob0-f175.google.com (HELO mail-ob0-f175.google.com) (209.85.214.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 07 Aug 2012 08:31:33 +0000 Received: by obc16 with SMTP id 16so3952702obc.20 for ; Tue, 07 Aug 2012 01:31:32 -0700 (PDT) MIME-Version: 1.0 Received: by 10.60.24.7 with SMTP id q7mr23357108oef.54.1344328292684; Tue, 07 Aug 2012 01:31:32 -0700 (PDT) Received: by 10.76.90.71 with HTTP; Tue, 7 Aug 2012 01:31:32 -0700 (PDT) In-Reply-To: References: Date: Tue, 7 Aug 2012 10:31:32 +0200 Message-ID: Subject: Re: [patch] Use a smaller, dynamic worklist in compute_global_livein From: Richard Guenther To: Steven Bosscher Cc: GCC Patches X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On Tue, Aug 7, 2012 at 8:24 AM, Steven Bosscher wrote: > Hello, > > In the test case for PR54146, compute_global_livein allocates/frees a > worklist for >400,000 basic blocks on each invocation. And it's called > a lot, for rewrite_into_loop_closed_ssa. But the maximum number of > basic blocks ever on the work list was only ~6500. So the work list > can be much smaller most of the time. > > Bootstrapped&tested on x86_64-unknown-linux-gnu. OK for trunk? comments elsewhere about tracking vops can you fix that to s/SSA_OP_ALL_USES/SSA_OP_USE/? void -compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED) +compute_global_livein (bitmap livein, bitmap def_blocks) { - basic_block bb, *worklist, *tos; unsigned i; bitmap_iterator bi; + VEC (basic_block, heap) *worklist; - tos = worklist - = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1)); + /* Normally the work list size is bounded by the number of basic + blocks in the largest loop. We don't know this number, but we + can be fairly sure that it will be relatively small. */ + worklist = VEC_alloc (basic_block, heap, MAX (8, n_basic_blocks / 100)); I suppose if we really want to optimize this we can make worklist static so we at most grow once. (in case you want to optimize allocation overhead, not memory used). Other structures in the ssa rewriter have this kind of lifetime, too (the per-SSA name info for example). Ok with the first change, whatever you prefer on the compute_global_livein thing. Thanks, Richard. > Ciao! > Steven Index: tree-ssa-loop-manip.c =================================================================== --- tree-ssa-loop-manip.c (revision 190176) +++ tree-ssa-loop-manip.c (working copy) @@ -162,10 +162,8 @@ add_exit_phis_var (tree var, bitmap live basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); bitmap_iterator bi; - if (is_gimple_reg (var)) - bitmap_clear_bit (livein, def_bb->index); - else - bitmap_set_bit (livein, def_bb->index); + gcc_checking_assert (is_gimple_reg (var)); + bitmap_clear_bit (livein, def_bb->index); !is_gimple_reg is true for virtual operand PHIs ... and at least find_uses_to_rename_stmt loops over all uses (so, I suppose given the