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: 933163 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-480264-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=linaro.org Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="e8JWFWN2"; 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 41BtHK2ztZz9s3C for ; Fri, 22 Jun 2018 19:16:45 +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 :mime-version:from:date:message-id:subject:to:content-type; q= dns; s=default; b=mY/yvJxaz4GNLiVRDpCghWgD0Ly7mhh7QZ++n3JhTgaDpB Mg5RdBVIAVCbsqEhzdvb6jJ1nZ4265QXRrnO6LAgBcefqEmV/TREXRI9Pvdn8Cb1 FhWF+sf7SFQ2pRz7FAoPmG1PNsMN1faDuVOjjD/My23zB0rg5LRnWIeEMURpQ= 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=e8JWFWN2Mma3YYkVunqd JfiHkkBmkdxVW9zkmnA2oVytS0jQVqVTyfuKfkJ+B4a0Pf7pwgdfF7j/DtKmhev/ WNYo0YKVYILHsz0C1kpQZ7LLbT7G5u1VLmAy7TIDUizMhCDhh+XNVUAghJ8eKazH nJtblk+bXDup7NU/sPTXSLQ= 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-Google-Smtp-Source: ADUXVKIPsFjaXrQJzlthxr0f6UfvZouxe7n6tYqBb9LwaDneigjLY0FKhtuqGLtdUUZu6fJOeM0Z5wx0/SfGlU5LarE= 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