From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 80082 invoked by alias); 1 Feb 2018 12:21:58 -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 80064 invoked by uid 89); 1 Feb 2018 12:21:57 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.2 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_NONE,SPF_PASS autolearn=ham version=3.3.2 spammy=business X-HELO: mail-lf0-f51.google.com Received: from mail-lf0-f51.google.com (HELO mail-lf0-f51.google.com) (209.85.215.51) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 01 Feb 2018 12:21:56 +0000 Received: by mail-lf0-f51.google.com with SMTP id k19so25941351lfj.1 for ; Thu, 01 Feb 2018 04:21:55 -0800 (PST) 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=vFJWfpq/Nevli/9eynXkp1sYfXBTt6ufY7P9W082/64=; b=e9w+sY5/Tyn9KOWXobsCpmWciND1qAdgyIwV0WdGcx3HWVkvPZPVGufxlMIyR/jHOH NkA5NlePc8/BxIrlDkWOyXSLAhUOw3g815UPKZ1zFptcTNfBrZZdssNqsbLqM7+c3Y/k 8Ara9bTlEUEblkJZokBWe58YBGPdmGNuFdNU7FR0VOk/enCIaJIPwZsx1RoiKqyQtoXi jONcmCS3mSNZvAAe2QZIG6H1nKq6tOrwrAjZrLz1ZT/Yu6dM/qvTWSuNQNTGgQdhtaKL ZH86A1WssCdrg7G5lDuI7Dn0rZBvxYJPzDiIewOf7oVZOqmIhr8nix9OmRSimSP/gm5I M6IQ== X-Gm-Message-State: AKwxyte8mk7pFd5aTgqIWJWOEwvSuHFCOZOHjrW4bLL6PJ+zugeXy9Us aWrCO7fSsjkyZIXVxCGULPpkkb+JXw/Rcr4ZmP8= X-Google-Smtp-Source: AH8x224BDTb7g+uvjL8oFWNEykQ6x5FJc3ReHwp0oiMc3mA+4k5iI6Be/Z3gXWL8VAsgOkjwlwHlDz+DuRNQurTgaeY= X-Received: by 10.25.215.72 with SMTP id o69mr22047425lfg.103.1517487713908; Thu, 01 Feb 2018 04:21:53 -0800 (PST) MIME-Version: 1.0 Received: by 10.46.51.21 with HTTP; Thu, 1 Feb 2018 04:21:53 -0800 (PST) In-Reply-To: References: From: Richard Biener Date: Thu, 01 Feb 2018 12:21:00 -0000 Message-ID: Subject: Re: [RFC][PR82479] missing popcount builtin detection To: Kugan Vivekanandarajah Cc: GCC Patches Content-Type: text/plain; charset="UTF-8" X-IsSubscribed: yes X-SW-Source: 2018-02/txt/msg00029.txt.bz2 On Thu, Feb 1, 2018 at 5:07 AM, Kugan Vivekanandarajah wrote: > Hi Richard, > > On 31 January 2018 at 21:39, Richard Biener wrote: >> On Wed, Jan 31, 2018 at 11:28 AM, Kugan Vivekanandarajah >> wrote: >>> Hi Richard, >>> >>> Thanks for the review. >>> On 25 January 2018 at 20:04, Richard Biener wrote: >>>> On Wed, Jan 24, 2018 at 10:56 PM, Kugan Vivekanandarajah >>>> wrote: >>>>> Hi All, >>>>> >>>>> Here is a patch for popcount builtin detection similar to LLVM. I >>>>> would like to queue this for review for next stage 1. >>>>> >>>>> 1. This is done part of loop-distribution and effective for -O3 and above. >>>>> 2. This does not distribute loop to detect popcount (like >>>>> memcpy/memmove). I dont think that happens in practice. Please correct >>>>> me if I am wrong. >>>> >>>> But then it has no business inside loop distribution but instead is >>>> doing final value >>>> replacement, right? You are pattern-matching the whole loop after all. I think >>>> final value replacement would already do the correct thing if you >>>> teached number of >>>> iteration analysis that niter for >>>> >>>> [local count: 955630224]: >>>> # b_11 = PHI >>>> _1 = b_11 + -1; >>>> b_8 = _1 & b_11; >>>> if (b_8 != 0) >>>> goto ; [89.00%] >>>> else >>>> goto ; [11.00%] >>>> >>>> [local count: 850510900]: >>>> goto ; [100.00%] >>> >>> I am looking into this approach. What should be the scalar evolution >>> for b_8 (i.e. b & (b -1) in a loop) should be? This is not clear to me >>> and can this be represented with the scev? >> >> No, it's not affine and thus cannot be represented. You only need the >> scalar evolution of the counting IV which is already handled and >> the number of iteration analysis needs to handle the above IV - this >> is the missing part. > Thanks for the clarification. I am now matching this loop pattern in > number_of_iterations_exit when number_of_iterations_exit_assumptions > fails. If the pattern matches, I am inserting the _builtin_popcount in > the loop preheater and setting the loop niter with this. This will be > used by the final value replacement. Is this what you wanted? No, you shouldn't insert a popcount stmt but instead the niter GENERIC tree should be a CALL_EXPR to popcount with the appropriate argument. > In general, there is also a condition gating the loop like > > if (b_4 != 0) > goto loop; > else > end: > > This of course will not be removed by final value replacement. Since > popcount (0) is defined, this is redundant and could be removed but > not removed. Yeah, that's probably sth for another pass though. I suppose the end: case just uses zero in which case you'll have a PHI and you can optimize if (b != 0) return popcount (b); return 0; in phiopt. Richard. > Thanks, > Kugan > >> >> Richard. >> >>> Thanks, >>> Kugan >>>> >>>> is related to popcount (b_5). >>>> >>>> Richard. >>>> >>>>> Bootstrapped and regression tested on aarch64-linux-gnu with no new regressions. >>>>> >>>>> Thanks, >>>>> Kugan >>>>> >>>>> gcc/ChangeLog: >>>>> >>>>> 2018-01-25 Kugan Vivekanandarajah >>>>> >>>>> PR middle-end/82479 >>>>> * tree-loop-distribution.c (handle_popcount): New. >>>>> (pass_loop_distribution::execute): Use handle_popcount. >>>>> >>>>> gcc/testsuite/ChangeLog: >>>>> >>>>> 2018-01-25 Kugan Vivekanandarajah >>>>> >>>>> PR middle-end/82479 >>>>> * gcc.dg/tree-ssa/popcount.c: New test.