From patchwork Tue Jul 25 08:22:38 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Monakov X-Patchwork-Id: 793257 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-458854-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="s2NOM1so"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3xGrq54SF2z9s1h for ; Tue, 25 Jul 2017 18:23:28 +1000 (AEST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type; q=dns; s=default; b=koarS6521lXxOg4e bqyb4bckTdGVAeKABpVmd1LGPmCU+VXCO9gLb91J779v4/quLeldphsMpZWpSG2b jq5eIP8HZ2dMPfNcTTGxPRlZkGvBJN06lYeSr127Jnp2qxcNKwz4UTqVqRwKMi0f NPqOcG80iCJMyN7CuHkity5/Aio= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:in-reply-to:message-id:references :mime-version:content-type; s=default; bh=DAhEPlBKH7ugOm+pheep45 Fbhvw=; b=s2NOM1so8/rvN9lg18cTVgMRibTIxmpyq0TvjcMuh1tkwAlraBPDRy evLdTjhJqZoIyxLUmBJsufjrswwh1/CpYtjm2yzjeYmrakmBVxrE+mK5Zb9Cljwf +V70LXeimTAF2DmhLCLUnkUmdqJ0mlnnISvGBtRX51MeBHlmVIIZk= Received: (qmail 111310 invoked by alias); 25 Jul 2017 08:23:19 -0000 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 Received: (qmail 110197 invoked by uid 89); 25 Jul 2017 08:23:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.7 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RP_MATCHES_RCVD, SPF_PASS autolearn=ham version=3.3.2 spammy= X-HELO: smtp.ispras.ru Received: from bran.ispras.ru (HELO smtp.ispras.ru) (83.149.199.196) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 25 Jul 2017 08:23:15 +0000 Received: from monopod.intra.ispras.ru (monopod.intra.ispras.ru [10.10.3.121]) by smtp.ispras.ru (Postfix) with ESMTP id 9B9D95FB34; Tue, 25 Jul 2017 11:23:11 +0300 (MSK) Date: Tue, 25 Jul 2017 11:22:38 +0300 (MSK) From: Alexander Monakov To: Jeff Law cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Optimize BB sorting in domwalk In-Reply-To: <63efcbc4-f439-ad52-d21c-eeed8ea8b096@redhat.com> Message-ID: References: <20170724112952.9218-1-amonakov@ispras.ru> <63efcbc4-f439-ad52-d21c-eeed8ea8b096@redhat.com> User-Agent: Alpine 2.20.13 (LNX 116 2015-12-14) MIME-Version: 1.0 On Mon, 24 Jul 2017, Jeff Law wrote: > As Uli noted, we should be using std::swap. > > Can you please repost ? * domwalk.c (cmp_bb_postorder): Simplify. (sort_bbs_postorder): New function. Use it... (dom_walker::walk): ...here to optimize common cases. --- gcc/domwalk.c | 53 ++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 36 insertions(+), 17 deletions(-) diff --git a/gcc/domwalk.c b/gcc/domwalk.c index a0daae6b2d8..df51b8c4451 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -128,19 +128,46 @@ along with GCC; see the file COPYING3. If not see which is currently an abstraction over walking tree statements. Thus the dominator walker is currently only useful for trees. */ +/* Reverse postorder index of each basic block. */ static int *bb_postorder; static int cmp_bb_postorder (const void *a, const void *b) { - basic_block bb1 = *(basic_block *)const_cast(a); - basic_block bb2 = *(basic_block *)const_cast(b); - if (bb1->index == bb2->index) - return 0; + basic_block bb1 = *(const basic_block *)(a); + basic_block bb2 = *(const basic_block *)(b); + int n1 = bb_postorder[bb1->index], n2 = bb_postorder[bb2->index]; /* Place higher completion number first (pop off lower number first). */ - if (bb_postorder[bb1->index] > bb_postorder[bb2->index]) - return -1; - return 1; + return (n1 < n2) - (n1 > n2); +} + +/* Permute array BBS of N basic blocks in postorder, + i.e. by descending number in BB_POSTORDER array. */ + +static void +sort_bbs_postorder (basic_block *bbs, int n) +{ + if (__builtin_expect (n == 2, true)) + { + basic_block bb0 = bbs[0], bb1 = bbs[1]; + if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) + bbs[0] = bb1, bbs[1] = bb0; + } + else if (__builtin_expect (n == 3, true)) + { + basic_block bb0 = bbs[0], bb1 = bbs[1], bb2 = bbs[2]; + if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) + std::swap (bb0, bb1); + if (bb_postorder[bb1->index] < bb_postorder[bb2->index]) + { + std::swap (bb1, bb2); + if (bb_postorder[bb0->index] < bb_postorder[bb1->index]) + std::swap (bb0, bb1); + } + bbs[0] = bb0, bbs[1] = bb1, bbs[2] = bb2; + } + else + qsort (bbs, n, sizeof *bbs, cmp_bb_postorder); } /* Constructor for a dom walker. @@ -284,16 +311,8 @@ dom_walker::walk (basic_block bb) for (dest = first_dom_son (m_dom_direction, bb); dest; dest = next_dom_son (m_dom_direction, dest)) worklist[sp++] = dest; - if (m_dom_direction == CDI_DOMINATORS) - switch (sp - saved_sp) - { - case 0: - case 1: - break; - default: - qsort (&worklist[saved_sp], sp - saved_sp, - sizeof (basic_block), cmp_bb_postorder); - } + if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS) + sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp); } /* NULL is used to mark pop operations in the recursion stack. */ while (sp > 0 && !worklist[sp - 1])