public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/18046] New: Missed jump threading optimization
@ 2004-10-18 12:16 steven at gcc dot gnu dot org
2004-10-18 12:52 ` [Bug tree-optimization/18046] " pinskia at gcc dot gnu dot org
` (6 more replies)
0 siblings, 7 replies; 8+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-10-18 12:16 UTC (permalink / raw)
To: gcc-bugs
Filed under unknown since there is no version tag for the
tree-cleanup-branch.
The problem probably also exists on mainline, but I have
not tried it there.
Consider this code,
-----------------------------------------------------
extern void foo (void);
extern int i;
void
bar (void)
{
switch (i)
{
case 0:
foo ();
break;
case 1:
break;
}
switch (i)
{
case 0:
foo ();
break;
case 1:
break;
}
}
-----------------------------------------------------
This gives the following .dse2 dump:
;; Function bar (bar)
bar ()
{
int i.0;
<bb 0>:
# VUSE <i_2>;
i.0_3 = i;
switch (i.0_3)
{
case 0: goto <L0>;
default : goto <L1>;
}
<L0>:;
# i_6 = V_MAY_DEF <i_2>;
foo ();
# i_1 = PHI <i_2(0), i_6(1)>;
<L1>:;
# VUSE <i_1>;
i.0_4 = i;
switch (i.0_4)
{
case 0: goto <L4>;
default : goto <L5>;
}
<L4>:;
# i_5 = V_MAY_DEF <i_1>;
foo ();
<L5>:;
return;
}
If the first switch goes through the default case, the
switch condition "i" is not call clobbered by the call
to "foo ()" so in the second switch "i" is unchanged and
we can thread the jump.
We don't catch this jump threading opportunity on trees,
but we *do* catch it on RTL. This is *the* major source
of missed jump threads on the tree-cleanup-branch (we
catch rougly a thousand of these on the cc1-i file set).
If we teach the tree optimizers to catch this case, we
can almost certainly kill the RTL thread_jump junk on the
tree-cleanup-branch.
--
Summary: Missed jump threading optimization
Product: gcc
Version: unknown
Status: UNCONFIRMED
Keywords: missed-optimization, alias, TREE
Severity: normal
Priority: P2
Component: tree-optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: steven at gcc dot gnu dot org
CC: dnovillo at redhat dot com,gcc-bugs at gcc dot gnu dot
org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
@ 2004-10-18 12:52 ` pinskia at gcc dot gnu dot org
2004-10-18 13:22 ` steven at gcc dot gnu dot org
` (5 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-10-18 12:52 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-10-18 12:52 -------
Confirmed. To summarize what the code should look like:
extern void foo (void);
extern int i;
void
bar (void)
{
switch (i)
{
case 0:
foo ();
break;
default:
goto other_block;
}
switch (i)
{
case 0:
foo ();
break;
default:
other_block:
break;
}
}
--
What |Removed |Added
----------------------------------------------------------------------------
Severity|normal |enhancement
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2004-10-18 12:52:47
date| |
Summary|Missed jump threading |Missed jump threading
|optimization |optimization
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
2004-10-18 12:52 ` [Bug tree-optimization/18046] " pinskia at gcc dot gnu dot org
@ 2004-10-18 13:22 ` steven at gcc dot gnu dot org
2004-10-18 17:30 ` steven at gcc dot gnu dot org
` (4 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-10-18 13:22 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-10-18 13:22 -------
Might I propose we don't deal with this as an enhancement
request but as a "normal" bug? Killing the jump threader
in cfgcleanup.c would be a mighty feat, it's one of the
slowest parts of the cfgcleanup on RTL (and IIRC it's one
of the quadratic bottleneckt).
Otherwise, perhaps I should (have) add(ed) the compile
time hog keyword...
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
2004-10-18 12:52 ` [Bug tree-optimization/18046] " pinskia at gcc dot gnu dot org
2004-10-18 13:22 ` steven at gcc dot gnu dot org
@ 2004-10-18 17:30 ` steven at gcc dot gnu dot org
2004-10-18 18:31 ` law at redhat dot com
` (3 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-10-18 17:30 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-10-18 17:30 -------
Diego told me to bug Law. Obedient as I always am, I hereby
do so :-)
Jeff, this is a missed jump threading opportunity, the default
case can be threaded here. Any ideas how to fix this?
--
What |Removed |Added
----------------------------------------------------------------------------
CC| |law at redhat dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
` (2 preceding siblings ...)
2004-10-18 17:30 ` steven at gcc dot gnu dot org
@ 2004-10-18 18:31 ` law at redhat dot com
2004-10-18 22:50 ` stevenb at suse dot de
` (2 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: law at redhat dot com @ 2004-10-18 18:31 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From law at redhat dot com 2004-10-18 18:31 -------
Subject: Re: Missed jump threading
optimization
On Mon, 2004-10-18 at 11:30, steven at gcc dot gnu dot org wrote:
> ------- Additional Comments From steven at gcc dot gnu dot org 2004-10-18 17:30 -------
> Diego told me to bug Law. Obedient as I always am, I hereby
> do so :-)
>
> Jeff, this is a missed jump threading opportunity, the default
> case can be threaded here. Any ideas how to fix this?
I don't see a good way to fix this. There's lots of interconnected
issues that would need to be addressed.
Clearly we need better range information so that we can determine
that i != 0 on the default case leaving the first switch statement
(or we would need to avoid collapsing empty cases to the default
label until expansion).
Second, we need to rewrite the jump threading selection code; that's
on the queue. Specifically we need to drop the requirement that
the statements at the start of the intermediate block are nops.
The SSA update code is already prepared to handle this change, so
it really ought to be isolated in the jump threading selection
code.
Given those two improvements we'd have a chance of threading the
default case out of the first switch statement.
jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
` (3 preceding siblings ...)
2004-10-18 18:31 ` law at redhat dot com
@ 2004-10-18 22:50 ` stevenb at suse dot de
2004-10-19 20:16 ` law at redhat dot com
2005-04-23 16:58 ` steven at gcc dot gnu dot org
6 siblings, 0 replies; 8+ messages in thread
From: stevenb at suse dot de @ 2004-10-18 22:50 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From stevenb at suse dot de 2004-10-18 22:50 -------
Subject: Re: Missed jump threading optimization
Hmm, threading the default case sounds interesting, but the real
reason why the RTL threader catches this and the tree threader does
not is because on RTL the test case basically looks like this:
extern void foo (void);
extern int i;
void
bar (void)
{
if (i == 0)
foo ();
if (i == 0)
foo ();
}
Hey, I can thread that! :-)
So perhaps we should consider lowering SWITCH_EXPRs with only two
targets to COND_EXPRs after all...? That would be quite easy to
do.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
` (4 preceding siblings ...)
2004-10-18 22:50 ` stevenb at suse dot de
@ 2004-10-19 20:16 ` law at redhat dot com
2005-04-23 16:58 ` steven at gcc dot gnu dot org
6 siblings, 0 replies; 8+ messages in thread
From: law at redhat dot com @ 2004-10-19 20:16 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From law at redhat dot com 2004-10-19 20:16 -------
Subject: Re: Missed jump threading
optimization
On Mon, 2004-10-18 at 16:50, stevenb at suse dot de wrote:
> ------- Additional Comments From stevenb at suse dot de 2004-10-18 22:50 -------
> Subject: Re: Missed jump threading optimization
>
> Hmm, threading the default case sounds interesting, but the real
> reason why the RTL threader catches this and the tree threader does
> not is because on RTL the test case basically looks like this:
>
> extern void foo (void);
> extern int i;
> void
> bar (void)
> {
> if (i == 0)
> foo ();
>
> if (i == 0)
> foo ();
> }
>
> Hey, I can thread that! :-)
>
> So perhaps we should consider lowering SWITCH_EXPRs with only two
> targets to COND_EXPRs after all...? That would be quite easy to
> do.
Jan and maybe others have talked about lowering SWITCH_EXPRs
earlier. I don't recall if it ever got implemented.
jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
* [Bug tree-optimization/18046] Missed jump threading optimization
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
` (5 preceding siblings ...)
2004-10-19 20:16 ` law at redhat dot com
@ 2005-04-23 16:58 ` steven at gcc dot gnu dot org
6 siblings, 0 replies; 8+ messages in thread
From: steven at gcc dot gnu dot org @ 2005-04-23 16:58 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2005-04-23 16:57 -------
I'm going to implement lowering of some SWITCH_EXPRs at the tree level. At
least the ones that we do not produce a decision tree for now in stmt.c...
--
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |steven at gcc dot gnu dot
|dot org |org
Status|NEW |ASSIGNED
Last reconfirmed|2004-10-18 12:52:47 |2005-04-23 16:57:45
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18046
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2005-04-23 16:58 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-10-18 12:16 [Bug tree-optimization/18046] New: Missed jump threading optimization steven at gcc dot gnu dot org
2004-10-18 12:52 ` [Bug tree-optimization/18046] " pinskia at gcc dot gnu dot org
2004-10-18 13:22 ` steven at gcc dot gnu dot org
2004-10-18 17:30 ` steven at gcc dot gnu dot org
2004-10-18 18:31 ` law at redhat dot com
2004-10-18 22:50 ` stevenb at suse dot de
2004-10-19 20:16 ` law at redhat dot com
2005-04-23 16:58 ` steven at gcc dot gnu dot org
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).