2008-01-14
by earl, 6155 days ago
Knoop, Rüthing, and Steffen (1994) Optimal Code Motion: Theory and Practice (CiteSeer) -- not only because this kept me busy for quite a few days in the past: code motion is a program transformation aimed at improving code efficiency by suppressing redundant (re-)computations of an expression. Knoop et. al. pioneered a technique called "lazy code motion" (LCM) which is not only computationally optimal (a given expression is computed as few times as possible) but also "lifetime-optimal", i.e. it minimzes register pressure resulting from the temporary variables used to store a redundantly calculated expression in. The paper describes the LCM transformation, it's relation to other possible CM transformations and proves LCM to be correct (expressions are replaced by variables that are initialized with the proper value) and safe (no new computations are introduced on a program path).It's for sure a tough read even if you are familiar with basic ideas of optimizing compilers (e.g. bitvector frameworks) and some may find the seminal paper introducing LCM (Knoop, et. al. (1992), Lazy Code Motion; CiteSeer) more accessible. I personally find code motion to be very interesting for several reasons: first of all, this particular algorithm (LCM), is in wide use and solves a practical problem. Generally, code motion combines a whole series of analysises/optimizations and uses surprisingly simple and elegant concepts which when put together result in a fairly challenging whole with lots of interesting problems to think about.
I also think, the presentation given by Knoop et. al. would be very suited to an educational implementation using Datalog or something similar. It would be very nice to really "see" all those predicates attached to program nodes -- is anybody aware if someone should has done something like that already?
search
37 active users
- unknown (37)
backlinks (more)
none, yet
recent stores (more)
recent comments
echo earlZstrainYat|tr ZY @.
