Lesson 9: Interprocedural Analysis

Gist

Recap: we have done local (within a basic block) and global (within a function) analyses & optimizations. But what about optimizations that have to cross function boundaries? Those are interprocedural.

Like, what if we want to do LICM to this code?

main() {
    let x = ...;
    for (...) {
        g(f(x));
    }
}

f(x) {
    return x * 42;
}

The multiplication in f is clearly loop invariant, but no global optimization can tell that. And worse still, we can’t very well move the multiplication “out of” the body of f because there might be other places that call f that expect it to work as written.

The Call Graph

Open vs. Closed World

Inlining

Devirtualization

Context Sensitivity

Sometimes the answer to a question about a function depends on another question: which call are we talking about?

For example, imagine we are trying to optimize this somewhat funky program that uses lots of evil mutable global state:

bool b;  // global variables
int i = 0;

main() {
    g1();
    print(i):

    g2()
    print(i);
}

g1() {
    b = true;
    f();
}

g2() {
    b = false;
    f();
}

f() {
    if (b) {
        i++;
    }
}

The call to f in g1 matters, but the one in g2 is “dead code” that can’t affect anything the program will do. Inlining could reveal this fact, of course, but we know it’s not always practical to inline everything. And any self-respecting (i.e., sound) interprocedural analysis that asks does f modify i? must say yes, it might!

So is there a way to tell that the second f can be eliminated? For that, we need a context-sensitive analysis. The idea is to use some kind of contextual information to distinguish different invocations of the same code. For example, one common kind of context is the call stack: a context-sensitive analysis could draw different conclusions about calls to f from g1 versus calls to f from g2.

Context-sensitive analyses can get expensive quickly. For example, in our imaginary does the function modify i? analysis, a context-insensitive analysis would need to answer n queries where n is the number of functions in the program. But a context-sensitive analysis that uses the calling function as the context needs queries. And you can even use deeper call stacks as context to get even more precise answers—if you use the i most recent calls as context, you now need to answer nⁱ queries. So in general, context sensitivity represents a pretty steep trade-off between analysis precision and cost.

Tasks

There are no tasks to turn in for this lesson. For “fun,” you can consider implementing inlining for Bril function calls!