From: Richard Biener <rguenther@suse.de>
To: Jiufu Guo <guojiufu@linux.ibm.com>
Cc: gcc-patches@gcc.gnu.org, Jakub Jelinek <jakub@redhat.com>,
Daniel Berlin <dberlin@dberlin.org>,
segher@kernel.crashing.org, wschmidt@linux.ibm.com,
law@redhat.com
Subject: Re: [PATCH] A jump threading opportunity for condition branch
Date: Wed, 22 May 2019 12:38:00 -0000 [thread overview]
Message-ID: <alpine.LSU.2.20.1905221427050.10704@zhemvz.fhfr.qr> (raw)
In-Reply-To: <1558446288-52444-1-git-send-email-guojiufu@linux.ibm.com>
On Tue, 21 May 2019, Jiufu Guo wrote:
> Hi,
>
> This patch implements a new opportunity of jump threading for PR77820.
> In this optimization, conditional jumps are merged with unconditional jump.
> And then moving CMP result to GPR is eliminated.
>
> It looks like below:
>
> <P0>
> p0 = a CMP b
> goto <X>;
>
> <P1>
> p1 = c CMP d
> goto <X>;
>
> <X>
> # phi = PHI <p0 (P0), p1 (P1)>
> if (phi != 0) goto <Y>; else goto <Z>;
>
> Could be transformed to:
>
> <P0>
> p0 = a CMP b
> if (p0 != 0) goto <Y>; else goto <Z>;
>
> <P1>
> p1 = c CMP d
> if (p1 != 0) goto <Y>; else goto <Z>;
>
>
> This optimization eliminates:
> 1. saving CMP result: p0 = a CMP b.
> 2. additional CMP on branch: if (phi != 0).
> 3. converting CMP result if there is phi = (INT_CONV) p0 if there is.
>
> Bootstrapped and tested on powerpc64le with no regressions(one case is improved)
> and new testcases are added. Is this ok for trunk?
>
> Thanks!
> Jiufu Guo
>
>
> [gcc]
> 2019-05-21 Jiufu Guo <guojiufu@linux.ibm.com>
> Lijia He <helijia@linux.ibm.com>
>
> PR tree-optimization/77820
> * tree-ssa-threadedge.c (cmp_from_unconditional_block): New function.
> * tree-ssa-threadedge.c (is_trivial_join_block): New function.
> * tree-ssa-threadedge.c (thread_across_edge): Call is_trivial_join_block.
>
> [gcc/testsuite]
> 2019-05-21 Jiufu Guo <guojiufu@linux.ibm.com>
> Lijia He <helijia@linux.ibm.com>
>
> PR tree-optimization/77820
> * gcc.dg/tree-ssa/phi_on_compare-1.c: New testcase.
> * gcc.dg/tree-ssa/phi_on_compare-2.c: New testcase.
> * gcc.dg/tree-ssa/phi_on_compare-3.c: New testcase.
> * gcc.dg/tree-ssa/phi_on_compare-4.c: New testcase.
> * gcc.dg/tree-ssa/split-path-6.c: Update testcase.
>
> ---
> gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c | 32 +++++++++
> gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c | 27 +++++++
> gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c | 31 ++++++++
> gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c | 40 +++++++++++
> gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c | 2 +-
> gcc/tree-ssa-threadedge.c | 91 +++++++++++++++++++++++-
> 6 files changed, 219 insertions(+), 4 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
> new file mode 100644
> index 0000000..ad4890a
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-1.c
> @@ -0,0 +1,32 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fdump-tree-vrp1" } */
> +
> +void g (int);
> +void g1 (int);
> +
> +void
> +f (long a, long b, long c, long d, long x)
> +{
> + _Bool t;
> + if (x)
> + {
> + g (a + 1);
> + t = a < b;
> + c = d + x;
> + }
> + else
> + {
> + g (b + 1);
> + a = c + d;
> + t = c > d;
> + }
> +
> + if (t)
> + {
> + g1 (c);
> + }
> +
> + g (a);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
> new file mode 100644
> index 0000000..ca67d65
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-2.c
> @@ -0,0 +1,27 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fdump-tree-vrp1" } */
> +
> +void g (void);
> +void g1 (void);
> +
> +void
> +f (long a, long b, long c, long d, int x)
> +{
> + _Bool t;
> + if (x)
> + {
> + t = c < d;
> + }
> + else
> + {
> + t = a < b;
> + }
> +
> + if (t)
> + {
> + g1 ();
> + g ();
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
> new file mode 100644
> index 0000000..a126e97
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-3.c
> @@ -0,0 +1,31 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fdump-tree-vrp1" } */
> +
> +void g (void);
> +void g1 (void);
> +
> +void
> +f (long a, long b, long c, long d, int x)
> +{
> + int t;
> + if (x)
> + {
> + t = a < b;
> + }
> + else if (d == x)
> + {
> + t = c < b;
> + }
> + else
> + {
> + t = d > c;
> + }
> +
> + if (t)
> + {
> + g1 ();
> + g ();
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c
> new file mode 100644
> index 0000000..5a50c2d
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/phi_on_compare-4.c
> @@ -0,0 +1,40 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Ofast -fdump-tree-vrp1" } */
> +
> +void g (int);
> +void g1 (int);
> +
> +void
> +f (long a, long b, long c, long d, int x)
> +{
> + int t;
> + _Bool l1 = 0, l2 = 0;
> + if (x)
> + {
> + g (a);
> + c = a + b;
> + t = a < b;
> + l1 = 1;
> + }
> + else
> + {
> + g1 (b);
> + t = c > d;
> + d = c + b;
> + l2 = 1;
> + }
> +
> + if (t)
> + {
> + if (l1 | l2)
> + g1 (c);
> + }
> + else
> + {
> + g (d);
> + g1 (a + b);
> + }
> + g (c + d);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Removing basic block" 1 "vrp1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c
> index e9b4f26..1d7b587 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c
> @@ -69,4 +69,4 @@ lookharder (string)
> }
> }
>
> -/* { dg-final { scan-tree-dump-times "Duplicating join block" 3 "split-paths" } } */
> +/* { dg-final { scan-tree-dump-times "Duplicating join block" 2 "split-paths" } } */
> diff --git a/gcc/tree-ssa-threadedge.c b/gcc/tree-ssa-threadedge.c
> index c3ea2d6..23000f6 100644
> --- a/gcc/tree-ssa-threadedge.c
> +++ b/gcc/tree-ssa-threadedge.c
> @@ -1157,6 +1157,90 @@ thread_through_normal_block (edge e,
> return 0;
> }
>
> +/* Return true if PHI's INDEX-th incoming value is a CMP, and the CMP is
> + defined in the incoming basic block. Otherwise return false. */
> +static bool
> +cmp_from_unconditional_block (gphi *phi, int index)
> +{
> + tree value = gimple_phi_arg_def (phi, index);
> + if (!(TREE_CODE (value) == SSA_NAME && has_single_use (value)))
> + return false;
Not sure why we should reject a constant here but I guess we
expect it to find a simplified condition anyways ;)
> +
> + gimple *def = SSA_NAME_DEF_STMT (value);
> +
> + if (!is_gimple_assign (def))
> + return false;
> +
> + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)))
> + {
> + value = gimple_assign_rhs1 (def);
> + if (!(TREE_CODE (value) == SSA_NAME && has_single_use (value)))
> + return false;
> +
> + def = SSA_NAME_DEF_STMT (value);
> +
> + if (!is_gimple_assign (def))
> + return false;
too much vertial space.
> + }
> +
> + if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
> + return false;
> +
> + /* Check if phi's incoming value is defined in the incoming basic_block. */
> + edge e = gimple_phi_arg_edge (phi, index);
> + if (def->bb != e->src)
> + return false;
why does this matter?
> +
> + if (!single_succ_p (def->bb))
> + return false;
Or this? The actual threading will ensure this will hold true.
> + return true;
> +}
> +
> +/* There are basic blocks look like:
> + <P0>
> + p0 = a CMP b ; or p0 = (INT)( a CMP b)
> + goto <X>;
> +
> + <P1>
> + p1 = c CMP d
> + goto <X>;
> +
> + <X>
> + # phi = PHI <p0 (P0), p1 (P1)>
> + if (phi != 0) goto <Y>; else goto <Z>;
> +
> + Then, <X>: a trivial join block.
> +
> + Check if BB is <X> in like above. */
> +
> +bool
> +is_trivial_join_block (basic_block bb)
I'd make this work on a specific edge.
edge_forwards_conditional_to_conditional_jump_through_empty_bb_p (edge e)
{
basic_block b = e->dest;
maybe too elaborate name ;)
> +{
> + gimple *gs = last_and_only_stmt (bb);
> + if (gs == NULL)
> + return false;
> +
> + if (gimple_code (gs) != GIMPLE_COND)
> + return false;
> +
> + tree cond = gimple_cond_lhs (gs);
> +
> + if(TREE_CODE (cond) != SSA_NAME)
> + return false;
space after if( too much vertical space in this function
for my taste btw.
For the forwarding to work we want a NE_EXPR or EQ_EXPR
as gimple_cond_code and integer_one_p or integer_zero_p
gimple_cond_rhs.
> +
> + if (gimple_code (SSA_NAME_DEF_STMT (cond)) != GIMPLE_PHI)
> + return false;
> +
> + gphi *phi = as_a<gphi *> (SSA_NAME_DEF_STMT (cond));
I think to match your pattern you want to check that
gimple_bb (phi) == bb as well here.
> + for (unsigned int i = 0; i < phi->nargs; i++)
> + if (!cmp_from_unconditional_block (phi, i))
Just process the incoming edge argument and inline the
helper. You can use PHI_ARG_DEF_FROM_EDGE here.
Thanks for integrating this into jump-threading - it does look
like a good fit.
How often does this trigger during bootstrap?
Thanks,
Richard.
next prev parent reply other threads:[~2019-05-22 12:38 UTC|newest]
Thread overview: 38+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-05-21 13:45 Jiufu Guo
2019-05-22 12:38 ` Richard Biener [this message]
2019-05-23 12:06 ` Jiufu Guo
2019-05-23 12:11 ` Richard Biener
2019-05-23 14:40 ` Jiufu Guo
2019-05-24 12:45 ` Richard Biener
2019-05-24 14:52 ` Jiufu Guo
2019-05-28 14:07 ` [PATCH V2] " Jiufu Guo
2019-05-29 1:51 ` Jiufu Guo
2019-05-29 12:40 ` Richard Biener
2019-05-29 19:47 ` Jeff Law
2019-05-30 15:09 ` Jiufu Guo
2019-05-30 23:55 ` Jeff Law
2019-05-31 7:34 ` Richard Biener
2019-06-04 3:03 ` Jiufu Guo
2019-05-30 15:34 ` Jeff Law
2019-06-03 2:18 ` [PATCH V3] " Jiufu Guo
2019-06-04 5:30 ` [PATCH V4] " Jiufu Guo
2019-06-13 18:56 ` Jeff Law
2019-06-14 12:51 ` Jiufu Guo
2019-06-14 16:34 ` Jeff Law
2019-05-29 20:26 ` [PATCH] " Jeff Law
2019-05-30 6:57 ` Richard Biener
2019-05-30 6:58 ` Jiufu Guo
2019-05-30 14:59 ` Jeff Law
2019-05-30 15:03 ` Jeff Law
2019-05-29 20:22 ` Jeff Law
2019-05-30 6:40 ` Jiufu Guo
2019-05-30 6:44 ` Richard Biener
2019-05-30 20:17 ` Jeff Law
2019-05-31 7:30 ` Richard Biener
2019-05-31 15:28 ` Jeff Law
2019-06-04 5:19 ` Jiufu Guo
2019-06-04 7:07 ` Richard Biener
2019-06-07 0:05 ` Jeff Law
2019-05-29 20:18 ` Jeff Law
2019-05-30 6:41 ` Richard Biener
2019-05-29 20:12 ` Jeff Law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=alpine.LSU.2.20.1905221427050.10704@zhemvz.fhfr.qr \
--to=rguenther@suse.de \
--cc=dberlin@dberlin.org \
--cc=gcc-patches@gcc.gnu.org \
--cc=guojiufu@linux.ibm.com \
--cc=jakub@redhat.com \
--cc=law@redhat.com \
--cc=segher@kernel.crashing.org \
--cc=wschmidt@linux.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).