Re: reducible loops

preston@dawn.cs.rice.edu (Preston Briggs)
Tue, 10 Mar 1992 18:38:39 GMT

          From comp.compilers

Related articles
[2 earlier articles]
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-26)
Re: reducible loops lee@dumas.rutgers.edu (1992-02-26)
Re: reducible loops glew@pdx007.intel.com (1992-02-26)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-27)
Re: reducible loops joel@decwrl.dec.com (1992-02-28)
Re: reducible loops idacrd!desj@uunet.UU.NET (1992-03-09)
Re: reducible loops preston@dawn.cs.rice.edu (1992-03-10)
| List of all articles for this month |

Newsgroups: comp.compilers
From: preston@dawn.cs.rice.edu (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-03-033
Date: Tue, 10 Mar 1992 18:38:39 GMT

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
--


Post a followup to this message

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