jhallen@wpi.wpi.edu (Joseph H Allen) (11/13/89)
How much of an effect do gotos have on register and other optimization
techniques? In particular, do C optimizing compilers take a simple minded
view towards gotos or does data flow analysis actually follow goto paths?
The reason I ask is, I know some compilers (WATCOM C compiler on IBM PCs I
think is one) combine common endings:
if( )
{
XXX
YYY <-------+----- These don't get duplicated
return; |
} |
else |
{ |
ZZZ |
YYY <-------+
return;
}
But mine doesn't. So is it better to just let the code be duplicated or
is it o.k. to use gotos to prevent the duplication:
if( )
{
XXX
goto here;
}
else
{
ZZZ
here:
YYY
return;
}
(Please ignore the fact that for this example you can just move the 'YYY
return' outside the if construct. Assume that it is a more complicated case
where you just can't do that)
Joe
[Depends on the compiler; I've seen some that depend on loops in the source
code and punt if gotos change it at all, and I've seen others that turn
everything into low-level gotos in intermediate code and then rediscover the
control structure from that. Comments from actual compiler writers are
welcome. The last C compiler I wrote was the original PCC for the RT PC and
it avoided the problem by doing almost no optimization at all. The assembler
postpass did tail merging, but at the time we hadn't ported it. -John]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.preston@rice.edu (Preston Briggs) (11/14/89)
In article <1989Nov12.222530.14148@esegue.segue.boston.ma.us> you write: >How much of an effect do gotos have on register and other optimization >techniques? In particular, do C optimizing compilers take a simple minded >view towards gotos or does data flow analysis actually follow goto paths? > >The reason I ask is, I know some compilers (WATCOM C compiler on IBM PCs I >think is one) combine common endings: "tail merging" or "cross jumping" >But mine doesn't. So is it better to just let the code be duplicated or >is it o.k. to use gotos to prevent the duplication: Coloring register allocators don't have any special problem with goto's. Generally, global (within a procedure) optimizations require data flow analysis, and the point of the analysis is not to be confused by the flow graph. On the other hand, goto's can degrade the optimization. In your example, xxx yyy zzz zzz | | \ / ------------- | V converted into xxx yyy | | \ / ------------- | zzz | V lowers the effectiveness of value numbering and constant propagation on "zzz." Additionally, the register allocation may be slightly worse since the graph could have become more contrained. (If xxx and yyy define a register used in zzz, tail merging will force the register allocator to use the same register in both xxx and yyy. This doesn't sound too bad, but it's a loss and the losses accumulate.) Basically, I would avoid tail-merging in the source (and goto's in general). The only payoff is in code space and there's a speed penalty. In a compiler, I would only do it at the last second (after register allocation) if at all. Do any of the IBM PC-class C compilers do global optimizations? Global constant propagation? Graph coloring register allocation? Preston Briggs preston@titan.rice.edu [The Metaware compilers are reputed to do graph coloring, though it's a trick to make it work on something as asymmetrical as a 286. Also, I wonder if one can do useful graph coloring without infringing IBM's patents. -John] -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
bright@dataio.Data-IO.COM (Walter Bright) (11/19/89)
In article <1989Nov13.203034.1778@esegue.segue.boston.ma.us> Preston Briggs <preston@rice.edu> writes: >In article <1989Nov12.222530.14148@esegue.segue.boston.ma.us> you write: >>In particular, do C optimizing compilers take a simple minded >>view towards gotos or does data flow analysis actually follow goto paths? Zortech C's optimizer (which I wrote) converts *everything* into goto's, and then analyzes the flow graph to discover loops and such. >Do any of the IBM PC-class C compilers do global optimizations? Zortech does. >Global constant propagation? Zortech does. >Graph coloring register allocation? Zortech does. ZTC also does loop induction variables, copy propagation, common subexpressions, very busy expressions, dead variables, dead code, loop invariants, etc. [From bright@dataio.Data-IO.COM (Walter Bright)] -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.