From patchwork Fri Apr 13 08:32:36 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 152266 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]) by ozlabs.org (Postfix) with SMTP id E27C5B70E8 for ; Fri, 13 Apr 2012 18:33:17 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1334910798; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:Content-Type:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=WAMa6dR+GPMwmU6KQrSp2FUWiBw=; b=BLMS2MyyPLCUnSd D/fJbvwPT8FnYnidnEU33/f0LN3mDU08B/8+frac/8AzHIhTkB//Ez9zeOoiBifP TsBAaXoIc3nnv3jNSknhsgF0f4KmoSJfLeiUgg4DVW2KgR4PwMGGTnAeokBJIOtg 8HTpBosOQcRdZUc2jbucSpNbCEzE= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=YLGHjUw6TUQUglSleLM3covQfUA25456RjXacvz2daVzrH3j8idgIUlVatw2TT zpls0Zg+2A/qOH8CuSYJFNgm9zgJ/370cJQkK3ez587mm8Yzg27QaVNcywdDK/sH OPWNzxA0DGuUjKor2B2i9ucSh6F7utpzQYVld2eTO4E5U=; Received: (qmail 18117 invoked by alias); 13 Apr 2012 08:33:13 -0000 Received: (qmail 18109 invoked by uid 22791); 13 Apr 2012 08:33:11 -0000 X-SWARE-Spam-Status: No, hits=-3.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, TW_TM X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 13 Apr 2012 08:32:46 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1SIbvx-0000NX-Ip from Tom_deVries@mentor.com ; Fri, 13 Apr 2012 01:32:45 -0700 Received: from SVR-IES-FEM-02.mgc.mentorg.com ([137.202.0.106]) by svr-orw-fem-01.mgc.mentorg.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Fri, 13 Apr 2012 01:32:45 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-02.mgc.mentorg.com (137.202.0.106) with Microsoft SMTP Server id 14.1.289.1; Fri, 13 Apr 2012 09:32:42 +0100 Message-ID: <4F87E4A4.2080807@mentor.com> Date: Fri, 13 Apr 2012 10:32:36 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.28) Gecko/20120313 Lightning/1.0b2 Thunderbird/3.1.20 MIME-Version: 1.0 To: Richard Guenther CC: "gcc-patches@gcc.gnu.org" Subject: [PATCH] Fix for PR52734 (-ftree-tail-merge) 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 Richard, this patch fixes PR52743. The problem is as follows: blocks 3 and 5, with successor 6 are considered equal and merged. ... # BLOCK 3 freq:6102 # PRED: 2 [61.0%] (true,exec) # VUSE <.MEMD.1734_10> dddD.1710_3 = bbbD.1703; goto ; # SUCC: 6 [100.0%] (fallthru,exec) # BLOCK 5 freq:2378 # PRED: 4 [61.0%] (false,exec) # SUCC: 6 [100.0%] (fallthru,exec) # BLOCK 6 freq:10000 # PRED: 3 [100.0%] (fallthru,exec) 7 [100.0%] (fallthru) 5 [100.0%] (fallthru,exec) # dddD.1710_1 = PHI # .MEMD.1734_8 = PHI <.MEMD.1734_10(3), .MEMD.1734_11(7), .MEMD.1734_11(5)> # VUSE <.MEMD.1734_8> return dddD.1710_1; # SUCC: EXIT [100.0%] ... Tail merge considers 2 blocks equal if the effect at the tail is equal, meaning: - the sequence of side effects produced by each block is equal - the value phis are equal There are no side effects in block 3 and 5, and the phi alternatives of dddD.1710_1 for 3 (dddD.1710_3) and 5 (dddD.1710_4) are proven equal by gvn. The problem is that changing the (4->5) edge into a (4->3) edge changes the value of dddD.1710_3, because block 4 contains a store that affects the load in block 3. ... # BLOCK 4 freq:3898 # PRED: 2 [39.0%] (false,exec) # VUSE <.MEMD.1734_10> dddD.1710_4 = bbbD.1703; # .MEMD.1734_11 = VDEF <.MEMD.1734_10> # USE = nonlocal null # CLB = nonlocal null D.1724_5 = aaaD.1705 (); if (D.1724_5 != 0) goto ; else goto ; # SUCC: 7 [39.0%] (true,exec) 5 [61.0%] (false,exec) ... Or, put differently, the incoming vuse of block 3 affects a value phi alternative for that block (dddD.1710_3), so the 2 blocks are equal only under the condition that the incoming vuses are equal. We could build an analysis that addresses that precisely, but for now I implemented a more coarse-grained fix: if the incoming vuses are not equal, and at least one of the vuses influenced a non-virtual result, we don't consider the blocks equal. Bootstrapped and reg-tested on x86_64. ok for trunk, 4.7.1? Thanks, - Tom 2012-04-13 Tom de Vries * tree-ssa-tail-merge.c (gsi_advance_bw_nondebug_nonlocal): Add parameters vuse and vuse_escaped. (find_duplicate): Init vuse1, vuse2 and vuse_escaped. Pass to gsi_advance_bw_nondebug_nonlocal. Return if vuse_escaped and vuse1 != vuse2. * gcc.dg/pr52734.c: New test. Index: gcc/tree-ssa-tail-merge.c =================================================================== --- gcc/tree-ssa-tail-merge.c (revision 185028) +++ gcc/tree-ssa-tail-merge.c (working copy) @@ -1123,18 +1123,31 @@ gimple_equal_p (same_succ same_succ, gim } } -/* Let GSI skip backwards over local defs. */ +/* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE. + Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the + processed statements. */ static void -gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi) +gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse, + bool *vuse_escaped) { gimple stmt; + tree lvuse; while (true) { if (gsi_end_p (*gsi)) return; stmt = gsi_stmt (*gsi); + + lvuse = gimple_vuse (stmt); + if (lvuse != NULL_TREE) + { + *vuse = lvuse; + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF)) + *vuse_escaped = true; + } + if (!(is_gimple_assign (stmt) && local_def (gimple_get_lhs (stmt)) && !gimple_has_side_effects (stmt))) return; @@ -1150,9 +1163,11 @@ find_duplicate (same_succ same_succ, bas { gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1); gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2); + tree vuse1 = NULL_TREE, vuse2 = NULL_TREE; + bool vuse_escaped = false; - gsi_advance_bw_nondebug_nonlocal (&gsi1); - gsi_advance_bw_nondebug_nonlocal (&gsi2); + gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped); + gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped); while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2)) { @@ -1161,13 +1176,20 @@ find_duplicate (same_succ same_succ, bas gsi_prev_nondebug (&gsi1); gsi_prev_nondebug (&gsi2); - gsi_advance_bw_nondebug_nonlocal (&gsi1); - gsi_advance_bw_nondebug_nonlocal (&gsi2); + gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped); + gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped); } if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2))) return; + /* If the incoming vuses are not the same, and the vuse escaped into an + SSA_OP_DEF, then merging the 2 blocks will change the value of the def, + which potentially means the semantics of one of the blocks will be changed. + TODO: make this check more precise. */ + if (vuse_escaped && vuse1 != vuse2) + return; + if (dump_file) fprintf (dump_file, "find_duplicates: duplicate of \n", bb1->index, bb2->index); Index: gcc/testsuite/gcc.dg/pr52734.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/pr52734.c (revision 0) @@ -0,0 +1,35 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +int bbb = 0; + +int __attribute__((noinline,noclone)) aaa(void) +{ + ++bbb; + return 0; +} + +int __attribute__((noinline,noclone)) ccc(void) +{ + int ddd; + /* bbb == 0 */ + if (aaa()) + return bbb; + + /* bbb == 1 */ + ddd = bbb; + /* bbb == ddd == 1 */ + if (aaa ()) + return 0; + /* bbb == 2, ddd == 1 */ + + return ddd; +} + +int main(void) +{ + if (ccc() != 1) + __builtin_abort(); + return 0; +} +