When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis

Question

I've been exploring the differences between Context Sensitive Analysis (CSA) and Context Insensitive Analysis (CIA), members of inter-procedural static analysis. The problem I'm coming up against is when to use one over the other.

Namely, suppose the following context:

The input program is in Static Single Assignment form. We have a machine that has no memory hierarchy. All it can do is store things in registers. We want host languages to support functions, including non-tail recursion. Which is to imply, when we call a function, we need to save all variables live across the function into registers and then calculate space requirements to see if we have enough registers to execution the function.

To do so, we need to use both CIA and CSA. Though I'm not entirely sure why that is the case. I've speculated a few ideas:

1. reaching definitions require a tighter bound,
2. invalid paths through recursion could ruin analysis,
3. there is some dark magic here that I'm unaware of.

But ultimately, given the context, I'm not sure why we need both CSA and CIA to compute space requirements across function calls.

Answer 1

It's a tradeoff between accuracy vs running time. CSA often provides more accurate (more precise) results than CIA; but it takes longer. There's no hard-and-fast rule about when you must use one or the other; rather, you can use either, and you choose where you want to live on that tradeoff.

Answer 2

Registers are different from memory in that you only have an absolute addressing mode, no indirect or relative addressing modes. They are also a finite resource in a way that can't be avoided (memory is also a finite resource, but compilers can often pretend that it is infinite and rely on the O.S. to kill the program if we run out of memory).

If you didn't have recursion (or only had tail recursion). You could do a CIA of every function to determine the maximum number of registers it required (other than for function calls) and then assign each function a different non-overlapping range of registers for every one of its internal variables.

But (a) that would be incredibly suboptimal because there will be many functions that are never live simultaneously (thus could be assigned overlapping ranges), and (b) you do have recursion.