From patchwork Fri May 31 20:18:16 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jeff Law X-Patchwork-Id: 248008 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id F1D552C007C for ; Sat, 1 Jun 2013 06:18:33 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :message-id:date:from:mime-version:to:subject:content-type; q= dns; s=default; b=Ehr2Dp73wlb6+JzkCZIyP/meJl9QHizbi/H2neQhsmTQsh pwsPSZFMilu3HInMg/By3xkwTkKt5HPGSLit7eXQ8esekPj9etViWaoEn4dwQcbi xIKDgAwnMuWoGVB9OSdsnL87qPn/IywtEDESZ8DYiiWy3KM0XjA3uoZTqtDLQ= 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 :message-id:date:from:mime-version:to:subject:content-type; s= default; bh=UgnEUT3jyxor7Buv2i2l0JIJI8k=; b=n4T6YcQOzKNOSNAEbF+h LpVZTfkedIRTChvuYQ+r1pwBu6//UNHlckhZfTwx6bRtPLqg0M/6STht1uvOnImP isHXU/ZGOjshUHjHnjvtdh4Z0QSHd9VwgSVa7B36OpeAcvf3KomMAipc5syZscOY 8mZyDdmbVd6oGFDGRY0t0vw= Received: (qmail 3290 invoked by alias); 31 May 2013 20:18:26 -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 3264 invoked by uid 89); 31 May 2013 20:18:20 -0000 X-Spam-SWARE-Status: No, score=-7.2 required=5.0 tests=AWL, BAYES_00, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, RP_MATCHES_RCVD, SPF_HELO_PASS, SPF_PASS, TW_TM autolearn=ham version=3.3.1 Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Fri, 31 May 2013 20:18:19 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r4VKIHYI005208 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Fri, 31 May 2013 16:18:18 -0400 Received: from stumpy.slc.redhat.com (ovpn-113-97.phx2.redhat.com [10.3.113.97]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r4VKIHrg014093 for ; Fri, 31 May 2013 16:18:17 -0400 Message-ID: <51A90588.5080807@redhat.com> Date: Fri, 31 May 2013 14:18:16 -0600 From: Jeff Law User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130402 Thunderbird/17.0.5 MIME-Version: 1.0 To: gcc-patches Subject: [PATCH] Improve folding of bitwise ops on booleans X-Virus-Found: No This is an implementation to fix a missed optimization pointed out to me by Kai. In all these examples, assume a & b are single bit types. ~a && b --> a < b a && ~b --> b < a ~a || b --> a <= b a && ~b --> b <= a This happens with some regularity in GCC itself, though it's not as pervasive as some of the other missed optimizations I've run into. This could have gone into fold-const.c or tree-forwprop. fold-const.c isn't as useful as would need to see the entire expression as a single tree node. tree-forwprop.c can follow the use-def links and discover more opportunities even when the expressions span two source statements or are exposed by other optimizations. Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for the trunk? commit 2b61de6f70576105fe6ada31618db23857f9c902 Author: Jeff Law Date: Fri May 31 14:16:27 2013 -0600 * tree-ssa-forwprop.c (simplify_bitwise_binary_boolean): New * function. (simplify_bitwise_binary): Use it to simpify certain binary ops on booleans. * gcc.dg/tree-ssa/forwprop-27.c: New test. diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 396111e..7f027b0 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2013-05-31 Jeff Law + + * tree-ssa-forwprop.c (simplify_bitwise_binary_boolean): New function. + (simplify_bitwise_binary): Use it to simpify certain binary ops on + booleans. + 2013-05-28 Steve Ellcey * config/mips/mips-cpus.def (mips32r2): Change processor type. diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 869371a..6f80afb 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2013-05-31 Jeff Law + + * gcc.dg/tree-ssa/forwprop-27.c: New test. + 2013-05-28 Balaji V. Iyer * c-c++-common/cilk-plus/AN/array_test1.c: New test. diff --git a/gcc/testsuite/gcc.dg/tree-ssa/forwprop-27.c b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-27.c new file mode 100644 index 0000000..75e935d --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/forwprop-27.c @@ -0,0 +1,78 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1" } */ + +extern char * frob (void); +extern _Bool testit(void); + +test (int code) +{ + char * temp = frob();; + int rotate = (code == 22); + if (temp == 0 && !rotate) + oof(); +} + +test_2 (int code) +{ + char * temp = frob(); + int rotate = (code == 22); + if (!rotate && temp == 0) + oof(); +} + + +test_3 (int code) +{ + char * temp = frob(); + int rotate = (code == 22); + if (!rotate || temp == 0) + oof(); +} + + +test_4 (int code) +{ + char * temp = frob(); + int rotate = (code == 22); + if (temp == 0 || !rotate) + oof(); +} + + +test_5 (int code) +{ + _Bool temp = testit();; + _Bool rotate = (code == 22); + if (temp == 0 && !rotate) + oof(); +} + +test_6 (int code) +{ + _Bool temp = testit(); + _Bool rotate = (code == 22); + if (!rotate && temp == 0) + oof(); +} + + +test_7 (int code) +{ + _Bool temp = testit(); + _Bool rotate = (code == 22); + if (!rotate || temp == 0) + oof(); +} + + +test_8 (int code) +{ + _Bool temp = testit(); + _Bool rotate = (code == 22); + if (temp == 0 || !rotate) + oof(); +} + +/* { dg-final { scan-tree-dump-times "Replaced" 8 "forwprop1"} } */ + + diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c index 6043d31..8c3f08b 100644 --- a/gcc/tree-ssa-forwprop.c +++ b/gcc/tree-ssa-forwprop.c @@ -1870,6 +1870,45 @@ hoist_conversion_for_bitop_p (tree to, tree from) return false; } +/* GSI points to a statement of the form + + result = OP0 CODE OP1 + + Where OP0 and OP1 are single bit SSA_NAMEs and CODE is either + BIT_AND_EXPR or BIT_IOR_EXPR. + + If OP0 is fed by a bitwise negation of another single bit SSA_NAME, + then we can simplify the two statements into a single LT_EXPR or LE_EXPR + when code is BIT_AND_EXPR and BIT_IOR_EXPR respectively. + + If a simplification is mode, return TRUE, else return FALSE. */ +static bool +simplify_bitwise_binary_boolean (gimple_stmt_iterator *gsi, + enum tree_code code, + tree op0, tree op1) +{ + gimple op0_def_stmt = SSA_NAME_DEF_STMT (op0); + + if (!is_gimple_assign (op0_def_stmt) + || (gimple_assign_rhs_code (op0_def_stmt) != BIT_NOT_EXPR)) + return false; + + tree x = gimple_assign_rhs1 (op0_def_stmt); + if (TREE_CODE (x) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (x)) + && TYPE_PRECISION (TREE_TYPE (x)) == 1) + { + gimple stmt = gsi_stmt (*gsi); + gimple_assign_set_rhs1 (stmt, x); + gimple_assign_set_rhs2 (stmt, op1); + gimple_assign_set_rhs_code (stmt, code == BIT_AND_EXPR ? LT_EXPR : LE_EXPR); + update_stmt (gsi_stmt (*gsi)); + return true; + } + return false; + +} + /* Simplify bitwise binary operations. Return true if a transformation applied, otherwise return false. */ @@ -2118,8 +2157,26 @@ simplify_bitwise_binary (gimple_stmt_iterator *gsi) return true; } } - } + /* If arg1 and arg2 are booleans (or any single bit type) + then try to simplify: + + (~X & Y) -> X < Y + (X & ~Y) -> Y < X + (~X | Y) -> X <= Y + (X | ~Y) -> Y <= X */ + if (TREE_CODE (arg1) == SSA_NAME + && TREE_CODE (arg2) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (arg1)) + && TYPE_PRECISION (TREE_TYPE (arg1)) == 1 + && TYPE_PRECISION (TREE_TYPE (arg2)) == 1) + { + if (simplify_bitwise_binary_boolean (gsi, code, arg1, arg2)) + return true; + if (simplify_bitwise_binary_boolean (gsi, code, arg2, arg1)) + return true; + } + } return false; }