Homework 4

Due Feb 20th, 1998

1. One of the major components of automatic inlining is the policy which decides when to inline. In class we discussed many metrics that can help decide when to inline a call (from procedure g into procedure f) such as the size of g or the number of callers of g or the frequency of the call f->g or the number and type of optimizations enabled by the inlining. Write an algorithm that decides when to inline. Your algorithm should also take into account the optimizations that are potentially enabled by the inlining (you need not consider any optimizations that we haven't yet covered in the course). More specifically, describe one or more analyses (may or may not be data-flow analyses) that efficiently try to determine whether or not inlining will enable optimizations. Assume that inlining is expensive in compile time and that you must only attempt to inline those calls where there is reasonable expectation for a high payoff.

2. Inlining a call (from procedure f to g) changes the body of f. How does this change the data-flow information in f? Give concrete examples using an analysis of your choice.

3. Loop unrolling replaces the body of a loop by several copies of the body and adjusts the loop-control code accordingly. For example,
for i := 1 to 100 do
t := t + Inv
s := s + t + a[i]

becomes (after unrolling it once)
for i := 1 by 2 to 99 do
     t := t + Inv
     s := s + t + a[i]
     t := t + Inv
     s := s + t + a[i+1]

Assume that Inv is loop invariant. Convert the original and the unrolled loop into a low-level representation that makes the operations involved in array references explicit. List the induction variables (basic and dependent) in the original and unrolled code (you may split variables if needed). Perform strength reduction and linear-function test replacement on the original and unrolled code.