Taming Pointers – A Symbolic Approach

Taming Pointers – A Symbolic Approach

Speaker Professor Jianwen Zhu 
Department of Electrical and Computer Engineering
University of Toronto, Canada
CECS Host Professor Daniel Gajski
Location McDonnell Douglas Auditorium
Date & Time Tuesday, August 17, 2004
Refreshments at 2:30pm, Seminar begins at 3:00pm
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.
Biography  

Jianwen Zhu received the B.S degree in electrical engineering from the Tsinghua University, Beijing, China, and the M.S. and Ph.D. degrees in computer science from the University of California, Irvine, 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.

Taming Pointers – A Symbolic Approach
click on the thumbnails to view the full-sized images