Re: Detecting Unrolled loops

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?


4 years ago Zhaofang Wen implemented generalized rerolling of
partially and completely unrolled loops as a part of a research
project we were doing.


Given the level of effort it took to get the generality we wanted, I
strongly doubt that a syntax based approach would be useful for real
code. The implementation is 17 pages of code, plus 4 pages of header
files for the special data structures. It was done in the middle of
the loop transformation module of the Convex Application Compiler,
which was an interprocedural compiler for Fortran and C. The
implementation would have been much larger without all the
infrastructure already provided by that system. Induction value
analysis in particular was essential to get it right. The actual
transformation was done before dependency analysis, loop interchange,
and loop distribution. We considered doing it after DA, but the costs
outweighed the benefits.


We collected or wrote some 120+ test cases -- the problem is not as
simple as it seems on the surface.


We were unable to find any decent references on rerolling
implementations -- I'd be happy to receive any.


There is a page in our (forthcoming) book that describes what
rerolling is, though not how we did it. (Loop rerolling was just a
side-show to enable our real objectives.)


For those who want a reference,
Automatic Algorithm Recognition and Replacement:
A New Approach to Program Optimization
Robert Metzger and Zhaofang Wen
MIT Press, forthcoming
see page 58, section 4.5.1

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