Inter Procedural Optimization

Submitted ByRohit GuptaS Praveenkumar

Topics

What is Inter Procedural Optimization and Why it is required
Call forwarding
Inter-procedural dead catch handler optimizations

Introduction : The code generated for a function or procedure in a dynamically typed language typically has to carry out various type and range checks on its arguments before it can operate on them. These runtime tests can incur a significant performance overhead. As a very simple example, consider the following function to compute the average of a list of numbers.

int Ave (L, Sum, Count) {

If null (!L) return ( Sum/Count);

else return (Ave (tail (L), Sum+head (L), Count+1));

}

The call forwarding problem

The code generated for a procedure consists of a set of entry actions, which can carried out in a number of different legal order, followed by the code for its body Each procedure has number of call sites, and at each call site there is some information about the actual parameters for calls issued from that site, specifying which entry actions must be executed and which may be skipped. to decide ordering and which instruction is t copied is a n.p complete problem.

Solution

The best solution to this problem is to impose a global bound on the total number of entry actions that may be copied across all the call sites occurring in a program, but this turns out to be complicated to implement because when performing call forwarding on any particular procedure, we have to keep track of the number of entry actions copied for all the procedures in the program, including those that have not yet been processed by the optimizer. A simple and effective approximation to his approach is to assign, for each procedure, a bout non the number of entry actions that can be copied to each call site for that procedure. If we start with a global bound on the total number of entry actions that can be copied, such per-procedure bounds can be obtained by “dividing up” the global bound among the procedures

Greedy algorithm

the problem of computing optimal solutions for arbitrary call forwarding problems is NP-complete in general, a greedy algorithm appears to work quite well in practice. Given a call forwarding problem for a procedure with a bound of k on the number of actions that can be copied from the callee to the call sites, the general idea is to pick actions one at a time, at each step choosing an actions that minimizes the cost to be paid at that step The algorithm maintains a list of call sites that do not need to execute more than k of the actions chosen up to that point.

Inter Procedural Optimization – – The call forwarding problem

sbpraveen34

Inter Procedural Optimization – – The call forwarding problem

0 0

Compiler-Design-HTML5-Presentation