Re: Compiler loop optimizations

"Amit Gupta" <emailamit@gmail.com>
31 Dec 2006 09:25:37 -0500

          From comp.compilers

Related articles
Compiler loop optimizations linuxkaffee@gmx.net (Christian Sturz) (2006-12-29)
Re: Compiler loop optimizations emailamit@gmail.com (Amit Gupta) (2006-12-31)
Re: Compiler loop optimizations robert.hundt@gmail.com (Robert H) (2007-01-01)
Re: Compiler loop optimizations robert.hundt@gmail.com (Robert H) (2007-01-01)
Re: Compiler loop optimizations torbenm@app-0.diku.dk (2007-01-05)
Re: Compiler loop optimizations linuxkaffee@gmx.net (Christian Sturz) (2007-01-05)
Re: Compiler loop optimizations emailamit@gmail.com (Amit Gupta) (2007-01-07)
Compiler loop optimizations Heiko.Falk@udo.edu (Heiko Falk) (2007-01-10)
[2 later articles]
| List of all articles for this month |

From: "Amit Gupta" <emailamit@gmail.com>
Newsgroups: comp.compilers
Date: 31 Dec 2006 09:25:37 -0500
Organization: Compilers Central
References: 06-12-109
Keywords: optimize, architecture
Posted-Date: 31 Dec 2006 09:25:37 EST

The problem here is unreachable-code elimination based on data-flow
analysis. An optimizing compiler should be able to do so. Note that,
reachability analysis is np-hard, so no compiler will tackle all such
problems, however cases like this and even more complicated ones can be
handled by good compilers. Another example would be "if(x == 5) Y = 7 +
x". You dont need to do this computation. Note that, in logic synthesis
compilers, we sometime call it either partial constant propagation or
don't care words optimization.


NOW, you don't really need to worry if gcc/CC can optimize this
particular program. The processor branch prediction unit will be able
to take care of it.


How...?


In "foo10", when (i==15) is not true for first time, the prediction
unit will speculate the condition is false in following iterations as
well. The only time spent is on checking (i==15) at first iteration
(minimal).


Similarily, for f100, (i==15) will result in only two stall(before and
after) when branch prediction unit goes wrong. Over 100 iterations
though, the execution time spent is minimal (also depends if Block1
changes variables used in the loop).


You should be able to verify this, by running foo10/100 over million
iterations.


At any rate, for the specified program, a compiler optimization would
not result into any endcase significant improvement.


HTH
Amit Gupta


Christian Sturz wrote:
> Hi,
>
> I was curious if there are any gcc compiler optimizations that can improve
> this code:
>


> 1) For the function foo10:
> The if-block following "if( i == 15 )" will be never executed since 'i'
> will never become 15 here. So, this entire block could be removed without


>
> 2) For the function foo100:
> This code is not optimal as well. The if-condition is just once met but
> has to be evaluated for all of the 100 loop iterations. An idea I had in
> mind was to split the loop in two parts: for ( int i = 0; i <= 15; ++i )
> {...} BLOCK2


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.