UC Irvine

Program analysis extracts software properties that are helpful to developers and provides invaluable insights into a program; it is essential to many computer science areas such as compiler optimizations, cybersecurity, and performance engineering, to name a few.In the past few decades, however, researchers and practitioners have found difficulties in scaling up program analyses of all kinds, both static or dynamic ones, with modern software whose size and complexity have rapidly increased. In this dissertation, we focus on two of the most important program analysis areas, dataflow and throughput analysis, and create two frameworks -- DFI and MCAD, respectively -- with the principle of combining several optimizations in a novel way to overcome the scalability issues in their areas.

Our contributions in DFI augments IFDS, an efficient dataflow analysis framework for distributive dataflow problems, with a more efficient algorithm and a sparse program representation.Our key insight is an entirely new way of looking at IFDS problems and the realization that doing things in the \textit{reverse} direction of the graph reachability algorithm leads to much better performance; scaling to programs that were previously out of reach due to physical memory constraints.

MCAD is a novel way of predicting the performance characteristics (\emph{e.g.} total cycle counts and instructions per cycle) of a program, based on combining the best ideas from both static and dynamic throughput analysis. It uses dynamic traces and run time information to drive a static throughput analysis engine. Such combination avoids poor accuracy across branch boundaries traditionally suffered by static approach and more importantly, has much better scalability than dynamic methods like cycle-accurate emulators. MCAD also shows comparable accuracy in differential throughput analysis.

Together with other works in the fields, this dissertation provides building blocks and novel ideas of combining different techniques for program analyses to scale up with the ever-growing size, complexity, and challenges of future software codebases.