Well, I have a deeply nested tree of let blocks intermixed with lambda abstractions (my front-end, which uses a continuation passing style, generates very inefficient code). If I alternate between beta-reductions and inlining, then I need to do many passes to end up with something small and sensible (and this takes a lot of time). So, I guess I have to do both types of steps in a single depth-first pass. I'm about to rewrite my optimizer this way, so I thought perhaps I'd better read up on it first to prevent unnecessary work :)
Yes, checking what to inline is tricky, but I'm not there yet; my code is still very simple and everything can be inlined in principle (unless of course intermediate results would cause problems, which I'm not sure about).
Ok, I think I see the problem.
What about traversing down to as deep as possible, then walking up the AST inlining as you go? This should allow processing in a linear time in the number of nodes, with a single pass.
Hey, thanks for the reply. I'm already doing something like that. The problem is that I also have to do the beta-reductions (i.e. reduction of function applications), and I'm not sure what order is best.
* Replace function application (function call) expression with body of inlined function
* Now replace all variables in the target function body with the argument values from the func expr
* Re-bind all variables.
(Some details elided :) )
The trickiest aspect of inlining is deciding what to inline.