From patchwork Wed Jul 4 18:07:11 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: 169033 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 4F8E12C00E7 for ; Thu, 5 Jul 2012 04:07:40 +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=1342030061; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:References:In-Reply-To:Content-Type:Mailing-List: Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:Sender:Delivered-To; bh=c8rP5qOTuEtI74ODaJRolahqhYU=; b=wRaa0N0NKfvVOxF5zrqUNy68COXoi/2NwVtHzr0OEbOwH7+E6hM/ZI+Q6U0nOy TfYMWg5198dLsr4xvJyC5jO9P0mcoHv17IAp8cAJLuZH9hpW3M2YKxrKVjvPJ9Dn pKnl7pMQ9g8CM001D6XlPaAvKMHDIlw6cf3IoyUlo1lzU= 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:References:In-Reply-To:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=qree1iTeScEEfwJyNhwHuT9lyA7uMsE6m8Sj7st4ef7ZywnO6DlyzlTkqvHTdc yX+BSG/PQjzyGlCWzNr3Bcb9lOBDHGaKwReTW9YM8cW5UHwwJ9mcFFHg2EVIXdCB If+j7GIdSi9lSax8VgIUdX9roIMd80hjCg/nwtI8+jcxs=; Received: (qmail 30863 invoked by alias); 4 Jul 2012 18:07:35 -0000 Received: (qmail 30837 invoked by uid 22791); 4 Jul 2012 18:07:32 -0000 X-SWARE-Spam-Status: No, hits=-4.3 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, KHOP_THREADED, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, TW_VN 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; Wed, 04 Jul 2012 18:07:17 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1SmTyu-0007Pu-Po from Tom_deVries@mentor.com ; Wed, 04 Jul 2012 11:07:16 -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); Wed, 4 Jul 2012 11:07:16 -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; Wed, 4 Jul 2012 19:07:14 +0100 Message-ID: <4FF4864F.5090108@mentor.com> Date: Wed, 4 Jul 2012 20:07:11 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1 MIME-Version: 1.0 To: Richard Guenther CC: "gcc-patches@gcc.gnu.org" Subject: Re: [PATCH] Fix for PR52009 - Another missed tail merging opportunity References: <4F2857AC.7050107@mentor.com> <4F285801.5050807@mentor.com> In-Reply-To: <4F285801.5050807@mentor.com> 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 On 31/01/12 22:07, Tom de Vries wrote: > On 31/01/12 22:05, Tom de Vries wrote: >> Richard, >> > > Sorry, with patch this time. > >> this patch fixes PR52009. >> >> Consider this test-case: >> ... >> int z; >> >> void >> foo (int y) >> { >> if (y == 6) >> z = 5; >> else >> z = 5; >> } >> ... >> >> Currently, compiling with -O2 gives us this representation at pr51879-7.c.094t.pre: >> ... >> # BLOCK 3 freq:1991 >> # PRED: 2 [19.9%] (true,exec) >> # .MEMD.1710_4 = VDEF <.MEMD.1710_3(D)> >> zD.1702 = 5; >> goto ; >> # SUCC: 5 [100.0%] (fallthru,exec) >> >> # BLOCK 4 freq:8009 >> # PRED: 2 [80.1%] (false,exec) >> # .MEMD.1710_5 = VDEF <.MEMD.1710_3(D)> >> zD.1702 = 5; >> # SUCC: 5 [100.0%] (fallthru,exec) >> >> # BLOCK 5 freq:10000 >> # PRED: 3 [100.0%] (fallthru,exec) 4 [100.0%] (fallthru,exec) >> # .MEMD.1710_2 = PHI <.MEMD.1710_4(3), .MEMD.1710_5(4)> >> # VUSE <.MEMD.1710_2> >> return; >> ... >> >> Blocks 3 and 4 are not tail-merged. >> >> The patch allows the example to be tail-merged by: >> - value numbering .MEMD.1710_4 and .MEMD.1710_5 equal >> - comparing gimple_vdef value numbers for assignments during tail-merge >> >> Bootstrapped and reg-tested on x86_64. >> >> OK for stage1? >> Richard, I did some trivial changes such that the patch is applicable again to trunk, and added a test-case, which you suggested in http://gcc.gnu.org/ml/gcc-patches/2012-05/msg00220.html. The test-case handles the case of 2 identical calls assigning to different deferenced pointers, where the pointers are value-numbered the same: ... void bar (int c, int *p) { int *q = p; if (c) *p = foo (); else *q = foo (); } ... The representation before pre looks like this: ... # BLOCK 3 freq:3900 # PRED: 2 [39.0%] (true,exec) # .MEMD.1724_8 = VDEF <.MEMD.1724_7(D)> # USE = nonlocal # CLB = nonlocal D.1721_4 = fooD.1712 (); # .MEMD.1724_9 = VDEF <.MEMD.1724_8> *pD.1714_1(D) = D.1721_4; goto ; # SUCC: 5 [100.0%] (fallthru,exec) # BLOCK 4 freq:6100 # PRED: 2 [61.0%] (false,exec) # .MEMD.1724_10 = VDEF <.MEMD.1724_7(D)> # USE = nonlocal # CLB = nonlocal D.1723_5 = fooD.1712 (); # .MEMD.1724_11 = VDEF <.MEMD.1724_10> *qD.1717_2 = D.1723_5; # SUCC: 5 [100.0%] (fallthru,exec) ... In pre, we're already value numbering the result and vdef of the calls the same, and the pointers the same: ... Value numbers: q_2 = p_1(D) D.1723_5 = D.1721_4 .MEM_10 = .MEM_8 ... But not the vdefs of the stores. This patch implements that, and allows the blocks to be merged. ok for trunk? Thanks, - Tom 2012-07-04 Tom de Vries PR tree-optimization/52009 * tree-ssa-tail-merge.c (gimple_equal_p): For GIMPLE_ASSIGN, compare value numbers of gimple_vdef. * tree-ssa-sccvn.h (vn_reference_insert): Add vdef parameter to prototype. * tree-ssa-sccvn.c (copy_reference_ops_from_ref): Handle MODIFY_EXPR. (vn_reference_insert): Add and handle vdef parameter. (visit_reference_op_load): Add argument to vn_reference_insert call. (visit_reference_op_store): Find value number of vdef of store. Insert value number of vdef of store. * gcc.dg/pr51879-7.c: New test. * gcc.dg/pr51879-18.c: New test. Index: gcc/tree-ssa-tail-merge.c =================================================================== --- gcc/tree-ssa-tail-merge.c (revision 189007) +++ gcc/tree-ssa-tail-merge.c (working copy) @@ -1119,6 +1119,14 @@ gimple_equal_p (same_succ same_succ, gim case GIMPLE_ASSIGN: lhs1 = gimple_get_lhs (s1); lhs2 = gimple_get_lhs (s2); + if (gimple_vdef (s1)) + { + if (vn_valueize (gimple_vdef (s1)) != vn_valueize (gimple_vdef (s2))) + return false; + if (TREE_CODE (lhs1) != SSA_NAME + && TREE_CODE (lhs2) != SSA_NAME) + return true; + } return (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME && vn_valueize (lhs1) == vn_valueize (lhs2)); Index: gcc/tree-ssa-sccvn.c =================================================================== --- gcc/tree-ssa-sccvn.c (revision 189007) +++ gcc/tree-ssa-sccvn.c (working copy) @@ -628,6 +628,9 @@ copy_reference_ops_from_ref (tree ref, V switch (temp.opcode) { + case MODIFY_EXPR: + temp.op0 = TREE_OPERAND (ref, 1); + break; case WITH_SIZE_EXPR: temp.op0 = TREE_OPERAND (ref, 1); temp.off = 0; @@ -748,6 +751,7 @@ copy_reference_ops_from_ref (tree ref, V VEC_safe_push (vn_reference_op_s, heap, *result, &temp); if (REFERENCE_CLASS_P (ref) + || TREE_CODE (ref) == MODIFY_EXPR || TREE_CODE (ref) == WITH_SIZE_EXPR || (TREE_CODE (ref) == ADDR_EXPR && !is_gimple_min_invariant (ref))) @@ -1941,7 +1945,7 @@ vn_reference_lookup (tree op, tree vuse, RESULT, and return the resulting reference structure we created. */ vn_reference_t -vn_reference_insert (tree op, tree result, tree vuse) +vn_reference_insert (tree op, tree result, tree vuse, tree vdef) { void **slot; vn_reference_t vr1; @@ -1957,6 +1961,7 @@ vn_reference_insert (tree op, tree resul vr1->set = get_alias_set (op); vr1->hashcode = vn_reference_compute_hash (vr1); vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result; + vr1->result_vdef = vdef; slot = htab_find_slot_with_hash (current_info->references, vr1, vr1->hashcode, INSERT); @@ -2775,7 +2780,7 @@ visit_reference_op_load (tree lhs, tree else { changed = set_ssa_val_to (lhs, lhs); - vn_reference_insert (op, lhs, last_vuse); + vn_reference_insert (op, lhs, last_vuse, NULL_TREE); } return changed; @@ -2789,8 +2794,11 @@ static bool visit_reference_op_store (tree lhs, tree op, gimple stmt) { bool changed = false; - tree result; + vn_reference_t vnresult = NULL; + tree result, assign; bool resultsame = false; + tree vuse = gimple_vuse (stmt); + tree vdef = gimple_vdef (stmt); /* First we want to lookup using the *vuses* from the store and see if there the last store to this location with the same address @@ -2808,7 +2816,7 @@ visit_reference_op_store (tree lhs, tree Otherwise, the vdefs for the store are used when inserting into the table, since the store generates a new memory state. */ - result = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_NOWALK, NULL); + result = vn_reference_lookup (lhs, vuse, VN_NOWALK, NULL); if (result) { @@ -2821,8 +2829,17 @@ visit_reference_op_store (tree lhs, tree if (!result || !resultsame) { - tree vdef; + assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op); + vn_reference_lookup (assign, vuse, VN_NOWALK, &vnresult); + if (vnresult) + { + VN_INFO (vdef)->use_processed = true; + return set_ssa_val_to (vdef, vnresult->result_vdef); + } + } + if (!result || !resultsame) + { if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, "No store match\n"); @@ -2834,7 +2851,7 @@ visit_reference_op_store (tree lhs, tree } /* Have to set value numbers before insert, since insert is going to valueize the references in-place. */ - if ((vdef = gimple_vdef (stmt))) + if (vdef) { changed |= set_ssa_val_to (vdef, vdef); } @@ -2842,22 +2859,21 @@ visit_reference_op_store (tree lhs, tree /* Do not insert structure copies into the tables. */ if (is_gimple_min_invariant (op) || is_gimple_reg (op)) - vn_reference_insert (lhs, op, vdef); + vn_reference_insert (lhs, op, vdef, NULL); + + assign = build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, op); + vn_reference_insert (assign, lhs, vuse, vdef); } else { /* We had a match, so value number the vdef to have the value number of the vuse it came from. */ - tree def, use; if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Store matched earlier value," "value numbering store vdefs to matching vuses.\n"); - def = gimple_vdef (stmt); - use = gimple_vuse (stmt); - - changed |= set_ssa_val_to (def, SSA_VAL (use)); + changed |= set_ssa_val_to (vdef, SSA_VAL (vuse)); } return changed; Index: gcc/tree-ssa-sccvn.h =================================================================== --- gcc/tree-ssa-sccvn.h (revision 189007) +++ gcc/tree-ssa-sccvn.h (working copy) @@ -200,7 +200,7 @@ tree vn_reference_lookup_pieces (tree, a VEC (vn_reference_op_s, heap) *, vn_reference_t *, vn_lookup_kind); tree vn_reference_lookup (tree, tree, vn_lookup_kind, vn_reference_t *); -vn_reference_t vn_reference_insert (tree, tree, tree); +vn_reference_t vn_reference_insert (tree, tree, tree, tree); vn_reference_t vn_reference_insert_pieces (tree, alias_set_type, tree, VEC (vn_reference_op_s, heap) *, tree, unsigned int); Index: gcc/testsuite/gcc.dg/pr51879-7.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/pr51879-7.c (revision 0) @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-pre" } */ + +int bar (int); + +int z; + +void +foo (int y) +{ + if (y == 6) + z = 5; + else + z = 5; +} + +/* { dg-final { scan-tree-dump-times "z = 5" 1 "pre"} } */ +/* { dg-final { cleanup-tree-dump "pre" } } */ Index: gcc/testsuite/gcc.dg/pr51879-18.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/pr51879-18.c (revision 0) @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-pre -fno-tree-copy-prop -fno-tree-dominator-opts -fno-tree-copyrename" } */ + +extern int foo (void); + +void bar (int c, int *p) +{ + int *q = p; + + if (c) + *p = foo (); + else + *q = foo (); +} + +/* { dg-final { scan-tree-dump-times "foo \\(" 1 "pre"} } */ +/* { dg-final { cleanup-tree-dump "pre" } } */