Abstract:

The silicon real estate available in systems-on-chip (SOC) has
given hope for the massive-parallel, high-performance
implementation of complex applications. However, new efforts in
silicon compilers that synthesize applications in C into SOC
cannot dodge an old problem, called pointer analysis, which has
been actively pursued in the programming language and compiler
community for two decades. The challenges of precise pointer
analysis stem from the need to explore an exponential number of
program execution paths, and the need to maintain program state
for every program point under all such paths.

In this talk, I will introduce a new method for constructing
scalable graph algorithms (ICCAD'02, PLDI'04), called
superposition, which solves different problem instances in an
aggregate fashion. Applying this method to pointer analysis,
different program states under different execution paths are
combined into a single Boolean function, and solved together using
the efficient, BDD-based image computation operator developed by
the formal verification community. Experimental results show that
context-sensitive, flow-insensitive analysis on programs with
billions of different calling paths can be performed, and
benchmarks as large as GCC (200KLOC) can be completed in seconds.

The subject of this talk can be of interest to researchers in CAD,
compiler, software engineering and security.

Speakers Bio:

Jianwen Zhu received the B.S degree in electrical engineering from
the Tsinghua University, Beijing, China, the M.S and Ph.D. degree
in computer science from the University of California, Irvine,
USA, in 1993, 1996 and 1999 respectively. He is currently an
assistant professor in the Department of Electrical and Computer
Engineering, University of Toronto, Canada. He is the coauthor of
the book SpecC: Specification Language and Methodology
(Kluwer-Academic, 2000). His research interest includes
hardware/software codesign, high-level synthesis for
high-performance circuits and retargetable compilation.