[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From kazu at cs dot umass dot edu 2005-01-23 20:39
---
IMHO, we need to call rewrite_ssa_into_ssa after fixing CFG.
Consider:
int c, d;
int
bar (int a)
{
void *p;
int b;
if (a!=0)
{
b = 3;
p = &&L0;
}
else
{
b = 5;
p = &&L1;
}
goto *p;
L0:
c = b;
return 1;
L1:
d = b;
return 0;
}
Here is the corresponding SSA form.
:
if (a_4 != 0) goto ; else goto ;
:;
# p_2 = PHI <&L0(0), &L1(1)>;
# b_1 = PHI <3(0), 5(1)>;
:;
goto p_2;
L0:;
c = b_1;
goto ();
L1:;
d = b_1;
# D.1130_3 = PHI <1(3), 0(4)>;
:;
return D.1130_3;
Then the problem becomes pretty much the same as jump threading.
Note that has two incoming edges, one from and the other from
. We are basically trying to thread each incoming edge through .
Then we need to duplicate PHI nodes at and rewrite b_1 into SSA.
CCing Jeff as I think this PR fits very naturally to the jump threading
algogorithm in DOM.
--
What|Removed |Added
CC||law at redhat dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From steven at gcc dot gnu dot org 2005-01-23 20:59 --- This is one of those things that jump bypassing does catch, but tree CCP doesn't. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From kazu at cs dot umass dot edu 2005-01-23 21:09
---
Here is another idea that would not compilicate the DOM.
That is, we can set up things so that the actual threading part will be
done by DOM.
Suppose we have a factored computed goto block like so:
# p_2 = PHI <&L0(0), &L1(1), p_3(2)>;
# b_1 = PHI <3(0), 5(1), 4(2)>;
:;
... possibly some other statements ...
goto p_2;
Let's split this block like so:
# p_2 = PHI <&L0(0), &L1(1), p_3(2)>;
# b_1 = PHI <3(0), 5(1), 4(2)>;
:;
... possibly some other statements ...
:; // fall through from L2.
goto p_2;
Note that we are still in SSA form without need for rewriting.
Now let's add a new PHI node and a new SWITCH_EXPR to like so:
# p_2 = PHI <&L0(0), &L1(1), p_3(2)>;
# b_1 = PHI <3(0), 5(1), 4(2)>;
# fac_1 = PHI <0(0), 1(1), 2(2)>;
:;
... possibly some other statements ...
switch (fac_1)
{
case 0: goto L0;<- a threadable, normal edge
case 1: goto L1;<- a threadable, normal edge
default: goto ; <- not threadable because p_3 is an SSA_NAME
}
:;
goto p_2;
That is, we create a new PHI node fac_1 so that we can build a
dispatch table using a SWITCH_EXPR.
Now it's easy for DOM to pick up the jump threading opportunities at
SWITCH_EXPR.
If you like, you can say that we "reduce" the factored computed goto
block to a SWITCH_EXPR.
Any thoughts?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From law at redhat dot com 2005-01-24 20:46 ---
Subject: Re: computed gotos are not folded
back to regular gotos when it is found that they are not computed gotos
at
all
On Sun, 2005-01-23 at 21:09 +, kazu at cs dot umass dot edu wrote:
> --- Additional Comments From kazu at cs dot umass dot edu 2005-01-23
> 21:09 ---
> Here is another idea that would not compilicate the DOM.
> That is, we can set up things so that the actual threading part will be
> done by DOM.
>
> Suppose we have a factored computed goto block like so:
>
> # p_2 = PHI <&L0(0), &L1(1), p_3(2)>;
> # b_1 = PHI <3(0), 5(1), 4(2)>;
> :;
> ... possibly some other statements ...
> goto p_2;
>
>
> Let's split this block like so:
>
>
> # p_2 = PHI <&L0(0), &L1(1), p_3(2)>;
> # b_1 = PHI <3(0), 5(1), 4(2)>;
> :;
> ... possibly some other statements ...
>
> :; // fall through from L2.
> goto p_2;
>
>
> Note that we are still in SSA form without need for rewriting.
>
> Now let's add a new PHI node and a new SWITCH_EXPR to like so:
>
>
> # p_2 = PHI <&L0(0), &L1(1), p_3(2)>;
> # b_1 = PHI <3(0), 5(1), 4(2)>;
> # fac_1 = PHI <0(0), 1(1), 2(2)>;
> :;
> ... possibly some other statements ...
> switch (fac_1)
> {
> case 0: goto L0;<- a threadable, normal edge
> case 1: goto L1;<- a threadable, normal edge
> default: goto ; <- not threadable because p_3 is an SSA_NAME
> }
>
> :;
> goto p_2;
>
> That is, we create a new PHI node fac_1 so that we can build a
> dispatch table using a SWITCH_EXPR.
>
> Now it's easy for DOM to pick up the jump threading opportunities at
> SWITCH_EXPR.
>
> If you like, you can say that we "reduce" the factored computed goto
> block to a SWITCH_EXPR.
>
> Any thoughts?
Interesting approach. I'm not sure if your approach is easier
than just expanding the threading code to handle threading indirect
jumps.
I don't initially *think* that extending the threading code would be
all that difficult. In fact, all I think we need to do is update
the selection code to detect this case -- I think the code to update
the CFG and SSA graphs will DTRT without any changes.
Jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From kazu at cs dot umass dot edu 2005-01-24 20:56 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all Hi Jeff, > Interesting approach. I'm not sure if your approach is easier > than just expanding the threading code to handle threading indirect > jumps. > > I don't initially *think* that extending the threading code would be > all that difficult. In fact, all I think we need to do is update > the selection code to detect this case -- I think the code to update > the CFG and SSA graphs will DTRT without any changes. Some people do not want to see DOM getting bigger and bigger, so I just wanted to point out that there is an approach without making DOM any bigger, but then you're right. I don't think extending the jump threader is all that difficult or dirty, either. Either approach works for me. Kazu Hirata -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From stevenb at suse dot de 2005-01-24 20:59 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all > Some people do not want to see DOM getting bigger and bigger, That includes me, but ... > I don't think extending the jump > threader is all that difficult or dirty, either. ...which is a very strong argument for just making DOM handle this. My understanding is thatin the end DOM will mostly be just a threader, and threading through computed jumps is part of that. That the existing threader can already handle this is bonus. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From law at redhat dot com 2005-01-24 21:08 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all On Mon, 2005-01-24 at 20:56 +, kazu at cs dot umass dot edu wrote: > --- Additional Comments From kazu at cs dot umass dot edu 2005-01-24 > 20:56 --- > Subject: Re: computed gotos are not folded > back to regular gotos when it is found that they are not computed gotos at > all > > Hi Jeff, > > > Interesting approach. I'm not sure if your approach is easier > > than just expanding the threading code to handle threading indirect > > jumps. > > > > I don't initially *think* that extending the threading code would be > > all that difficult. In fact, all I think we need to do is update > > the selection code to detect this case -- I think the code to update > > the CFG and SSA graphs will DTRT without any changes. > > Some people do not want to see DOM getting bigger and bigger, so I > just wanted to point out that there is an approach without making DOM > any bigger, but then you're right. I don't think extending the jump > threader is all that difficult or dirty, either. Either approach > works for me. Understood. What I expect long term is DOM will degenerate into just a context sensitive optimizer. The bulk of its copy propagation and expression elimination will ultimately be subsumed by other, better optimization passes. Extending DOM to handle this case would fit into that long term goal since we'd be extending the part of DOM which is not likely to be subsumed by better optimizers. jeff -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From law at redhat dot com 2005-01-24 21:37 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all On Mon, 2005-01-24 at 20:59 +, stevenb at suse dot de wrote: > --- Additional Comments From stevenb at suse dot de 2005-01-24 20:59 > --- > Subject: Re: computed gotos are not folded back to regular gotos when it is > found that they are not computed gotos at all > > > Some people do not want to see DOM getting bigger and bigger, > > That includes me, but ... > > > I don't think extending the jump > > threader is all that difficult or dirty, either. > > ...which is a very strong argument for just making DOM handle this. > > My understanding is thatin the end DOM will mostly be just a threader, > and threading through computed jumps is part of that. That the existing > threader can already handle this is bonus. Out of curiosity, does this case actually happen very often? Maybe in Fortran code perhaps? jeff -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From pinskia at physics dot uc dot edu 2005-01-24 21:47 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all On Jan 24, 2005, at 4:37 PM, law at redhat dot com wrote: > Out of curiosity, does this case actually happen very often? Maybe > in Fortran code perhaps? Actually I don't think this happens very much but it could happen a lot with generated code from Scheme code (which gets converted to c). -- Pinski -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From stevenb at suse dot de 2005-01-24 21:50 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all On Monday 24 January 2005 22:37, law at redhat dot com wrote: > Out of curiosity, does this case actually happen very often? Maybe > in Fortran code perhaps? It can happen a lot in interpreter code, though probably not *that* often. The most important reason why I would like to see this handled at the tree level is because jump bypassing in gcse.c can do it, see http://gcc.gnu.org/ml/gcc-patches/2003-02/msg00647.html -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From law at redhat dot com 2005-01-24 21:59 --- Subject: Re: computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all On Mon, 2005-01-24 at 21:50 +, stevenb at suse dot de wrote: > It can happen a lot in interpreter code, though probably not *that* > often. The most important reason why I would like to see this handled > at the tree level is because jump bypassing in gcse.c can do it, see > http://gcc.gnu.org/ml/gcc-patches/2003-02/msg00647.html OK. Thanks, Jeff -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From law at redhat dot com 2005-03-08 03:44 --- I just checked in a patch which should fix this problem. -- What|Removed |Added OtherBugsDependingO||17652 nThis|| http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From pinskia at gcc dot gnu dot org 2005-03-08 03:47 --- Fixed. -- What|Removed |Added Status|NEW |RESOLVED Resolution||FIXED http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
[Bug tree-optimization/18133] computed gotos are not folded back to regular gotos when it is found that they are not computed gotos at all
--- Additional Comments From pinskia at gcc dot gnu dot org 2005-03-08 03:47 --- Fixed. -- What|Removed |Added Target Milestone|--- |4.1.0 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18133
