[{"id":1764606,"web_url":"http://patchwork.ozlabs.org/comment/1764606/","msgid":"","list_archive_url":null,"date":"2017-09-07T09:19:56","subject":"Re: [PATCH] Enhance PHI processing in VN","submitter":{"id":4338,"url":"http://patchwork.ozlabs.org/api/people/4338/","name":"Richard Biener","email":"rguenther@suse.de"},"content":"On Thu, 7 Sep 2017, Richard Biener wrote:\n\n> \n> This enhances VN to do the same PHI handling as CCP, meeting\n> undefined and constant to constant. I've gone a little bit\n> further (and maybe will revisit this again) in also meeting\n> all-undefined to undefined taking one of the undefined args\n> as the value number. I feel like this might run into\n> the equation issues I mentioned in the other mail so it\n> would be cleaner to invent a \"new\" undefined value number\n> here -- but I have to make sure to not create too many\n> default-defs or break iteration convergence (default defs are also\n> expensive given they require a decl - sth I want to change as well).\n> \n> So for now I guess I'll stick with the slightly bogus(?) way also\n> hoping for a testcase that shows the issue this uncovers.\n> \n> Note it's required to handle\n> \n> _3 = PHI <_1(D), _2(D)>\n> ..\n> \n> _4 = PHI <_3, 1>\n> \n> consistently with\n> \n> _4 = PHI <_1(D), _2(D), 1>\n> \n> aka with/without extra forwarders.\n\nThat said, \"fallout\" is we simplify\n\nint foo (int b)\n{ \n int i, j, k;\n if (b)\n k = i;\n else\n k = j;\n if (k == i)\n return 1;\n else if (k == j)\n return 2;\n return 0;\n\nto\n\n if (j == i)\n return 1;\n else\n return 2;\n\nor even just\n\n return 2;\n\ndependent on PHI argument order of k = PHI .\n\nLikewise we'd say that either k - i or k - j is zero.\n\nThe complication with PHIs is that they do not always only appear\nin places where uses of the args dominate it but the other way\naround so we can't really invoke the undefined behavior rule\non a PHI node with undefined args itself. The question is whether\nwe may for PHIs with just undefined args ... but my guess is no\nso I do have to fix the above.\n\nAnybody can produce a testcase that we'd consider wrong-code?\n(the above examples clearly are not)\n\nThanks,\nRichard.\n\n> Similar to CCP/copyprop this doesn't allow copies to be propagated\n> this way as this removes most gcc.dg/Wuninitialized* warnings\n> we test for...\n> \n> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.\n> \n> Richard.\n> \n> 2017-09-07 Richard Biener \n> \n> \t* tree-ssa-sccnv.c (visit_phi): Handle meeting undefined\n> \tvalues.\n> \n> \t* gcc.dg/tree-ssa/ssa-fre-59.c: New testcase.\n> \n> Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-59.c\n> ===================================================================\n> --- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-59.c\t(nonexistent)\n> +++ gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-59.c\t(working copy)\n> @@ -0,0 +1,14 @@\n> +/* { dg-do compile } */\n> +/* { dg-options \"-O -fdump-tree-fre1\" } */\n> +\n> +int i;\n> +int foo (int b)\n> +{\n> + int j;\n> + i = 1;\n> + if (b)\n> + j = i;\n> + return i - j;\n> +}\n> +\n> +/* { dg-final { scan-tree-dump \"return 0;\" \"fre1\" } } */\n> Index: gcc/tree-ssa-sccvn.c\n> ===================================================================\n> --- gcc/tree-ssa-sccvn.c\t(revision 251833)\n> +++ gcc/tree-ssa-sccvn.c\t(working copy)\n> @@ -3864,6 +3864,7 @@ visit_phi (gimple *phi)\n> tree result;\n> tree sameval = VN_TOP;\n> bool allsame = true;\n> + tree seen_undef = NULL_TREE;\n> unsigned n_executable = 0;\n> \n> /* TODO: We could check for this in init_sccvn, and replace this\n> @@ -3884,8 +3885,12 @@ visit_phi (gimple *phi)\n> \tif (TREE_CODE (def) == SSA_NAME)\n> \t def = SSA_VAL (def);\n> \tif (def == VN_TOP)\n> -\t continue;\n> -\tif (sameval == VN_TOP)\n> +\t ;\n> +\t/* Ignore undefined defs here. */\n> +\telse if (TREE_CODE (def) == SSA_NAME\n> +\t\t && ssa_undefined_value_p (def, false))\n> +\t seen_undef = def;\n> +\telse if (sameval == VN_TOP)\n> \t sameval = def;\n> \telse if (!expressions_equal_p (def, sameval))\n> \t {\n> @@ -3893,7 +3898,18 @@ visit_phi (gimple *phi)\n> \t break;\n> \t }\n> }\n> - \n> + /* If we found undefined values and didn't end up with a constant\n> + drop back to varying as otherwise we end up removing most late\n> + uninitialized use warnings. CCP/copyprop have the same restriction. */\n> + if (allsame && seen_undef)\n> + {\n> + /* Unless this was the only value we've seen. */\n> + if (sameval == VN_TOP)\n> +\tsameval = seen_undef;\n> + else if (! is_gimple_min_invariant (sameval))\n> +\tallsame = false;\n> + }\n> +\n> /* If none of the edges was executable or all incoming values are\n> undefined keep the value-number at VN_TOP. If only a single edge\n> is exectuable use its value. */\n>","headers":{"Return-Path":"","X-Original-To":"incoming@patchwork.ozlabs.org","Delivered-To":["patchwork-incoming@bilbo.ozlabs.org","mailing list gcc-patches@gcc.gnu.org"],"Authentication-Results":["ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-461665-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"B4ptQr9o\"; dkim-atps=neutral","sourceware.org; auth=none"],"Received":["from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xnw0C6b8pz9sNV\n\tfor ;\n\tThu, 7 Sep 2017 19:20:11 +1000 (AEST)","(qmail 8720 invoked by alias); 7 Sep 2017 09:20:03 -0000","(qmail 6829 invoked by uid 89); 7 Sep 2017 09:20:00 -0000","from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by\n\tsourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tThu, 07 Sep 2017 09:19:58 +0000","from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254])\tby\n\tmx1.suse.de (Postfix) with ESMTP id 8FE7AAC15\tfor\n\t; Thu, 7 Sep 2017 09:19:56 +0000 (UTC)"],"DomainKey-Signature":"a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:date\n\t:from:to:subject:in-reply-to:message-id:references:mime-version\n\t:content-type; q=dns; s=default; b=MYLzQMgIky12QEZsZl0Kz7AchbleP\n\td52nFLlc0/c1PPz2FKidoRwwC6CBfdGTcj7iq5LTYZZOPcS4V1aKPF54qEVUiix8\n\t3ILJ4wDvE02ncswUhSRIS/xnuZJrC1zuXl/FHHAZMk1VHUM6LhhlOyfa2u+9Xc25\n\tsRkjeKzUNlTpFU=","DKIM-Signature":"v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:date\n\t:from:to:subject:in-reply-to:message-id:references:mime-version\n\t:content-type; s=default; bh=2O3U/lH02bQjFFSiBoY1z+EsBts=; b=B4p\n\ttQr9oRT1Fp9nBsO4+SQ7mBX1V1l6QMszZy/RG47kIz0wbNVF47mly64GvZupHwPl\n\tNKRS094zT5Hw88dRBJAFA5aB9caA9MDlkvEVIprnLQ8q/vp9nG1VAvcX7l/f/YZ3\n\tvrqQXoj0PiVKhRKoimCXaQI7FEYRaDhWw1MAKyZg=","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","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-11.1 required=5.0 tests=BAYES_00, GIT_PATCH_2,\n\tGIT_PATCH_3, KAM_ASCII_DIVIDERS, RP_MATCHES_RCVD,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=","X-HELO":"mx1.suse.de","Date":"Thu, 7 Sep 2017 11:19:56 +0200 (CEST)","From":"Richard Biener ","To":"gcc-patches@gcc.gnu.org","Subject":"Re: [PATCH] Enhance PHI processing in VN","In-Reply-To":"","Message-ID":"","References":"","User-Agent":"Alpine 2.20 (LSU 67 2015-01-07)","MIME-Version":"1.0","Content-Type":"text/plain; charset=US-ASCII"}},{"id":1768540,"web_url":"http://patchwork.ozlabs.org/comment/1768540/","msgid":"","list_archive_url":null,"date":"2017-09-14T11:55:59","subject":"Re: [PATCH] Enhance PHI processing in VN","submitter":{"id":4338,"url":"http://patchwork.ozlabs.org/api/people/4338/","name":"Richard Biener","email":"rguenther@suse.de"},"content":"On Thu, 7 Sep 2017, Richard Biener wrote:\n\n> On Thu, 7 Sep 2017, Richard Biener wrote:\n> \n> > \n> > This enhances VN to do the same PHI handling as CCP, meeting\n> > undefined and constant to constant. I've gone a little bit\n> > further (and maybe will revisit this again) in also meeting\n> > all-undefined to undefined taking one of the undefined args\n> > as the value number. I feel like this might run into\n> > the equation issues I mentioned in the other mail so it\n> > would be cleaner to invent a \"new\" undefined value number\n> > here -- but I have to make sure to not create too many\n> > default-defs or break iteration convergence (default defs are also\n> > expensive given they require a decl - sth I want to change as well).\n> > \n> > So for now I guess I'll stick with the slightly bogus(?) way also\n> > hoping for a testcase that shows the issue this uncovers.\n> > \n> > Note it's required to handle\n> > \n> > _3 = PHI <_1(D), _2(D)>\n> > ..\n> > \n> > _4 = PHI <_3, 1>\n> > \n> > consistently with\n> > \n> > _4 = PHI <_1(D), _2(D), 1>\n> > \n> > aka with/without extra forwarders.\n> \n> That said, \"fallout\" is we simplify\n> \n> int foo (int b)\n> { \n> int i, j, k;\n> if (b)\n> k = i;\n> else\n> k = j;\n> if (k == i)\n> return 1;\n> else if (k == j)\n> return 2;\n> return 0;\n> \n> to\n> \n> if (j == i)\n> return 1;\n> else\n> return 2;\n> \n> or even just\n> \n> return 2;\n> \n> dependent on PHI argument order of k = PHI .\n> \n> Likewise we'd say that either k - i or k - j is zero.\n> \n> The complication with PHIs is that they do not always only appear\n> in places where uses of the args dominate it but the other way\n> around so we can't really invoke the undefined behavior rule\n> on a PHI node with undefined args itself. The question is whether\n> we may for PHIs with just undefined args ... but my guess is no\n> so I do have to fix the above.\n> \n> Anybody can produce a testcase that we'd consider wrong-code?\n> (the above examples clearly are not)\n\nAfter some pondering I decided for PHIs with all undefs there's\nreally no way things can go wrong.\n\nThus the following is what I installed.\n\nBootstrapped and tested on x86_64-unknown-linux-gnu.\n\nRichard.\n\n2017-09-14 Richard Biener \n\n\t* tree-ssa-sccvn.c (visit_phi): Merge undefined values similar\n\tto VN_TOP.\n\n\t* gcc.dg/tree-ssa/ssa-fre-59.c: New testcase.\n\t* gcc.dg/uninit-suppress_2.c: Adjust.\n\t* gcc.dg/tree-ssa/ssa-sccvn-2.c: Likewise.\n\nIndex: gcc/tree-ssa-sccvn.c\n===================================================================\n--- gcc/tree-ssa-sccvn.c\t(revision 252062)\n+++ gcc/tree-ssa-sccvn.c\t(working copy)\n@@ -3860,11 +3860,11 @@ visit_reference_op_store (tree lhs, tree\n static bool\n visit_phi (gimple *phi)\n {\n- bool changed = false;\n- tree result;\n- tree sameval = VN_TOP;\n- bool allsame = true;\n+ tree result, sameval = VN_TOP, seen_undef = NULL_TREE;\n unsigned n_executable = 0;\n+ bool allsame = true;\n+ edge_iterator ei;\n+ edge e;\n \n /* TODO: We could check for this in init_sccvn, and replace this\n with a gcc_assert. */\n@@ -3873,8 +3873,6 @@ visit_phi (gimple *phi)\n \n /* See if all non-TOP arguments have the same value. TOP is\n equivalent to everything, so we can ignore it. */\n- edge_iterator ei;\n- edge e;\n FOR_EACH_EDGE (e, ei, gimple_bb (phi)->preds)\n if (e->flags & EDGE_EXECUTABLE)\n {\n@@ -3884,8 +3882,12 @@ visit_phi (gimple *phi)\n \tif (TREE_CODE (def) == SSA_NAME)\n \t def = SSA_VAL (def);\n \tif (def == VN_TOP)\n-\t continue;\n-\tif (sameval == VN_TOP)\n+\t ;\n+\t/* Ignore undefined defs for sameval but record one. */\n+\telse if (TREE_CODE (def) == SSA_NAME\n+\t\t && ssa_undefined_value_p (def, false))\n+\t seen_undef = def;\n+\telse if (sameval == VN_TOP)\n \t sameval = def;\n \telse if (!expressions_equal_p (def, sameval))\n \t {\n@@ -3893,30 +3895,39 @@ visit_phi (gimple *phi)\n \t break;\n \t }\n }\n- \n- /* If none of the edges was executable or all incoming values are\n- undefined keep the value-number at VN_TOP. If only a single edge\n- is exectuable use its value. */\n- if (sameval == VN_TOP\n- || n_executable == 1)\n- return set_ssa_val_to (PHI_RESULT (phi), sameval);\n \n+\n+ /* If none of the edges was executable keep the value-number at VN_TOP,\n+ if only a single edge is exectuable use its value. */\n+ if (n_executable <= 1)\n+ result = seen_undef ? seen_undef : sameval;\n+ /* If we saw only undefined values create a new undef SSA name to\n+ avoid false equivalences. */\n+ else if (sameval == VN_TOP)\n+ {\n+ gcc_assert (seen_undef);\n+ result = seen_undef;\n+ }\n /* First see if it is equivalent to a phi node in this block. We prefer\n this as it allows IV elimination - see PRs 66502 and 67167. */\n- result = vn_phi_lookup (phi);\n- if (result)\n- changed = set_ssa_val_to (PHI_RESULT (phi), result);\n- /* Otherwise all value numbered to the same value, the phi node has that\n- value. */\n- else if (allsame)\n- changed = set_ssa_val_to (PHI_RESULT (phi), sameval);\n+ else if ((result = vn_phi_lookup (phi)))\n+ ;\n+ /* If all values are the same use that, unless we've seen undefined\n+ values as well and the value isn't constant.\n+ CCP/copyprop have the same restriction to not remove uninit warnings. */\n+ else if (allsame\n+\t && (! seen_undef || is_gimple_min_invariant (sameval)))\n+ result = sameval;\n else\n {\n- vn_phi_insert (phi, PHI_RESULT (phi));\n- changed = set_ssa_val_to (PHI_RESULT (phi), PHI_RESULT (phi));\n+ result = PHI_RESULT (phi);\n+ /* Only insert PHIs that are varying, for constant value numbers\n+ we mess up equivalences otherwise as we are only comparing\n+\t the immediate controlling predicates. */\n+ vn_phi_insert (phi, result);\n }\n \n- return changed;\n+ return set_ssa_val_to (PHI_RESULT (phi), result);\n }\n \n /* Try to simplify RHS using equivalences and constant folding. */\nIndex: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-59.c\n===================================================================\n--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-59.c\t(nonexistent)\n+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-59.c\t(working copy)\n@@ -0,0 +1,14 @@\n+/* { dg-do compile } */\n+/* { dg-options \"-O -fdump-tree-fre1\" } */\n+\n+int i;\n+int foo (int b)\n+{\n+ int j;\n+ i = 1;\n+ if (b)\n+ j = i;\n+ return i - j;\n+}\n+\n+/* { dg-final { scan-tree-dump \"return 0;\" \"fre1\" } } */\nIndex: gcc/testsuite/gcc.dg/uninit-suppress_2.c\n===================================================================\n--- gcc/testsuite/gcc.dg/uninit-suppress_2.c\t(revision 252062)\n+++ gcc/testsuite/gcc.dg/uninit-suppress_2.c\t(working copy)\n@@ -1,5 +1,5 @@\n /* { dg-do compile } */\n-/* { dg-options \"-fno-tree-ccp -fno-tree-vrp -O2 -Wuninitialized -Werror=uninitialized -Wno-error=maybe-uninitialized\" } */\n+/* { dg-options \"-fno-tree-ccp -fno-tree-vrp -fno-tree-fre -fno-tree-pre -fno-code-hoisting -O2 -Wuninitialized -Werror=uninitialized -Wno-error=maybe-uninitialized\" } */\n void blah();\n void bar (int);\n int gflag;\nIndex: gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c\n===================================================================\n--- gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c\t(revision 252062)\n+++ gcc/testsuite/gcc.dg/tree-ssa/ssa-sccvn-2.c\t(working copy)\n@@ -21,4 +21,4 @@ int vnum_test8(int *data)\n } \n /* We should eliminate m - n, and set n = n + k into n = m, and\n set p to 0 */\n-/* { dg-final { scan-tree-dump-times \"Eliminated: 4\" 1 \"fre1\"} } */\n+/* { dg-final { scan-tree-dump-times \"Eliminated: 5\" 1 \"fre1\"} } */","headers":{"Return-Path":"","X-Original-To":"incoming@patchwork.ozlabs.org","Delivered-To":["patchwork-incoming@bilbo.ozlabs.org","mailing list gcc-patches@gcc.gnu.org"],"Authentication-Results":["ozlabs.org;\n\tspf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org\n\t(client-ip=209.132.180.131; helo=sourceware.org;\n\tenvelope-from=gcc-patches-return-462127-incoming=patchwork.ozlabs.org@gcc.gnu.org;\n\treceiver=)","ozlabs.org; dkim=pass (1024-bit key;\n\tunprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org\n\theader.b=\"sOHuK45E\"; dkim-atps=neutral","sourceware.org; auth=none"],"Received":["from sourceware.org (server1.sourceware.org [209.132.180.131])\n\t(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256\n\tbits)) (No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 3xtH731P50z9sPs\n\tfor ;\n\tThu, 14 Sep 2017 21:56:12 +1000 (AEST)","(qmail 70525 invoked by alias); 14 Sep 2017 11:56:05 -0000","(qmail 69992 invoked by uid 89); 14 Sep 2017 11:56:04 -0000","from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by\n\tsourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP;\n\tThu, 14 Sep 2017 11:56:02 +0000","from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254])\tby\n\tmx1.suse.de (Postfix) with ESMTP id 16C02AB9B\tfor\n\t; Thu, 14 Sep 2017 11:56:00 +0000 (UTC)"],"DomainKey-Signature":"a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:date\n\t:from:to:subject:in-reply-to:message-id:references:mime-version\n\t:content-type; q=dns; s=default; b=N+0WRBDbZT5fdxDCECjSrX1f3pr4d\n\tqmMZ2711fEeNDgZlzSYFKLIbWiTebOIWueaq5Sa8VdicVL5Aom7OZ4KDyw5FqnAv\n\thaWvs+SPx3044xN/OE2Pv3wpdOsZroJAFjCVkQNmlrE9vD+PyuakPUmaDABXXP6c\n\tlRYZkX3RKVL/tU=","DKIM-Signature":"v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id\n\t:list-unsubscribe:list-archive:list-post:list-help:sender:date\n\t:from:to:subject:in-reply-to:message-id:references:mime-version\n\t:content-type; s=default; bh=5X20fBrO7wUq6G0ziR12dbhi1qQ=; b=sOH\n\tuK45E7QbAXH62NWryF2a3z7I+O/KpTmUCvcyCrpH4jj76167gSZjtKKF19xTxnSX\n\tXcLPGrDd9KnpHjYoVWINeSMfjCIKUPrbSbCmqoEEl51dGOosVlQuUCkgfIw6u7sz\n\tDhfWQeqSFfxgwRhxI6qM2itpipQlpIFH5A8KWcTc=","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","X-Virus-Found":"No","X-Spam-SWARE-Status":"No, score=-11.1 required=5.0 tests=BAYES_00, GIT_PATCH_2,\n\tGIT_PATCH_3, KAM_ASCII_DIVIDERS, RP_MATCHES_RCVD,\n\tSPF_PASS autolearn=ham version=3.3.2 spammy=Wno-error,\n\twno-error, Wnoerror, wnoerror","X-HELO":"mx1.suse.de","Date":"Thu, 14 Sep 2017 13:55:59 +0200 (CEST)","From":"Richard Biener ","To":"gcc-patches@gcc.gnu.org","Subject":"Re: [PATCH] Enhance PHI processing in VN","In-Reply-To":"","Message-ID":"","References":"\n\t","User-Agent":"Alpine 2.20 (LSU 67 2015-01-07)","MIME-Version":"1.0","Content-Type":"text/plain; charset=US-ASCII"}}]