Implementing inline expansion

Question

Hello,
I am curious to know how to implement inline expansion.
I am writing my own compiler just for fun and education. I learn a lot by example so if someone can provide me an algorithm that does inlining that can help.
I prefer in C++ but the language doesn't matter.
The target language that I'm trying to write inlining for is javascript.

EDIT: Just to clarify, I am looking for ways to imrpove ShrinkSafe.
GWT inlines javascript functions so it is possible. GWT does inlining before the code is run.

Answer 1

A common implementation is to do it in the optimization phase, as a rewrite rule. You replace the actual function call instruction by the called instructions (minus the return statement, naturally).

Next, you make sure that the peephole optimizer can eliminate the stack setup which preceded the call instruction and the callee's prologue which is now inlined. Similarly, you should make sure that the peephole optimizer can optimize the callees epilogue and the callers processing of the return value.

The biggest benefits of this are that it makes the instruction sequence contiguous in memory and the peephole optimizer typically saves you a bunch of stack push/pops.

Answer 2

In-lining is done after the code has been parsed into a tree.

for(int loop=1;loop <= 10;++loop)
{
    f(loop);
}

for-|
    --- (Init Code)---Assign--|
    |                         --- loop
    |                         |
    |                         --- 1
    --- (Condition)--- <= |
    |                     --- loop
    |                     |
    |                     --- 10
    --- (Post) --- ++ |
    |                 --- loop
    |
    --- (Body) Call |
                    --- (Function Name) f
                    |
                    --- (Parameter List)---Node1 -- loop
                                             |
                                           NULL

You will also have a parse tree for the function f.
To inline the function you need to create a duplicate of the tree for the fucntion f. Then parse through the tree a replace all references to the parameter used in the function call with the variable (loop in this case). Once this is done. replace the 'Call' node in the above tree with the new tree you just created.