<aside> 💡 Key Points

• How to build call graph via class hierarchy analysis
• Concept of interprocedural control-flow graph
• Concept of interprocedural data-flow analysis
• Interprocedural constant propagation </aside>

I. Motivation

So far, all analyses we learnt are intraprocedural.

For better precision, we need Interprocedural analysis: propagate data-flow information along interprocedural control-flow edges

The concept “procedure” was used in old PL’s

II. Call Graph Construction (CHA)

To perform interprocedural analysis, we need call graph

A representation of calling relationships in the program

Essentially, a call graph is a set of call edges from call-sites to their target methods (callees)

Call graph is very important program information

1. Call Graph Construction for OOPLs

←Top← More Efficient ↔ More Precise →Bottom→

• Class hierarchy analysis (CHA)
• Rapid type analysis (RTA)
• Variable type analysis (VTA)
• Pointer analysis (k-CFA)

2. Method Calls in Java

• Private instance methods
• Superclass instance methods | - Other instance methods | | #Target methods | 1 | 1 | $\geq1$ (polymorphism) | | Determinacy | Compile-time | Compile-time | Run-time |

3. Method Dispatch of Virtual Calls