From patchwork Tue Mar 11 15:50:01 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 329141 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.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id C9B7E2C00C2 for ; Wed, 12 Mar 2014 02:50:28 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; q=dns; s=default; b=kqQcRaE/eoM/mmIjEIYuq2ZYKWpO7 VeSNb9ckJwGWOHe7a90/wELemBwOPp6aTuLADX6zAiSxx8J9uHwVRsfuxA2RQOQN DJaWi4Ds81tpDUnXHAsupkIVOSFoLU7Nt8L+vIhAatiW9ppUm9LhfSBKv50eHpt+ GYl6EYZvWHKRBk= 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:date :from:to:cc:subject:message-id:reply-to:mime-version :content-type; s=default; bh=BeVcrSbQ0kceil+JojvdQT6O6os=; b=x9b /gAhKMcw6bh+W87k7nr5MQJjRpd71fqc1PsTbli8ZhONc0tGbAGFVX1Gb3ubg4M9 P6G5N05MFh2oDUXH8DosoQjbzYeF34tqEZzJFF8kR0VJF+Qv8M7WBIC07C9CGtgN 323FBWcWoc+6EkUCDqVzrFp/xi9xBWsRI34uB1GM= Received: (qmail 8849 invoked by alias); 11 Mar 2014 15:50:18 -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 8823 invoked by uid 89); 11 Mar 2014 15:50:17 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-3.6 required=5.0 tests=AWL, BAYES_00, SPF_HELO_PASS, SPF_PASS, T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 11 Mar 2014 15:50:15 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s2BFo6QI009795 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 11 Mar 2014 11:50:13 -0400 Received: from tucnak.zalov.cz (ovpn-116-35.ams2.redhat.com [10.36.116.35]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id s2BFo4xn032560 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Tue, 11 Mar 2014 11:50:05 -0400 Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.14.7/8.14.7) with ESMTP id s2BFo2HY001362; Tue, 11 Mar 2014 16:50:03 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.14.7/8.14.7/Submit) id s2BFo14t001361; Tue, 11 Mar 2014 16:50:01 +0100 Date: Tue, 11 Mar 2014 16:50:01 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Improve ifcombine Message-ID: <20140311155001.GD22862@tucnak.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes Hi! This patch fixes the ssa-ifcombine-10.c regression. The thing is that the uselessly added ASSERT_EXPR makes vrp1 change the cfg slightly like this: : _4 = x_3(D) & 1; if (_4 == 0) goto ; else goto ; : _5 = x_3(D) & 4; if (_5 != 0) - goto ; - else goto ; + else + goto ; : : - # t_1 = PHI <0(2), 3(3), 0(4)> + # t_1 = PHI <0(2), 3(4), 0(3)> return t_1; (addition of the ASSERT_EXPR resulted in creation of a new bb to insert it into and that bb is then removed again during cfg cleanup, but it ends up effectively swapping the forwarder block from one edge of the gimple cond to the other with corresponding phi arg change). Now, tree_ssa_ifcombine_bb apparently only groks the latter form (the one with + lines), but not the equivalent form the testcase had before VRP (and with the PR60482 fix also has after VRP, the one with - lines). This patch teaches tree_ssa_ifcombine_bb to handle both forms. Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk? Note, the phi-opt-2.c change is there because the patch made the test fail, as for LOGICAL_OP_NON_SHORT_CIRCUIT we now generate even better code, return a && b. So, I've added ssa-ifcombine-13.c test which is phi-opt-2.c and test that for -mbranch-cost=2 we have no ifs, and phi-opt-2.c now checks that for -mbranch-cost=1 we do have one if (ifcombine then doesn't do anything and we verify that phiopt does what it should). 2014-03-11 Jakub Jelinek * tree-ssa-ifcombine.c (forwarder_block_to): New function. (tree_ssa_ifcombine_bb): Handle also cases where else_bb is an empty forwarder block to then_bb or vice versa and then_bb and else_bb are effectively swapped. * gcc.dg/tree-ssa/ssa-ifcombine-12.c: New test. * gcc.dg/tree-ssa/ssa-ifcombine-13.c: New test. * gcc.dg/tree-ssa/phi-opt-2.c: Pass -mbranch-cost=1 if possible, only test for exactly one if if -mbranch-cost=1 has been passed. Jakub --- gcc/tree-ssa-ifcombine.c.jj 2014-03-11 12:13:53.012618098 +0100 +++ gcc/tree-ssa-ifcombine.c 2014-03-11 16:15:29.084329709 +0100 @@ -135,6 +135,16 @@ bb_no_side_effects_p (basic_block bb) return true; } +/* Return true if BB is an empty forwarder block to TO_BB. */ + +static bool +forwarder_block_to (basic_block bb, basic_block to_bb) +{ + return empty_block_p (bb) + && single_succ_p (bb) + && single_succ (bb) == to_bb; +} + /* Verify if all PHI node arguments in DEST for edges from BB1 or BB2 to DEST are the same. This makes the CFG merge point free from side-effects. Return true in this case, else false. */ @@ -660,6 +670,102 @@ tree_ssa_ifcombine_bb (basic_block inner return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false, true); } + + if (forwarder_block_to (else_bb, then_bb)) + { + /* Other possibilities for the && form, if else_bb is + empty forwarder block to then_bb. Compared to the above simpler + forms this can be treated as if then_bb and else_bb were swapped, + and the corresponding inner_cond_bb not inverted because of that. + For same_phi_args_p we look at equality of arguments between + edge from outer_cond_bb and the forwarder block. */ + if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb) + && same_phi_args_p (outer_cond_bb, else_bb, then_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto inner_cond_bb; else goto then_bb; + + if (p) goto then_bb; else goto else_bb; + + # empty fallthru + + # x = PHI + ... + */ + return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, + false, false); + } + + /* And a version where the outer condition is negated. */ + if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) + && same_phi_args_p (outer_cond_bb, else_bb, then_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto then_bb; else goto inner_cond_bb; + + if (p) goto then_bb; else goto else_bb; + + # empty fallthru + + # x = PHI + ... + */ + return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, + true, false); + } + } + + if (forwarder_block_to (then_bb, else_bb)) + { + /* Other possibilities for the || form, if then_bb is + empty forwarder block to else_bb. Compared to the above simpler + forms this can be treated as if then_bb and else_bb were swapped, + and the corresponding inner_cond_bb not inverted because of that. + For same_phi_args_p we look at equality of arguments between + edge from outer_cond_bb and the forwarder block. */ + if (recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb) + && same_phi_args_p (outer_cond_bb, then_bb, else_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto else_bb; else goto inner_cond_bb; + + if (q) goto then_bb; else goto else_bb; + + # empty fallthru + + # x = PHI + ... + */ + return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, + true, true); + } + + /* And a version where the outer condition is negated. */ + if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) + && same_phi_args_p (outer_cond_bb, then_bb, else_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto inner_cond_bb; else goto else_bb; + + if (q) goto then_bb; else goto else_bb; + + # empty fallthru + + # x = PHI + ... + */ + return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, + false, true); + } + } } return false; --- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c.jj 2014-03-11 16:15:29.085329698 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c 2014-03-11 16:15:29.085329698 +0100 @@ -0,0 +1,20 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-optimized" } */ + +/* Testcase for PR31657. */ + +int f(int x, int a, int b) +{ + int t = 0; + int c = 1 << a; + if (!(x & 1)) + t = 0; + else + if (x & (1 << 2)) + t = 3; + else + t = 0; + return t; +} +/* { dg-final { scan-tree-dump "& 5" "optimized" } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c.jj 2014-03-11 16:28:49.506695564 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c 2014-03-11 16:31:11.426884506 +0100 @@ -0,0 +1,21 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -fdump-tree-optimized" } */ +/* { dg-additional-options "-mbranch-cost=2" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } */ + +_Bool f1(_Bool a, _Bool b) +{ + if (a) + { + if (b) + return 1; + else + return 0; + } + return 0; +} + + +/* For LOGICAL_OP_NON_SHORT_CIRCUIT, this should be optimized + into return a & b;, with no ifs. */ +/* { dg-final { scan-tree-dump-not "if" "optimized" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } } */ +/* { dg-final { cleanup-tree-dump "optimized" } } */ --- gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c.jj 2008-09-05 12:54:30.000000000 +0200 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c 2014-03-11 16:28:21.693848143 +0100 @@ -1,5 +1,6 @@ /* { dg-do compile } */ /* { dg-options "-O1 -fdump-tree-optimized" } */ +/* { dg-additional-options "-mbranch-cost=1" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } */ _Bool f1(_Bool a, _Bool b) { @@ -17,6 +18,8 @@ _Bool f1(_Bool a, _Bool b) /* There should be only one if, the outer one; the inner one should have been changed to straight line code with the value of b (except that we don't fold ! (b != 0) into b - which can be fixed in a different patch). */ -/* { dg-final { scan-tree-dump-times "if" 1 "optimized"} } */ + which can be fixed in a different patch). + Test this only when known to be !LOGICAL_OP_NON_SHORT_CIRCUIT, + otherwise ifcombine may convert this into return a & b;. */ +/* { dg-final { scan-tree-dump-times "if" 1 "optimized" { target { i?86-*-* x86_64-*-* mips*-*-* s390*-*-* avr*-*-* } } } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */