From patchwork Fri Jun 22 09:14:44 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kugan Vivekanandarajah X-Patchwork-Id: 139592 Delivered-To: patch@linaro.org Received: by 2002:a2e:970d:0:0:0:0:0 with SMTP id r13-v6csp637001lji; Fri, 22 Jun 2018 02:16:49 -0700 (PDT) X-Google-Smtp-Source: ADUXVKIErI6iwym1K48BuR/1gYaWOYbxshYUPTuT6IW05D30Z7TWcZwQghPSrdm0s/QY/s/ad8NF X-Received: by 2002:a17:902:64cf:: with SMTP id y15-v6mr833649pli.53.1529659009445; Fri, 22 Jun 2018 02:16:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1529659009; cv=none; d=google.com; s=arc-20160816; b=kUc7+w/6Qwp+TQQN7oJR/w/h21Z+YZUgOlhp7NqGCgEKiXtII2cshtgRq47JR5493g SykhzD4EZy+buWfFNg9zrXcKQrgQE/3I+NWVplNll18IICP7s3e9BXcqZbuqqxWYt0ON yLgF+kCSJVxr12fBeVfIr+liW+gVPI9KUfb/l7F2Z5PrDU1FzWQAvurjQ21Qm2IQg64i Xdcqmc41oDgW27FtBu+6p/XpLn8Ht6cockydUZB/UT5T+t8WtLZweUw6Fsv7ydPgb7I4 C5Wq6CC43+0qtA70vg7CUe1mb3h/Af4cWpvhvttAsw63HPna2aJKXH3OwGlDWD8dRiJA YUBA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:mime-version:delivered-to:sender :list-help:list-post:list-archive:list-unsubscribe:list-id :precedence:mailing-list:dkim-signature:domainkey-signature :arc-authentication-results; bh=VYVlq4l5t9L5O+AbE3cXSC0cZWhK9SGNz1s8CVTmIPM=; b=nzmzJb1Gj4Le4e5X8ntAtkUzZBqZ/r8Z7GJd7EgDR8NleNOSi6yeiJ72N1dy5XH+Hn 2kSS6W/+wXw7sG4ETCXuSvgBx33brKv7zbsGbIWctTMqwkBKyVQSTShVDWH0re3KRHtE ErL/gm6YGg0S63PrF1N6wDgFl3hb75cXfjJk7rlPu+37BKGPwIB38NyKm0vJN1cxcj6e jdU2PWh/ssixm5BV4k6gnmxEFT9ZuEyuef3hXNcwlMnb+XV0OQyKQprUN3JJhhaMFjKa YkZX8d4IpHcRwKVXszk+jgdr8zbcPOEAOC5cexnaOw4Ul8JkzCjRL+RXI3KirLNBoFqm P0Dw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="q/pUtJuk"; spf=pass (google.com: domain of gcc-patches-return-480264-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="gcc-patches-return-480264-patch=linaro.org@gcc.gnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from sourceware.org (server1.sourceware.org. [209.132.180.131]) by mx.google.com with ESMTPS id z3-v6si6886003plb.246.2018.06.22.02.16.49 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 22 Jun 2018 02:16:49 -0700 (PDT) Received-SPF: pass (google.com: domain of gcc-patches-return-480264-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) client-ip=209.132.180.131; Authentication-Results: mx.google.com; dkim=pass header.i=@gcc.gnu.org header.s=default header.b="q/pUtJuk"; spf=pass (google.com: domain of gcc-patches-return-480264-patch=linaro.org@gcc.gnu.org designates 209.132.180.131 as permitted sender) smtp.mailfrom="gcc-patches-return-480264-patch=linaro.org@gcc.gnu.org"; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=linaro.org DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:from:date:message-id:subject:to:content-type; q= dns; s=default; b=KH4FbD2j8AfiMfWe3dBgrtNgR7UctnuAZJDpCoprDl0M1R 1xZzmoM55+jrlvr8cdt8IY4ocVLNi7sLsnzEwHQACxtIirxLUfMHjUxRN033Huz9 zlHS6Rom0z9EiqUQDaqTy5qWo9oLb0i1cdt7pC8sy79feSeSW+RsCOpGSAXsU= 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 :mime-version:from:date:message-id:subject:to:content-type; s= default; bh=uXsGDzSjpg8LtyRfSwu0xcc0IpI=; b=q/pUtJuk9bWLT9Nax500 mGu52makljVGRySF6jXd2H2Vb/4aQvy2gxTVdUcjNEXcyf6ckIkmSIded/FZHRUz mB3Wl2kHjzzuwPeoZ8LiOPrrL9qJWMNtyYZGfsRcP808tBPd2NrbytDlAtHF+FUu D4P0nKj9PhPvgYlzV1yNsxU= Received: (qmail 41451 invoked by alias); 22 Jun 2018 09:16:36 -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 40997 invoked by uid 89); 22 Jun 2018 09:15:43 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.5 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=fndecl, gimple_get_lhs X-HELO: mail-lf0-f48.google.com Received: from mail-lf0-f48.google.com (HELO mail-lf0-f48.google.com) (209.85.215.48) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 22 Jun 2018 09:15:37 +0000 Received: by mail-lf0-f48.google.com with SMTP id j26-v6so197890lfb.11 for ; Fri, 22 Jun 2018 02:15:27 -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:from:date:message-id:subject:to; bh=ILW7lrmXaPhVg2Tz3VOPSaa4LYBGffXQFZN2pXntKM8=; b=e9vTRYXv74hdplWestS5kOdJcd0buJeNYx9Dt5P3mCuwnm3rmA4WAl8CduBKalULrD JGX4ZSRq1F5tGEtDajd98nT0RZKm+wlK9SV9vtE30XvKcOUIJxA2jnDmJLKjWxz9o62o +n7JtZsAcVgxw+BvyGODNTzUTKt7yOkdrp2nqnqVFgrwGQmDZYUR28fOq+kL+rqx82Bc bMMvfb4XZ8/I99AjUzHXbycB9/L25LAzbyJMsjWYf2TjQVEidXcL2Vlxxj0mGpkPPent qEYY1w3V93Cvg5BAmzqimG0B3c0oDZXmxzYsPHHI9a7NaBrpxjgsSneWOsMC8c24YCNO 6izw== X-Gm-Message-State: APt69E01CDPlw/TaCtlPZJPXdSj8vOKFde0gFLwTUXsgR1usoNEUyFHy hKkveptf5RWSde4Bvbbcf+HEmcV+yQNJlf/xRYPRhviVTIk= X-Received: by 2002:a19:8fd4:: with SMTP id s81-v6mr197662lfk.118.1529658925366; Fri, 22 Jun 2018 02:15:25 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a2e:1302:0:0:0:0:0 with HTTP; Fri, 22 Jun 2018 02:14:44 -0700 (PDT) From: Kugan Vivekanandarajah Date: Fri, 22 Jun 2018 19:14:44 +1000 Message-ID: Subject: [PATCH 3/3][POPCOUNT] Remove unnecessary if condition in phiopt To: GCC Patches X-IsSubscribed: yes gcc/ChangeLog: 2018-06-22 Kugan Vivekanandarajah * tree-ssa-phiopt.c (cond_removal_in_popcount_pattern): New. (tree_ssa_phiopt_worker): Call cond_removal_in_popcount_pattern. gcc/testsuite/ChangeLog: 2018-06-22 Kugan Vivekanandarajah * gcc.dg/tree-ssa/popcount3.c: New test. >From fa2cca6b186b70668a3334c23ea4b906dac454d4 Mon Sep 17 00:00:00 2001 From: Kugan Vivekanandarajah Date: Fri, 22 Jun 2018 14:16:21 +1000 Subject: [PATCH 3/3] improve phiopt for builtin popcount Change-Id: Id1a5997c78fc3ceded3ed7fb0c544ce2bd1a2b34 --- gcc/testsuite/gcc.dg/tree-ssa/popcount3.c | 15 ++++ gcc/tree-ssa-phiopt.c | 113 ++++++++++++++++++++++++++++++ 2 files changed, 128 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/popcount3.c diff --git a/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c new file mode 100644 index 0000000..293beb9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/popcount3.c @@ -0,0 +1,15 @@ +/* { dg-do run } */ +/* { dg-options "-O2 -fdump-tree-phiopt3 -fdump-tree-optimized" } */ + +int PopCount (long b) { + int c = 0; + + while (b) { + b &= b - 1; + c++; + } + return c; +} + +/* { dg-final { scan-tree-dump-times "__builtin_popcount" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "if" 0 "phiopt3" } } */ diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c index 8e94f6a..1db5226 100644 --- a/gcc/tree-ssa-phiopt.c +++ b/gcc/tree-ssa-phiopt.c @@ -57,6 +57,8 @@ static bool minmax_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); static bool abs_replacement (basic_block, basic_block, edge, edge, gimple *, tree, tree); +static bool cond_removal_in_popcount_pattern (basic_block, basic_block, + edge, edge, gimple *, tree, tree); static bool cond_store_replacement (basic_block, basic_block, edge, edge, hash_set *); static bool cond_if_else_store_replacement (basic_block, basic_block, basic_block); @@ -332,6 +334,9 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads) cfgchanged = true; else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; + else if (cond_removal_in_popcount_pattern (bb, bb1, e1, e2, + phi, arg0, arg1)) + cfgchanged = true; else if (minmax_replacement (bb, bb1, e1, e2, phi, arg0, arg1)) cfgchanged = true; } @@ -1516,6 +1521,114 @@ minmax_replacement (basic_block cond_bb, basic_block middle_bb, return true; } +/* Convert + + + if (b_4(D) != 0) + goto + else + goto + + + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + + + c_12 = PHI <0(2), _9(3)> + + Into + + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + + + c_12 = PHI <_9(2)> +*/ + +static bool +cond_removal_in_popcount_pattern (basic_block cond_bb, basic_block middle_bb, + edge e0 ATTRIBUTE_UNUSED, edge e1 ATTRIBUTE_UNUSED, + gimple *phi, tree arg0, tree arg1) +{ + gimple *cond; + gimple_stmt_iterator gsi; + gimple *popcount; + gimple *cast; + tree rhs, lhs, arg; + unsigned stmt_count = 0; + + /* Check that + _2 = (unsigned long) b_4(D); + _9 = __builtin_popcountl (_2); + are the only stmts in the middle_bb. */ + + for (gsi = gsi_start_bb (middle_bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (is_gimple_debug (stmt)) + continue; + stmt_count++; + } + if (stmt_count != 2) + return false; + + cast = first_stmt (middle_bb); + popcount = last_stmt (middle_bb); + if (popcount == NULL || cast == NULL) + return false; + + /* Check that we have a popcount builtin. */ + if (!is_gimple_call (popcount) + || !gimple_call_builtin_p (popcount, BUILT_IN_NORMAL)) + return false; + tree fndecl = gimple_call_fndecl (popcount); + if ((DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNT) + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTL) + && (DECL_FUNCTION_CODE (fndecl) != BUILT_IN_POPCOUNTLL)) + return false; + + /* Check that we have a cast prior to that. */ + if (gimple_code (cast) != GIMPLE_ASSIGN + || gimple_assign_rhs_code (cast) != NOP_EXPR) + return false; + + rhs = gimple_assign_rhs1 (cast); + lhs = gimple_get_lhs (popcount); + arg = gimple_call_arg (popcount, 0); + + /* Result of the cast stmt is the argument to the builtin. */ + if (arg != gimple_assign_lhs (cast)) + return false; + + if (lhs != arg0 + && lhs != arg1) + return false; + + cond = last_stmt (cond_bb); + + /* Cond_bb has a check for b_4 != 0 before calling the popcount + builtin. */ + if (gimple_code (cond) != GIMPLE_COND + || gimple_cond_code (cond) != NE_EXPR + || TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME + || rhs != gimple_cond_lhs (cond)) + return false; + + /* Remove the popcount builtin and cast stmt. */ + gsi = gsi_for_stmt (popcount); + gsi_remove (&gsi, true); + gsi = gsi_for_stmt (cast); + gsi_remove (&gsi, true); + + /* And insert the popcount builtin and cast stmt before the cond_bb. */ + gsi = gsi_last_bb (cond_bb); + gsi_insert_before (&gsi, popcount, GSI_NEW_STMT); + gsi_insert_before (&gsi, cast, GSI_NEW_STMT); + + /* Now update the PHI and remove unneeded bbs. */ + replace_phi_edge_with_variable (cond_bb, e1, phi, lhs); + return true; +} /* The function absolute_replacement does the main work of doing the absolute replacement. Return true if the replacement is done. Otherwise return -- 2.7.4