On 2011-05-06, at 4:36 PM, chevalma@iro.umontreal.ca wrote:
The code patching mechanism I proposed is fairly simple to implement and will be directly useful for my research, which I need to get started soon. Let's not rule out implementing something like that in the near term.
I'm 100% sure we can implement something specialized just for global function calls and get performance gains with a tightly coupled approach, but that won't teach us all that much.
Among the important things it will teach us is the best performance we can gain with code patching. That's because, at the back-end level, code patching is unconstrained (in the same sense that the execution time of a compiled high-level language can be no better than the best assembly language coding). I can see a software engineering advantage to express the code patching at the IR level (if it is possible in a simple way), but I also see a performance advantage to do the code patching in the back-end.
Specifically, for calling global functions, the back-end code patching approach can be compared to the "toggleable unconditional branch" approach you suggest to see how the performance compares. That's a really important thing to determine.
Being able to not only optimize global calls, but easily inline global functions with little extra effort, on the other hand, now that's interesting.
In the project we need to better understand how code patching can be used to improve performance. Both approaches have pros and cons. We need to experiment to gain experience and ultimately make the best decision. That is a sound scientific and engineering approach.
What I propose is as follows:
- Implement the toggleable unconditional branch (TUB?)
- Perhaps ~1-2 weeks of work? Most of the work here is in the backend, but
could be split among myself, Erick and others. 2. Implement global function call optimization using TUBs
- ~1 week of work, should be very easy
- Implement global function inlining heuristics
- 1-2 days of effort, inlining mechanisms are already implemented
For your point 2, have you considered how TUB would be used to optimize calling global functions? I think you are overlooking things. Before starting an implementation of TUB, some design and back-of-the envelope analysis or prototyping is needed to know if TUB is appropriate to optimize calling global functions. Some questions that come to mind:
The IR needs a new instruction of the form:
change_TUB( the_tub, the_new_destination )
1) How can the TUB be identified? A first-class pointer to a label? A global name? How does the IR reference a TUB identifier?
2) How can the new destination of the TUB be identified? A first-class pointer to a label/function? A global name?
3) Who is the code patcher (in other words which part of the system is doing the code patching)? How is the relevant code patching information passed to the code patcher?
4) What is the IR for a global function call? It seems that IR pseudo-code would be something like:
the_tub_label: tub_branch unoptimized_label unoptimized_label: fn = getprop( globalobj, "f" ) call fn, nbargs=2, arg1, arg2
Where should the tub_branch be redirected if the global property "f" is known to be bound to a function whose code is at address F? You can't just do change_TUB(the_tub_label, F) because that would no longer do the parameter setup, the stack adjustment, the argument count setup, etc So it has to be redirected to:
optimized_label: call F, nbargs=2, arg1, arg2
One concern is the code bloat due to the duplication of calls. Also, there are two branches (the TUB and the call) in the optimized and unoptimized versions, so there will be a runtime performance loss due to the superfluous branch (branches are important to avoid in code because it slows down the CPU pipeline). With aggressive code patching there will be many TUBs in the code, so many superfluous branches. Also, how can we use TUBs to optimize calls in the case where the number of arguments of the call site matches the number of parameters of the callee (to avoid setup of the argument count parameter and the check of the argument count in the callee)?
5) What is the mechanism for keeping track of the TUBs that have been changed, so that they can be reverted to their original destination when the optimization is no longer valid? Typically a list of TUBs dependent on a certain property needs to be maintained. How is this allocated and maintained? What is the space usage?
As I said in my previous message, we will start with an implementation of the code patching for global function calls in the back-end, allowing us to greatly improve the performance at a low implementation cost. After milestone 2 we can look at code patching at the IR level.
Marc