Compilers - Estimating loop iterations

Author

Estimating loop iterations

drizzle

2005-05-07, 3:57 am

Hi all.
Can anyone point me to any literature on estimating number of times
a loop would iterate. I noticed gcc 4 can estimate based on access
functions, size of data used etc in the loop. Anybody know what paper
is it based on ?

thanks
[Where is the Fortran FREQUENCY statement now that we need it? -John]

glen herrmannsfeldt

2005-05-07, 8:58 pm

drizzle wrote:

> Can anyone point me to any literature on estimating number of times
> a loop would iterate. I noticed gcc 4 can estimate based on access
> functions, size of data used etc in the loop. Anybody know what paper
> is it based on ?

> [Where is the Fortran FREQUENCY statement now that we need it? -John]

I wondered about it a year or two ago. I saw it in the 704 Fortran
manual when I was looking for something else. It seems that it
didn't last very long. Since its use was optional, I am not sure
why it would go away. The compiler could always ignore it.

The C reg attribute is sometimes used as an indication that a
variable is used more than others, but compilers are allowed to
ignore that.

Other than FREQUENCY, it is interesting how many Fortran features
are pretty much unchanged since Fortran I.

-- glen
[I heard that FREQUENCY went away both because nobody used it and because
at least with 1960 optimizing technology, it didn't tell the compiler anything
useful. -John]

sandya

2005-05-07, 8:58 pm

http://www.mirror5.com/software/gcc...filedriven.html

has some references, especially the Larus and Wu paper.

"drizzle" <drizzle76@gmail.com> wrote in message
> Can anyone point me to any literature on estimating number of times
> a loop would iterate. I noticed gcc 4 can estimate based on access
> functions, size of data used etc in the loop. Anybody know what paper
> is it based on ?

Trevor Jenkins

2005-05-08, 8:57 pm

On 7 May 2005 16:58:29 -0400, John Levine commented:

> [I heard that FREQUENCY went away both because nobody used it and because
> at least with 1960 optimizing technology, it didn't tell the compiler anything
> useful. -John]

I heard that the reason it was taken away after the first few FORTRAN
compilers implemented it round the wrong way ... but it didn't affect the
quality of the code produced. Also programmers were found to be poor at
determining which execution paths are actually followed,

Regards, Trevor

<>< Re: deemed!
[Yes, that agrees with what I've heard. -John]

glen herrmannsfeldt

2005-05-09, 3:58 am

Trevor Jenkins wrote:
> On 7 May 2005 16:58:29 -0400, John Levine commented:

[color=darkred]
> I heard that the reason it was taken away after the first few FORTRAN
> compilers implemented it round the wrong way ... but it didn't affect the
> quality of the code produced. Also programmers were found to be poor at
> determining which execution paths are actually followed,

Well, FREQUENCY has two, somewhat unrelated uses. One was for
relative branch frequency. For processors that do static branch
prediction (and I don't believe the 704 was one) with instruction or
prefix bits, it could be used.

The other use is for DO loops where it specifies the expected number
of iterations. There might be some things optimizers could do
differently based on that number. That seems to be the use that the
OP was asking about.

-- glen
[The point of the branch prediction was for the Fortran three-way arithmetic
IF, to tell it which test to put first. Pretty marginal. -John]

Sponsored Links