From patchwork Wed Mar 12 09:52:23 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 329351 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 2F5592C00A7 for ; Wed, 12 Mar 2014 20:52:41 +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:references:mime-version :content-type:in-reply-to; q=dns; s=default; b=fMwksF/d1UBzKNgPl xIZGGPEMyTSI/5brM6r/4DXF0vUm6jdwysnh09V/DoQNNVvwFImFyEmHIAfqxJsS xZwGFyaCxxS7u7JMDS/+nC8746y98vvdpOztGJoL/yVs4hUqi7KJ5XKiIMSSvRRL ah4qMaWHMngXBHiJdVq7KpkEW0= 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:references:mime-version :content-type:in-reply-to; s=default; bh=ZYYXYeinCNxaQqckVhPV66r 17nc=; b=XfWOBnKc9lDSgbDtdgcpJ608G/ez7P8/m7sCKXC9SEH86/vSCvKpWvy dC3ptiHrOJp6VNPFfUPmhEb/a0xQWXESpoMRlGC9epcB9RLHz+hHoHKIUtg/PdJT vSWjgoYcIJHh0ud9ReRP9TlsHKDL7d/qyr8Bsirc2QsZLL44ymCU= Received: (qmail 2924 invoked by alias); 12 Mar 2014 09:52:34 -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 2909 invoked by uid 89); 12 Mar 2014 09:52:33 -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; Wed, 12 Mar 2014 09:52:32 +0000 Received: from int-mx02.intmail.prod.int.phx2.redhat.com (int-mx02.intmail.prod.int.phx2.redhat.com [10.5.11.12]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id s2C9qU4G009019 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 12 Mar 2014 05:52:30 -0400 Received: from tucnak.zalov.cz (ovpn-116-35.ams2.redhat.com [10.36.116.35]) by int-mx02.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id s2C9qQOC004923 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 12 Mar 2014 05:52:29 -0400 Received: from tucnak.zalov.cz (localhost [127.0.0.1]) by tucnak.zalov.cz (8.14.7/8.14.7) with ESMTP id s2C9qPnA001833; Wed, 12 Mar 2014 10:52:25 +0100 Received: (from jakub@localhost) by tucnak.zalov.cz (8.14.7/8.14.7/Submit) id s2C9qN7m001832; Wed, 12 Mar 2014 10:52:23 +0100 Date: Wed, 12 Mar 2014 10:52:23 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] Improve ifcombine Message-ID: <20140312095223.GJ22862@tucnak.redhat.com> Reply-To: Jakub Jelinek References: <20140311155001.GD22862@tucnak.redhat.com> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-IsSubscribed: yes On Wed, Mar 12, 2014 at 09:51:46AM +0100, Richard Biener wrote: > Ok in principle, but is there a possibility to factor this a bit? > It looks like a lot of cut&paste (without looking too close for subtle > differences). Like this? 2014-03-12 Jakub Jelinek * tree-ssa-ifcombine.c (forwarder_block_to): New function. (tree_ssa_ifcombine_bb_1): New function. (tree_ssa_ifcombine_bb): Use it. 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 20:14:34.046082392 +0100 +++ gcc/tree-ssa-ifcombine.c 2014-03-12 10:45:29.355054715 +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. */ @@ -561,6 +571,99 @@ ifcombine_ifandif (basic_block inner_con return false; } +/* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and + dispatch to the appropriate if-conversion helper for a particular + set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB. + PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */ + +static bool +tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb, + basic_block then_bb, basic_block else_bb, + basic_block phi_pred_bb) +{ + /* The && form is characterized by a common else_bb with + the two edges leading to it mergable. The latter is + guaranteed by matching PHI arguments in the else_bb and + the inner cond_bb having no side-effects. */ + if (phi_pred_bb != else_bb + && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) + && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto inner_cond_bb; else goto else_bb; + + if (p) goto ...; else goto else_bb; + ... + + ... + */ + return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, false, + false); + } + + /* And a version where the outer condition is negated. */ + if (phi_pred_bb != else_bb + && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb) + && same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto else_bb; else goto inner_cond_bb; + + if (p) goto ...; else goto else_bb; + ... + + ... + */ + return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true, + false); + } + + /* The || form is characterized by a common then_bb with the + two edges leading to it mergable. The latter is guaranteed + by matching PHI arguments in the then_bb and the inner cond_bb + having no side-effects. */ + if (phi_pred_bb != then_bb + && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) + && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto then_bb; else goto inner_cond_bb; + + if (q) goto then_bb; else goto ...; + + ... + */ + return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, true, + true); + } + + /* And a version where the outer condition is negated. */ + if (phi_pred_bb != then_bb + && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb) + && same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb) + && bb_no_side_effects_p (inner_cond_bb)) + { + /* We have + + if (q) goto inner_cond_bb; else goto then_bb; + + if (q) goto then_bb; else goto ...; + + ... + */ + return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false, + true); + } + + return false; +} + /* Recognize a CFG pattern and dispatch to the appropriate if-conversion helper. We start with BB as the innermost worker basic-block. Returns true if a transformation was done. */ @@ -585,80 +688,33 @@ tree_ssa_ifcombine_bb (basic_block inner { basic_block outer_cond_bb = single_pred (inner_cond_bb); - /* The && form is characterized by a common else_bb with - the two edges leading to it mergable. The latter is - guaranteed by matching PHI arguments in the else_bb and - the inner cond_bb having no side-effects. */ - if (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb) - && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) - && bb_no_side_effects_p (inner_cond_bb)) - { - /* We have - - if (q) goto inner_cond_bb; else goto else_bb; - - if (p) goto ...; else goto else_bb; - ... - - ... - */ - 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, &else_bb, &inner_cond_bb) - && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb) - && bb_no_side_effects_p (inner_cond_bb)) - { - /* We have - - if (q) goto else_bb; else goto inner_cond_bb; - - if (p) goto ...; else goto else_bb; - ... - - ... - */ - return ifcombine_ifandif (inner_cond_bb, false, outer_cond_bb, true, - false); - } - - /* The || form is characterized by a common then_bb with the - two edges leading to it mergable. The latter is guaranteed - by matching PHI arguments in the then_bb and the inner cond_bb - having no side-effects. */ - if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb) - && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) - && bb_no_side_effects_p (inner_cond_bb)) - { - /* We have - - if (q) goto then_bb; else goto inner_cond_bb; - - if (q) goto then_bb; else goto ...; - - ... - */ - 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, &then_bb) - && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb) - && bb_no_side_effects_p (inner_cond_bb)) - { - /* We have - - if (q) goto inner_cond_bb; else goto then_bb; - - if (q) goto then_bb; else goto ...; - - ... - */ - return ifcombine_ifandif (inner_cond_bb, true, outer_cond_bb, false, - true); + if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, + then_bb, else_bb, inner_cond_bb)) + return 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 (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb, + then_bb, else_bb)) + return true; + } + else 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 (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb, + then_bb, then_bb)) + return true; } } --- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c.jj 2014-03-12 10:23:33.231679541 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c 2014-03-12 10:23:33.231679541 +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-12 10:23:33.231679541 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-13.c 2014-03-12 10:23:33.231679541 +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 2014-03-11 20:14:33.812083721 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c 2014-03-12 10:23:33.231679541 +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" } } */