Inter-procedural analysis (IPA): whole-program optimization across function boundaries

[yudongusa]

Background

All current optimization passes operate on a single function at a time (`FunctionPass`). Inter-procedural analysis (IPA) enables optimizations that require reasoning about multiple functions simultaneously — essential for eliminating redundancy in real-world programs where hot code is split across many small functions.

Goals

Call-graph construction

Build a CallGraph data structure (similar to llvm-analysis's CFG, but at module level):

• Nodes = functions
• Edges = call sites
• Distinguish direct calls, indirect calls (via pointer), and external calls
• Compute strongly connected components (SCCs) for bottom-up traversal order

Inter-procedural constant propagation (IPCP)

If a function is always called with the same constant argument, specialize the function for that constant:

• Identify call-site constant arguments
• Clone the callee with constants substituted
• Run intra-procedural ConstProp on the clone

Inter-procedural dead argument elimination

Remove function parameters that are never used by any caller. Reduces call overhead and enables further constant folding.

Escape analysis

Determine whether a pointer allocated in one function can "escape" to another function. Required for:

• Safe stack allocation of heap objects
• Proving aliasing cannot occur across calls

API sketch

// llvm-analysis/src/call_graph.rs
pub struct CallGraph { /* nodes + edges */ }
impl CallGraph {
    pub fn build(ctx: &Context, module: &Module) -> Self;
    pub fn callees(&self, f: FunctionId) -> &[FunctionId];
    pub fn callers(&self, f: FunctionId) -> &[FunctionId];
    pub fn sccs(&self) -> Vec<Vec<FunctionId>>;  // bottom-up SCC order
}

Acceptance criteria

• CallGraph in llvm-analysis with unit tests (cycles, DAGs, indirect calls)
• IPCP ModulePass that handles ≥1 constant-argument specialisation, with a test
• Dead-argument elimination ModulePass with a test
• Integrated into the O3 pipeline (see issue Optimization presets: implement -O0, -O1, -O2, -O3 pass pipelines #84)
• Benchmark on a multi-function module showing measurable improvement at O3 vs O2

References

• LLVM Interprocedural Optimizations
• Cooper & Torczon, "Engineering a Compiler", chapter 9