Reducible loop, was Re: How Smart Can We Afford to be?

In article 92-02-106 idacrd!desj@uunet.uu.net (David desJardins) writes:
>What I thought you were going to produce, and the only case which it seems
>to me should be hard, is code in which multiple cycles are intertwined
>with one another. In this case it may indeed be hard to find the "real
>loop." For example:


> ...
>110 continue
> statement A
>120 continue
> statement B
> if (condition a) then
> statement C
> goto 110
> endif
> statement D
> if (condition b) then
> statement E
> goto 120
> endif


>Now there are two cycles, (ABC) and (BDE), intertwined, and optimizing
>both simultaneously seems a hard problem.


It might not be the loops that you intended, but what you wrote is
reducible and easy to analyze. What you've got is one loop, nested
within another, written oddly.


  |
  v <-------+
  A |
  v <-----+ |
  B -> D | |
  v v | |
  C E -+ |
  | |
  +---------+


People don't always have good intuition about what is hard and what isn't.
Of course, your code may not have the execution profile that one might
expect of a nested loop, but that's a separate problem.


Your example is not necessarily hard to deal with, either. As long as you
write clearly, if the optimization "really matters" there's a good chance
that attention will have been paid to it. By the way, on some machines
the best code sequence to use depends heavily on context (superscalar
machines sometimes benefit from something I'll call "proper carburetion"
*), so the best recourse is to write clearly, use common idioms, and pay
your compiler writers well (so says the compiler writer). The best way to
get good performance is to persuade SPEC to use a benchmark that is
chock-full of your favorite idioms in time-critical inner loops (Herman,
are you listening? This is how to get what you want.)


(*) As an example, if you wanted to get the highest possible Useless
Instructions Per Second rating for 1000 instructions on an RS/6000, what
1000 instructions would you choose? I'll bet that 1000 NOPS is not the
correct answer.


David Chase
Sun


--

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