From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 52918 invoked by alias); 25 Jul 2017 08:46:00 -0000 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 Received: (qmail 51367 invoked by uid 89); 25 Jul 2017 08:45:59 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-24.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,GIT_PATCH_0,GIT_PATCH_1,GIT_PATCH_2,GIT_PATCH_3,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 spammy=Hx-spam-relays-external:209.85.215.66, H*RU:209.85.215.66 X-HELO: mail-lf0-f66.google.com Received: from mail-lf0-f66.google.com (HELO mail-lf0-f66.google.com) (209.85.215.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 25 Jul 2017 08:45:57 +0000 Received: by mail-lf0-f66.google.com with SMTP id w199so2271179lff.2 for ; Tue, 25 Jul 2017 01:45:57 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=wYGMfjPBjt+3AgBsZfXaHyQFN1qE+PYrfXqEv8GL07o=; b=ql6+LGyNIPngmPve/oJmZvvkzBUw+cKi15rS+U155NmXhmSJb2y6hlbinA2yxX02Tz v7dqqwbAtEhhnrlvkNcRkFJSMcyo76aAMFXcpbwXDFUd/13GjHdiecOTQgpqUouSFaMs c0GbiEvOZHbP/GBPphe4/M5gmeNVhjll9U2a1UfNxaHeJqSp3/SIS3gqx2elxv+pbrXO 3vu5zCSg7v/K7JWvyLkVUZXnY6Np6RfRkq2W+slpmeXSlo/2CP0jMWx41BAQG+DpuATR iz6f8S9Imm75IDDD9aSxVbbUCJE2Ijfa+I4fR14I7isVlXY05/pOQ1Bjgsq46F7uVeDF Etsw== X-Gm-Message-State: AIVw1136SyUkYKKrhOWkKEsG33N40VY0X6uD6Ny0cdVnD5+l8uImGuQr dBRZGDHByFmfKGfMkHOkdaaKtJEPWg== X-Received: by 10.25.125.214 with SMTP id y205mr5178671lfc.3.1500972355491; Tue, 25 Jul 2017 01:45:55 -0700 (PDT) MIME-Version: 1.0 Received: by 10.25.31.134 with HTTP; Tue, 25 Jul 2017 01:45:54 -0700 (PDT) In-Reply-To: References: <20170724112952.9218-1-amonakov@ispras.ru> <63efcbc4-f439-ad52-d21c-eeed8ea8b096@redhat.com> From: Richard Biener Date: Tue, 25 Jul 2017 08:46:00 -0000 Message-ID: Subject: Re: [PATCH] Optimize BB sorting in domwalk To: Alexander Monakov Cc: Jeff Law , GCC Patches Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2017-07/txt/msg01505.txt.bz2 On Tue, Jul 25, 2017 at 10:22 AM, Alexander Monakov wrote: > 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. Ok. Note that I think vec::qsort might benefit from handling length () == 2 and domwalk might benefit from using vec::qsort if it would work on a sub-vector as we are asking for here... Richard. > --- > 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]) > -- > 2.13.3