From patchwork Wed Jun 9 09:51:37 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jan Hubicka X-Patchwork-Id: 55065 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 C5467B7D5C for ; Wed, 9 Jun 2010 19:51:47 +1000 (EST) Received: (qmail 20197 invoked by alias); 9 Jun 2010 09:51:45 -0000 Received: (qmail 20188 invoked by uid 22791); 9 Jun 2010 09:51:45 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from nikam-dmz.ms.mff.cuni.cz (HELO nikam.ms.mff.cuni.cz) (195.113.20.16) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 09 Jun 2010 09:51:39 +0000 Received: by nikam.ms.mff.cuni.cz (Postfix, from userid 16202) id CD3639AC808; Wed, 9 Jun 2010 11:51:37 +0200 (CEST) Date: Wed, 9 Jun 2010 11:51:37 +0200 From: Jan Hubicka To: gcc-patches@gcc.gnu.org Subject: Speedup bitmap iterators Message-ID: <20100609095137.GA18910@kam.mff.cuni.cz> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.18 (2008-05-17) 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 Hi, this patch avoid dififcult to predict branch in bmp walking. Improving: :static inline bool :bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no) :{ : /* If our current word is nonzero, it contains the bit we want. */ 1551 0.1115 : if (bi->bits) : { : next_bit: 7282 0.5237 : while (!(bi->bits & 1)) : { 5312 0.3820 : bi->bits >>= 1; 7904 0.5685 : *bit_no += 1; : } : return true; : } to: : bool :bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no) :{ : /* If our current word is nonzero, it contains the bit we want. */ 1274 0.0973 : if (bi->bits) : { : next_bit: :#if (GCC_VERSION >= 3004) : { 1106 0.0845 : unsigned int n = __builtin_ctzl (bi->bits); : gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD)); 1811 0.1384 : bi->bits >>= n; 1892 0.1446 : *bit_no += n; : } :#else The code (including checking for 3.4) is the same as one present in bitmap_first_bit already. Bootstrapped/regtested x86_64-linux, OK? Honza * bitmap.h (bmp_iter_set, bmp_iter_and, bmp_iter_and_compl): Use __builtin_ctzl where possible. Index: bitmap.h =================================================================== --- bitmap.h (revision 160447) +++ bitmap.h (working copy) @@ -396,11 +396,20 @@ bmp_iter_set (bitmap_iterator *bi, unsig if (bi->bits) { next_bit: +#if (GCC_VERSION >= 3004) + { + unsigned int n = __builtin_ctzl (bi->bits); + gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD)); + bi->bits >>= n; + *bit_no += n; + } +#else while (!(bi->bits & 1)) { bi->bits >>= 1; *bit_no += 1; } +#endif return true; } @@ -443,11 +452,20 @@ bmp_iter_and (bitmap_iterator *bi, unsig if (bi->bits) { next_bit: +#if (GCC_VERSION >= 3004) + { + unsigned int n = __builtin_ctzl (bi->bits); + gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD)); + bi->bits >>= n; + *bit_no += n; + } +#else while (!(bi->bits & 1)) { bi->bits >>= 1; *bit_no += 1; } +#endif return true; } @@ -510,11 +528,20 @@ bmp_iter_and_compl (bitmap_iterator *bi, if (bi->bits) { next_bit: +#if (GCC_VERSION >= 3004) + { + unsigned int n = __builtin_ctzl (bi->bits); + gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD)); + bi->bits >>= n; + *bit_no += n; + } +#else while (!(bi->bits & 1)) { bi->bits >>= 1; *bit_no += 1; } +#endif return true; }