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
