Re: reducible loops

idacrd!desj@uunet.UU.NET (David desJardins) writes:


>My impression is that you can turn any code into a collection
>of loops.


Certainly can't find loops if no cycles exist!


>The problem is that if you get the wrong loops your code will
>really stink.


Loops are loops; can't find "the wrong ones". However, we can find the
wrong nesting relationship, where "wrong" means some particular invocation
executes the "outer loop" more times than the "inner loop".


This happens. A solution is to use profiling information.


>The job of the compiler is supposed to be a practical one of
>generating code which runs fast rather than an academic one of
>identifying a particular kind of subgraph.


It is not an academic problem, but a practical problem. The fact that
it's expressed in graph-theoretic terms is because graph theory offers
some helpful tools and notation.


>If your compiler makes decisions like the one you are talking about
>before looking at what the code is doing, then you have no chance to
>get it right.


Finding loops and other control-flow analysis _is_ "looking at the code to
see how it works".


When I write these postings, I sometimes talk about my limited personal
experience. Mostly though, I try and talk about the way real optimizing
compilers work, usually based on what's commonly available in the
literature (in other words, things you could look up yourself). Sometimes
I'm wrong and this usually provokes corrections from people who know
better. Thus, we all learn a little.


In this case, I'm telling you how real compilers work.


Preston Briggs
--

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