[Compiler] 18. Interprocedural Analysis and Pointer Analysis

void init(int* arr, int n) {
    for (int i = 0; i < n; i++)
        arr[i] = 0;
}

void process() {
    int a[100];
    init(a, 100);
    int x = a[0];  // Is x = 0?
}

// Conservative assumptions (without interprocedural analysis):
// - A function call may modify all global variables
// - May modify all memory accessible through pointer parameters
// - Nothing can be known about the return value

// After interprocedural analysis:
// - init() modifies only the array pointed to by arr
// - init() does not modify global variables
// - After init(), arr[0..n-1] are all 0

// Program:
// main() -> foo() -> bar()
//        -> baz() -> bar()
//                 -> qux()

// Call graph:
//   main -> foo -> bar
//        -> baz -> bar
//               -> qux

typedef int (*FuncPtr)(int);

int add1(int x) { return x + 1; }
int mul2(int x) { return x * 2; }

void apply(FuncPtr f, int x) {
    int result = f(x);  // Cannot tell if f is add1 or mul2
}

// Java example:
// When Animal.speak() is called
// Dog.speak(), Cat.speak(), etc. - all subclass methods are possible targets

// CHA: Include speak() of all subclasses of Animal as candidates
// RTA (Rapid Type Analysis): Consider only actually instantiated types
// VTA (Variable Type Analysis): Track actual types of variables

// Function identity:
int identity(int x) { return x; }

// Call sites:
a = identity(1);   // Call 1
b = identity(2);   // Call 2

// Context-insensitive analysis:
// identity's x = {1, 2}  (merge arguments from all calls)
// identity's return value = {1, 2}
// -> a = {1, 2}, b = {1, 2}  (imprecise!)

// Context-sensitive analysis:
// Call 1 context: identity(1) -> return value = 1 -> a = 1
// Call 2 context: identity(2) -> return value = 2 -> b = 2
// Precise results!

// main -> foo -> identity  (context: [main, foo])
// main -> bar -> identity  (context: [main, bar])

// k-limited call string: Consider only the most recent k calls
// k=1: [foo], [bar]
// k=2: [main,foo], [main,bar]

// Summary of identity function:
// Input x -> Output x (identity function)
// Apply summary at each call site:
// identity(1) -> 1
// identity(2) -> 2

// Questions of pointer analysis:
// What can pointer p point to?

int a, b;
int *p;
if (cond)
    p = &a;
else
    p = &b;

// At this point, p's points-to set: pts(p) = {a, b}

// Address-of: p = &x  -> p points to x
// Copy:       p = q   -> p points to what q points to
// Load:       p = *q  -> p points to what q's pointee points to
// Store:      *p = q  -> what p points to points to what q points to

Algorithm: Andersen's Analysis

Input: Set of pointer assignment statements
Output: Points-to set for each variable

Rules:
  p = &x       ->  Add {x} to pts(p)
  p = q        ->  Add pts(q) to pts(p)
  p = *q       ->  For each element r in pts(q), add pts(r) to pts(p)
  *p = q       ->  For each element r in pts(p), add pts(q) to pts(r)

Repeat: Until no changes

// Program:
p = &a;     // pts(p) = {a}
q = &b;     // pts(q) = {b}
p = q;      // pts(p) = {a, b} (add pts(q) to pts(p))
r = &p;     // pts(r) = {p}
s = *r;     // r points to p, so add pts(p) = {a, b} to pts(s)
            // pts(s) = {a, b}

Algorithm: Steensgaard's Analysis

Rules:
  p = &x     ->  Set p's type to point to x
  p = q      ->  Unify points-to sets of p and q
  p = *q     ->  Perform appropriate unification
  *p = q     ->  Perform appropriate unification

Uses Union-Find data structure

// Program:
p = &a;     // pts(p) = {a}
q = &b;     // pts(q) = {b}
p = q;      // Unify p and q -> pts(p) = pts(q) = {a, b}
// Same result as Andersen

// But:
r = &c;     // pts(r) = {c}
p = r;      // Andersen: pts(p) = {a, b, c}, pts(r) = {c}
            // Steensgaard: p,q,r all unified -> pts = {a, b, c}
            // Steensgaard is less precise (r doesn't actually point to a,b)

// Alias relationship:
// Are *p and a aliases? -> If p points to a, they are aliases

// Three possible answers for aliases:
// Must-alias: Always point to the same location
// May-alias:  Might point to the same location
// No-alias:   Never point to the same location

void foo(int *p, int *q) {
    *p = 10;
    *q = 20;
    int x = *p;  // x = 10? or 20?
}

// In C, pointers of different types can be assumed not to alias
int *pi;
float *pf;
// pi and pf are no-alias (different types)

// Exception: char* can alias with any type
// Exception: union members

// Without restrict, a, b, c might alias
void add(int *a, int *b, int *c, int n) {
    for (int i = 0; i < n; i++)
        a[i] = b[i] + c[i];
}

// With restrict: no aliasing guaranteed
void add(int * restrict a, int * restrict b, int * restrict c, int n) {
    for (int i = 0; i < n; i++)
        a[i] = b[i] + c[i];  // Can be vectorized!
}

// Flow-insensitive analysis:
p = &a;     // Statement 1
p = &b;     // Statement 2
x = *p;     // Statement 3

// Result: pts(p) = {a, b} (same at all points)
// Even after statement 1, pts(p) = {a, b}

// Flow-sensitive analysis:
p = &a;     // After this point: pts(p) = {a}
p = &b;     // After this point: pts(p) = {b}  (previous value overwritten)
x = *p;     // At this point: pts(p) = {b}
            // -> x can only point to b (more precise!)

// Typical compiler choices:
// - Intraprocedural analysis: flow-sensitive (precision matters, small scale)
// - Interprocedural analysis: flow-insensitive (scalability matters, large scale)
// - Pointer analysis: mostly flow-insensitive (scalability issues)

// MOD(f): Set of variables function f may modify
// REF(f): Set of variables function f may reference

void foo() {
    x = 1;       // MOD(foo) = {x, ...}
    y = x + z;   // REF(foo) = {x, z, ...}
    bar();       // Propagate bar's MOD/REF as well
}

// MOD(foo) = {x} U MOD(bar)  (include what bar modifies)
// REF(foo) = {x, z} U REF(bar)

// Original:
int square(int x) { return x * x; }
int result = square(5);

// After inlining:
int result = 5 * 5;  // -> constant folding possible -> result = 25

// Partial inlining: inline only the hot path
void foo(int x) {
    if (x > 0) {     // 90% probability
        // Simple code  -> inline
    } else {
        // Complex code  -> keep function call
    }
}

// Function cloning: generate specialized versions for call contexts
void foo_const5() {   // Specialized for x=5
    // Code with x=5 constant-propagated
}