Scalable program analysis is becoming more and more important, because of the tremendous growth in the size and complexity of programs and applications such as advanced compiler optimizations, software engineering tools, and type systems for advanced languages. However, it remains challenging to design effective analyses for large software systems.

Often, static analysis can be viewed as generating constraints describing the relationships among the constructs in a program. Analysis then reduces to finding a suitable solution to these constraints. In this talk, I will discuss practical and theoretical results on implementing scalable analyses through constraint simplification.

I will first illustrate that constraint simplification is a key to scalability by presenting a static analysis based on a simple form of subtyping for analyzing production-size factory control software. I will then present some heuristics for simplifying general subtyping constraints. These techniques have enabled a cubic time alias analysis for C programs to be applied to programs with half a million source lines in a matter of seconds, which is orders of magnitude larger than what could previously be analyzed. Finally, I will present theoretical results on more powerful simplifications of subtyping constraints. The problems considered here have resisted many competent attacks for almost ten years. Answers to these questions can enable the implementation of many powerful program analysis and advanced type systems.