From patchwork Wed Jul 7 13:31:27 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Makarov X-Patchwork-Id: 58119 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 B7B0CB6F0E for ; Wed, 7 Jul 2010 23:30:09 +1000 (EST) Received: (qmail 30868 invoked by alias); 7 Jul 2010 13:30:05 -0000 Received: (qmail 30800 invoked by uid 22791); 7 Jul 2010 13:30:03 -0000 X-SWARE-Spam-Status: No, hits=-5.1 required=5.0 tests=AWL, BAYES_05, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 07 Jul 2010 13:29:58 +0000 Received: from int-mx08.intmail.prod.int.phx2.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.21]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o67DTuoQ001987 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 7 Jul 2010 09:29:56 -0400 Received: from toll.yyz.redhat.com (toll.yyz.redhat.com [10.15.16.165]) by int-mx08.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o67DTtwX018813; Wed, 7 Jul 2010 09:29:56 -0400 Message-ID: <4C3481AF.10503@redhat.com> Date: Wed, 07 Jul 2010 09:31:27 -0400 From: Vladimir Makarov User-Agent: Thunderbird 2.0.0.23 (X11/20090825) MIME-Version: 1.0 To: gcc-patches CC: Jeffrey Law Subject: IRA improvements 2/4 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 The following patch speeds up some IRA code by compressing live ranges even more. The idea that if we have several subsequent deaths (or births) and there are no births (or deaths) between them, we can use one point for all these deaths (or births). Is the patch ok to commit the patch to the trunk? 2010-07-07 Vladimir Makarov * ira-live.c: Include sbitmap.h. (remove_some_program_points_and_update_live_ranges): Use sbitmaps. Compress live ranges even more. --- ira-lives.c 2010-07-06 11:37:23.000000000 -0400 +++ /home/cygnus/vmakarov/build1/ira-improv/gcc/gcc/ira-lives.c 2010-07-01 13:45:14.000000000 -0400 @@ -36,6 +36,7 @@ along with GCC; see the file COPYING3. #include "toplev.h" #include "params.h" #include "df.h" +#include "sbitmap.h" #include "sparseset.h" #include "ira-int.h" @@ -1203,26 +1204,44 @@ remove_some_program_points_and_update_li ira_allocno_t a; ira_allocno_iterator ai; live_range_t r; - bitmap born_or_died; - bitmap_iterator bi; - - born_or_died = ira_allocate_bitmap (); + sbitmap born_or_dead, born, dead; + sbitmap_iterator sbi; + bool born_p, dead_p, prev_born_p, prev_dead_p; + + born = sbitmap_alloc (ira_max_point); + dead = sbitmap_alloc (ira_max_point); + sbitmap_zero (born); + sbitmap_zero (dead); FOR_EACH_ALLOCNO (a, ai) { for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next) { ira_assert (r->start <= r->finish); - bitmap_set_bit (born_or_died, r->start); - bitmap_set_bit (born_or_died, r->finish); + SET_BIT (born, r->start); + SET_BIT (dead, r->finish); } } + born_or_dead = sbitmap_alloc (ira_max_point); + sbitmap_a_or_b (born_or_dead, born, dead); map = (int *) ira_allocate (sizeof (int) * ira_max_point); - n = 0; - EXECUTE_IF_SET_IN_BITMAP(born_or_died, 0, i, bi) + n = -1; + prev_born_p = prev_dead_p = false; + EXECUTE_IF_SET_IN_SBITMAP (born_or_dead, 0, i, sbi) { - map[i] = n++; + born_p = TEST_BIT (born, i); + dead_p = TEST_BIT (dead, i); + if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p) + || (prev_dead_p && ! prev_born_p && dead_p && ! born_p)) + map[i] = n; + else + map[i] = ++n; + prev_born_p = born_p; + prev_dead_p = dead_p; } - ira_free_bitmap (born_or_died); + sbitmap_free (born_or_dead); + sbitmap_free (born); + sbitmap_free (dead); + n++; if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) fprintf (ira_dump_file, "Compressing live ranges: from %d to %d - %d%%\n", ira_max_point, n, 100 * n / ira_max_point);