* RFA: Improve jump threading #2 of N
@ 2011-04-21 16:10 Jeff Law
2011-04-21 17:44 ` Steven Bosscher
2011-04-22 11:59 ` Richard Guenther
0 siblings, 2 replies; 6+ messages in thread
From: Jeff Law @ 2011-04-21 16:10 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1102 bytes --]
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
For some dumb reason I thought handling threading through a SWITCH_EXPR
was hard in VRP; that's definitely not the case, it's no more difficult
than handling a COND_EXPR.
This patch allows tree-vrp.c to thread through a SWITCH_EXPR when we
know the switch index via a particular path. Most of these would have
eventually been caught by DOM, but we get to pick up more secondary
effects if we can catch them in VRP.
Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
trunk?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNsFGKAAoJEBRtltQi2kC7wP4IAJZ6e/jF5WAnFdG5/G6lWdEp
D1mBlaFvrSgAXp/Qx9y8uLQfnpzSvcgb59naTH2p+rDILjAs9Bw1eXZN0MCwTN4H
tylFm3w4a9BMzHbzgiwGzDBTkUyzIQyQ1XzqSHbOTWtzEuFGbAmRzSgDoFPbZEPD
cWXsh7yRLr/aqOFLCoEbN/Wp87aBDSXi+I7d5rU+la97En3FWBSNku84dZf1F+8C
9qW4wCW7lX1LVnWy3LmeSxXf0k9JmJGkUvdmSr2TYtZVPvPLqHg97NOWG9CAfUVO
cTZW5QOFuyEGg/vbYOFmfWRI7uw+YjggV/v0LzUYjRV00fj+rygjgUfgA5f3rGA=
=NPtm
-----END PGP SIGNATURE-----
[-- Attachment #2: P --]
[-- Type: text/plain, Size: 2566 bytes --]
* tree-vrp.c (identify_jump_threads): Handle GIMPLE_SWITCH too.
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 172644)
--- tree-vrp.c (working copy)
*************** identify_jump_threads (void)
*** 7555,7579 ****
may be some value in handling SWITCH_EXPR here, I doubt it's
terribly important. */
last = gsi_stmt (gsi_last_bb (bb));
- if (gimple_code (last) != GIMPLE_COND)
- continue;
! /* We're basically looking for any kind of conditional with
integral or pointer type arguments. Note the type of the second
argument will be the same as the first argument, so no need to
check it explicitly. */
! if (TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
! && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
! || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
! && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
! || is_gimple_min_invariant (gimple_cond_rhs (last))))
{
edge_iterator ei;
/* We've got a block with multiple predecessors and multiple
! successors which also ends in a suitable conditional. For
! each predecessor, see if we can thread it to a specific
! successor. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
/* Do not thread across back edges or abnormal edges
--- 7555,7579 ----
may be some value in handling SWITCH_EXPR here, I doubt it's
terribly important. */
last = gsi_stmt (gsi_last_bb (bb));
! /* We're basically looking for a switch or any kind of conditional with
integral or pointer type arguments. Note the type of the second
argument will be the same as the first argument, so no need to
check it explicitly. */
! if (gimple_code (last) == GIMPLE_SWITCH
! || (gimple_code (last) == GIMPLE_COND
! && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
! && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
! || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
! && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
! || is_gimple_min_invariant (gimple_cond_rhs (last)))))
{
edge_iterator ei;
/* We've got a block with multiple predecessors and multiple
! successors which also ends in a suitable conditional or
! switch statement. For each predecessor, see if we can thread
! it to a specific successor. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
/* Do not thread across back edges or abnormal edges
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: RFA: Improve jump threading #2 of N
2011-04-21 16:10 RFA: Improve jump threading #2 of N Jeff Law
@ 2011-04-21 17:44 ` Steven Bosscher
2011-04-21 19:03 ` Jeff Law
2011-04-21 20:04 ` Jeff Law
2011-04-22 11:59 ` Richard Guenther
1 sibling, 2 replies; 6+ messages in thread
From: Steven Bosscher @ 2011-04-21 17:44 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
> trunk?
Would this also fix PR18046?
Ciao!
Steven
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: RFA: Improve jump threading #2 of N
2011-04-21 17:44 ` Steven Bosscher
@ 2011-04-21 19:03 ` Jeff Law
2011-04-21 20:04 ` Jeff Law
1 sibling, 0 replies; 6+ messages in thread
From: Jeff Law @ 2011-04-21 19:03 UTC (permalink / raw)
To: Steven Bosscher; +Cc: gcc-patches
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 04/21/11 11:26, Steven Bosscher wrote:
>> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
>> trunk?
>
> Would this also fix PR18046?
Not right now.
If we look at VRP2 (and this only affects VRP's jump threading) we have:
SSA form after inserting ASSERT_EXPRs
bar ()
{
int prephitmp.5;
int pretmp.4;
int i.0;
# BLOCK 2 freq:10000
# PRED: ENTRY [100.0%] (fallthru,exec)
# VUSE <.MEM_5(D)>
i.0_1 = i;
switch (i.0_1) <default: <L2>, case 0: <L0>>
# SUCC: 4 [71.0%] (exec) 3 [29.0%] (exec)
# BLOCK 3 freq:2900
# PRED: 2 [29.0%] (exec)
<L0>:
i.0_2 = ASSERT_EXPR <i.0_1, i.0_1 == 0>;
# .MEM_6 = VDEF <.MEM_5(D)>
foo ();
# VUSE <.MEM_6>
pretmp.4_8 = i;
# SUCC: 4 [100.0%] (fallthru,exec)
# BLOCK 4 freq:10000
# PRED: 2 [71.0%] (exec) 3 [100.0%] (fallthru,exec)
# .MEM_3 = PHI <.MEM_5(D)(2), .MEM_6(3)>
# prephitmp.5_9 = PHI <i.0_1(2), pretmp.4_8(3)>
<L2>:
switch (prephitmp.5_9) <default: <L6>, case 0: <L4>>
# SUCC: 6 [61.0%] (exec) 5 [39.0%] (exec)
# BLOCK 5 freq:3898
# PRED: 4 [39.0%] (exec)
<L4>:
# .MEM_7 = VDEF <.MEM_3>
foo ();
# SUCC: 6 [100.0%] (fallthru,exec)
# BLOCK 6 freq:10000
# PRED: 4 [61.0%] (exec) 5 [100.0%] (fallthru,exec)
# .MEM_4 = PHI <.MEM_3(4), .MEM_7(5)>
<L6>:
# VUSE <.MEM_4>
return;
# SUCC: EXIT [100.0%]
}
Note the lack of range information for i.0_1 for the default case of the
first switch. That's going to be a prerequisite for threading through
the second switch which its reached via the default path from the first
switch.
jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNsGviAAoJEBRtltQi2kC79/AH/3jrM+zArf6l9tUlyO8dFF4T
IBfJW8oq94DQfwyahEh6yk1Qeh6YkV3e5GsmIpI3GAzimhekoXEKchdqbXvYfSvC
JNk5FmTlv5rc4SUL+rPLpOeVNxgj46LXjlgUh3d3Ino5PXW8uhal4qidMEPxhonA
HHgbwuvYdhLWrJYJ35mEP5HPQGLRTVQtCdpDz+8CXl9D8Cr87y93W+cOEXckhOGI
yJeUhTRYftVCOwDdVfzEgqM+3OkGq6PE0TEMh/OUA2zDfeTVfQ8/vv9T521X/DJW
v9a7JN0gQM+6Hp5MmpMnSpKCfmeKKXUpvisT/Cr0pHeXKthmbm1nwRFoHalYp5g=
=6WXP
-----END PGP SIGNATURE-----
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: RFA: Improve jump threading #2 of N
2011-04-21 17:44 ` Steven Bosscher
2011-04-21 19:03 ` Jeff Law
@ 2011-04-21 20:04 ` Jeff Law
1 sibling, 0 replies; 6+ messages in thread
From: Jeff Law @ 2011-04-21 20:04 UTC (permalink / raw)
To: Steven Bosscher; +Cc: gcc-patches
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 04/21/11 11:26, Steven Bosscher wrote:
>> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
>> trunk?
>
> Would this also fix PR18046?
Also note that the assertion machinery doesn't really have the concept
of anti-ranges, much less the ability to build up an anti-range by
repeatedly excluding part of a range (say as we iterate over the labels
that go somewhere other than the default).
So while it wouldn't be terribly hard to deal with this testcase, it's
not going to be very effective on real world code. To be effective on
real world code we need to:
1. Lower trivial switches
2. build up anti-ranges as we encounter case labels that go elsewhere
3. track distinct values in a range at meet points
If you look at something like Coverity it clearly does this kind of
analysis and represents a clear case where Coverity can do better
localized code analysis.
jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNsIZVAAoJEBRtltQi2kC7004H/jjGdzr1+WM5z+XMSGzLlLhF
crz7ALIi/Ul+icUdlre+F1gUofAp+8g210uYESbeEJvPTtX7lBS0dQe+TX6r1Xvr
7kjKe2/iP1fl7lQzkNnbOqXygbmEFKG1ySwKIg0XkD7he58BDSAOaC1OgArpJAvI
ppYZAO1Tkkqy/38+Jdj2emFbiayFqbHmPid0QaoMywDkxl3a5ZElQo1+h2jpUEir
is8fb4tULoiswD4xL9PgNw5xFgDfqUUjXYVDEBWgQDI0DRaXJd/utO9C+Rg2to2S
jxFnrZ8ljSZ++KapVHSjDrRSiTm+tDFaGxRHz1+8VtBn9siBHs4yFoZ1VjgbrZ4=
=bNEt
-----END PGP SIGNATURE-----
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: RFA: Improve jump threading #2 of N
2011-04-21 16:10 RFA: Improve jump threading #2 of N Jeff Law
2011-04-21 17:44 ` Steven Bosscher
@ 2011-04-22 11:59 ` Richard Guenther
2011-04-25 20:50 ` Jeff Law
1 sibling, 1 reply; 6+ messages in thread
From: Richard Guenther @ 2011-04-22 11:59 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Thu, Apr 21, 2011 at 5:47 PM, Jeff Law <law@redhat.com> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
>
> For some dumb reason I thought handling threading through a SWITCH_EXPR
> was hard in VRP; that's definitely not the case, it's no more difficult
> than handling a COND_EXPR.
>
> This patch allows tree-vrp.c to thread through a SWITCH_EXPR when we
> know the switch index via a particular path. Most of these would have
> eventually been caught by DOM, but we get to pick up more secondary
> effects if we can catch them in VRP.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
> trunk?
Ok. Can you add a testcase?
Thanks,
Richard.
>
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJNsFGKAAoJEBRtltQi2kC7wP4IAJZ6e/jF5WAnFdG5/G6lWdEp
> D1mBlaFvrSgAXp/Qx9y8uLQfnpzSvcgb59naTH2p+rDILjAs9Bw1eXZN0MCwTN4H
> tylFm3w4a9BMzHbzgiwGzDBTkUyzIQyQ1XzqSHbOTWtzEuFGbAmRzSgDoFPbZEPD
> cWXsh7yRLr/aqOFLCoEbN/Wp87aBDSXi+I7d5rU+la97En3FWBSNku84dZf1F+8C
> 9qW4wCW7lX1LVnWy3LmeSxXf0k9JmJGkUvdmSr2TYtZVPvPLqHg97NOWG9CAfUVO
> cTZW5QOFuyEGg/vbYOFmfWRI7uw+YjggV/v0LzUYjRV00fj+rygjgUfgA5f3rGA=
> =NPtm
> -----END PGP SIGNATURE-----
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: RFA: Improve jump threading #2 of N
2011-04-22 11:59 ` Richard Guenther
@ 2011-04-25 20:50 ` Jeff Law
0 siblings, 0 replies; 6+ messages in thread
From: Jeff Law @ 2011-04-25 20:50 UTC (permalink / raw)
To: Richard Guenther; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1376 bytes --]
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 04/22/11 02:56, Richard Guenther wrote:
> On Thu, Apr 21, 2011 at 5:47 PM, Jeff Law <law@redhat.com> wrote:
>
> For some dumb reason I thought handling threading through a SWITCH_EXPR
> was hard in VRP; that's definitely not the case, it's no more difficult
> than handling a COND_EXPR.
>
> This patch allows tree-vrp.c to thread through a SWITCH_EXPR when we
> know the switch index via a particular path. Most of these would have
> eventually been caught by DOM, but we get to pick up more secondary
> effects if we can catch them in VRP.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu. OK for
> trunk?
>
>> Ok. Can you add a testcase?
Attached is the patch checked in (no functional changes since the
submission, just the new testcase).
Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
iQEcBAEBAgAGBQJNtdF2AAoJEBRtltQi2kC7VwYH/2pIkRUesXHnCCJ/GeqptZTM
J3aExZeG3kuxAEaWcmlPvurfUWoZVI56uM4igEBKKHl857Y3Qx/EMfHNaTXRHbDA
lzos+rMRpT5cPbFfpvsSoDEyS07LDYA4VsMQ910whiNhFKC14+HkXHH13PA8Enr9
gID8VviapiGh87CeCoAK/OsS72o8T0QBqsOKj0Ww+ZzHjqCSQnHPt0COw4qmxfij
gsZQIdFtYwzV+LSwu3KpO5jmXe2IPtT36vSvtkGmQgEJ5S0L4Sc66yuiLY3p8SEh
Di5ajN0m9ZWcaKvLKZVFRrv3eAXo8/hQp2Jrs+HDA8YTwIRKHj9bR4oJVuSoHwM=
=+Whu
-----END PGP SIGNATURE-----
[-- Attachment #2: P --]
[-- Type: text/plain, Size: 4476 bytes --]
Index: ChangeLog
===================================================================
*** ChangeLog (revision 172937)
--- ChangeLog (working copy)
***************
*** 1,3 ****
--- 1,7 ----
+ 2011-04-25 Jeff Law <law@redhat.com>
+
+ * tree-vrp.c (identify_jump_threads): Handle GIMPLE_SWITCH too.
+
2011-04-25 Jan Kratochvil <jan.kratochvil@redhat.com>
* system.h (ENUM_BITFIELD): Remove.
Index: tree-vrp.c
===================================================================
*** tree-vrp.c (revision 172937)
--- tree-vrp.c (working copy)
*************** identify_jump_threads (void)
*** 7555,7579 ****
may be some value in handling SWITCH_EXPR here, I doubt it's
terribly important. */
last = gsi_stmt (gsi_last_bb (bb));
- if (gimple_code (last) != GIMPLE_COND)
- continue;
! /* We're basically looking for any kind of conditional with
integral or pointer type arguments. Note the type of the second
argument will be the same as the first argument, so no need to
check it explicitly. */
! if (TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
! && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
! || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
! && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
! || is_gimple_min_invariant (gimple_cond_rhs (last))))
{
edge_iterator ei;
/* We've got a block with multiple predecessors and multiple
! successors which also ends in a suitable conditional. For
! each predecessor, see if we can thread it to a specific
! successor. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
/* Do not thread across back edges or abnormal edges
--- 7555,7579 ----
may be some value in handling SWITCH_EXPR here, I doubt it's
terribly important. */
last = gsi_stmt (gsi_last_bb (bb));
! /* We're basically looking for a switch or any kind of conditional with
integral or pointer type arguments. Note the type of the second
argument will be the same as the first argument, so no need to
check it explicitly. */
! if (gimple_code (last) == GIMPLE_SWITCH
! || (gimple_code (last) == GIMPLE_COND
! && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
! && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
! || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
! && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
! || is_gimple_min_invariant (gimple_cond_rhs (last)))))
{
edge_iterator ei;
/* We've got a block with multiple predecessors and multiple
! successors which also ends in a suitable conditional or
! switch statement. For each predecessor, see if we can thread
! it to a specific successor. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
/* Do not thread across back edges or abnormal edges
Index: testsuite/gcc.dg/tree-ssa/vrp56.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/vrp56.c (revision 0)
--- testsuite/gcc.dg/tree-ssa/vrp56.c (revision 0)
***************
*** 0 ****
--- 1,42 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-vrp1-details" } */
+ typedef struct basic_block_def *basic_block;
+ struct basic_block_def;
+ struct edge_def;
+ typedef struct edge_def *edge;
+ typedef struct VEC_edge_base
+ {
+ unsigned num;
+ } VEC_edge_base;
+ typedef struct VEC_edge_none
+ {
+ VEC_edge_base base;
+ } VEC_edge_none;
+ static __inline__ unsigned
+ VEC_edge_base_length (VEC_edge_base * vec_)
+ {
+ return vec_ ? vec_->num : 0;
+ }
+
+ typedef struct VEC_edge_gc
+ {
+ VEC_edge_base base;
+ } VEC_edge_gc;
+ struct basic_block_def
+ {
+ VEC_edge_gc *succs;
+ };
+
+ unsigned char
+ cleanup_empty_eh (basic_block bb)
+ {
+ edge e_out;
+ switch (VEC_edge_base_length (&bb->succs->base))
+ {
+ case 1:
+ foo ();
+ }
+ }
+ /* { dg-final { scan-tree-dump-times "Threaded" 2 "vrp1"} } */
+ /* { dg-final { cleanup-tree-dump "vrp1" } } */
+
Index: testsuite/ChangeLog
===================================================================
*** testsuite/ChangeLog (revision 172937)
--- testsuite/ChangeLog (working copy)
***************
*** 1,3 ****
--- 1,7 ----
+ 2011-04-25 Jeff Law <law@redhat.com>
+
+ * gcc.dg/tree-ssa/vrp56.c: new test.
+
2011-04-25 Rainer Orth <ro@CeBiTec.Uni-Bielefeld.DE>
* go.test/go-test.exp (go-set-goarch): Accept mips*-*-*.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2011-04-25 19:54 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-04-21 16:10 RFA: Improve jump threading #2 of N Jeff Law
2011-04-21 17:44 ` Steven Bosscher
2011-04-21 19:03 ` Jeff Law
2011-04-21 20:04 ` Jeff Law
2011-04-22 11:59 ` Richard Guenther
2011-04-25 20:50 ` Jeff Law
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).