Re: Detecting Unrolled loops

"Quinn Tyler Jackson" <qjackson@wave.home.com>
10 Jul 1999 01:14:36 -0400

          From comp.compilers

Related articles
Detecting Unrolled loops mikesw@whiterose.net (1999-07-06)
Re: Detecting Unrolled loops qjackson@wave.home.com (Quinn Tyler Jackson) (1999-07-10)
Re: Detecting Unrolled loops metzger@rsn.hp.com (Robert Metzger) (1999-07-14)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <qjackson@wave.home.com>
Newsgroups: comp.compilers
Date: 10 Jul 1999 01:14:36 -0400
Organization: Compilers Central
References: 99-07-025
Keywords: analysis, optimize

M Sweger <mikesw@whiterose.net> wrote in message
> I'm wondering if during the course of parsing a program that has
> code repeated multiple times (unrolled) instead of once using a For
> loop whether compiler techniques can detect/find them and reduce them
> down to a loop and mark in the tree structure that this is a loop.
[...]
> What compiler technique would be able to do this?


Just one perspective on this, since I happen to be knee deep in
research on something that allows what you're asking about... It's
probably overkill for what you need.


Once the source has been parsed and an AST constructed, the AST itself
becomes a candidate for a metaparse that can detect such things as
immediately repeated sequences (manually unrolled loops). The key to
doing it this way is to write a tree pattern matcher that is
expressive enough to allow you to specify abstractly the notion a{2+},
where "a" is any block of code whatsoever.


As part of the next phase of PAISLEI, I will be adding this ability to
"parse-the-parse" directly into the reduction specification language,
so that metaevents will be generated when these higher-level patterns
surface as a result of AST construction. I would hope that, once I've
nailed down the notational formalism (which I'm calling the meta-S
Calculus), it would be possible to write a standard grammar on the one
side that parses blocks, and a metagrammar on the m-S side that
produces events when such things as unrolled loops are unencountered.
Events and meta-events would be interleaved. The tricky part has been
nailing down the notation for communication between the standard and
the meta grammars, as well as an efficient k-level interleaved channel
communication protocol. (The lazy Lambda and Process Calculi are
somewhat opaque to me, and from what I can tell, the lazy-L and P
Calculi are time complex....)
--
Quinn Tyler Jackson
http://www.qtj.net/~quinn/


Post a followup to this message

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