Looks like I should have read more about Staapl before writing that email. I guess you do the equivalent of DCN by your peephole optimizations. The thing about Factor's compiler is, it does this in a more general way. You should look at Slava's past blog posts, or read the code, if you're interested in knowing more about it.
On Tue, Aug 25, 2009 at 12:49 PM, Daniel Ehrenberg<micro...@gmail.com> wrote: > Hey Tom, > > This is a good question. There's a lot of literature on peephole > optimization, and I've read very little of it. I bet it'd be relevant > here, though there are special complications for a stack language. > Peephole optimization has limits, since you can't do much with control > flow, and the linearization order of instructions has a big impact on > what optimizations can be done. But it's not totally outdated; GCC > uses a technique based on peephole optimization for its instruction > selection pass, even though they could have gone with a more general > tree/dag rewriting approach. It seems like a reasonable way to do > things for a simple compiler like yours. > > Well, here's a way to view a system like the one you're talking about > formally: consider your rewrite rules, and the program, and say all > the rewrite rules are optional and can be applied in any order to any > part of the program at any time. Now you have a set (hopefully finite, > if your rewrite rules have a certain monotonicity property) of > programs which implement the original code, and which the rewrite > rules can give you. If the rewrite rules are monotonic, then there's > an easy procedure to optimize the program: list out all programs, > calculate their efficiency, and select one of the best ones. The task > now is to construct an efficient algorithm to find an optimal program, > by some metric. > > But I guess I'm not saying anything very helpful in that paragraph, > since I didn't give you the algorithm. It depends on the structure of > the rewrite rules. The phrase "rewrite rule" implies the most general > thing possible, and you can't make an algorithm on something so > general. With something like an optimizer, I don't understand why > things have to be confluent. Maybe the algorithm to find the optimal > series of peephole optimizations will be a confluent subset of the > general rewriting system of all valid peephole optimizations; is this > what you mean? If you have a confluent and always-terminating rewrite > system, it's really easy to do the rewriting, so that'd be a reason to > think about confluent rewriting systems, but they're not the only > thing you should consider. > > On the topic of optimizing stack-based code: Factor's compiler might > be the most advanced stack-based compiler ever constructed. It does > not use peephole optimizations. The stack checker and compiler > 'frontend' (high-level IR) form a stack code to stack code optimizer > which is much more powerful than a peephole optimizer, taking control > flow into account. The intermediate form is based on SSA, but at the > same time the stack is always present; SSA values refer to stack > locations. The most important pass is Sparse Conditional Constant > Propagation, which can be done on a stack-based, tree-structured IR > with no special difficulties. The last step, in the conversion to > low-level IR, ignores the SSA values and lets things be passed around > on the stack that was there the whole time. > > On register-based architectures (like the PIC18, right?), doing > everything with a stack is inherently inefficient because of peeks and > replaces on the top of the stack. A major goal of Factor's low-level > optimizer (arguably the main goal) is to eliminate redundant peeks and > replaces between subroutine calls, exposing a value structure that > other optimizations and the register allocator can use. It seems like > any advanced-enough compiler for a stack language should have some way > of eliminating redundant peeks and replaces, and Factor's > deconcatenatization algorithm is an elegant solution to this problem. > > Dan > > On Tue, Aug 25, 2009 at 1:21 AM, Tom Schouten<t...@zwizwa.be> wrote: >> Hello list, >> >> I guess this is mostly for Daniel, but anyone else of course feel free >> to chime in... >> >> I'm trying to get a better idea about rewriting systems for >> concatenative languages, particularly in the area of specification of >> peephole optimizations. It's been on my mind for a while, but I've >> always side-stepped any non-deterministic computations. I.e. in >> Staapl[1], the PIC18 code generator[2] is written using an eager >> pattern matching approach, essentiall re-interpreting already >> generated machine code as stack machine code that can then be >> partially evaluated together with the currently compiling primitive >> operation. (Explained here[3] in some detail). >> >> I've always been suspicious that this formulation, while it works well >> in practice and has a certain elegance, is a special case of a more >> general, non-confluent rewriting system. >> >> It seems to me that if there are any interesting optimizations to >> make, they are not going to be unique and depend on which path through >> the reduction rules is used to get to a particular irreducible >> expression. >> >> And then it stops. >> >> I have some intuition about reduction machines, as long as they >> compute a unique solution (lambda calculus w. strict eval (CEK >> machine) and lazy eval using graph reduction, ...) but I'm not sure >> how to view the other cases where you have a bunch of rewrite rules >> and you ask the compiler to pick a sequence of reduction rule >> applications that leads to the ``most optimal'' reduction under some >> kind of cost function (for PIC18 this would be the machine code >> length). >> >> I hope this makes some sense.. >> Any ideas on this welcome. >> >> Cheers, >> Tom >> >> [1] http://zwizwa.be/staapl >> [2] http://zwizwa.be/darcs/staapl/staapl/pic18/pic18-unit.ss >> [3] http://zwizwa.be/archive/staapl.html >> >> >> ------------------------------------------------------------------------------ >> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day >> trial. Simplify your report design, integration and deployment - and focus on >> what you do best, core application coding. Discover what's new with >> Crystal Reports now. http://p.sf.net/sfu/bobj-july >> _______________________________________________ >> Factor-talk mailing list >> Factor-talk@lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/factor-talk >> > ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
