Pointer and Symbolic Analysis of Multithreaded Programs

Martin Rinard

Massachusetts Institute of Technology

Deep compiler analyses and transformations such as automatic parallelization and program distribution have traditionally focused on regular programs such as loop nests that access dense matrices using affine access functions. In this talk, we discuss foundational program analysis techniques for programs that access data structures using pointers and more sophisticated control structures such as recursion. In particular, we will present a new pointer analysis algorithm for multithreaded code, and an algorithm for the automatic parallelization of divide and conquer algorithms. We also discuss applications of our techniques to problems such as race detection in explicitly parallel programs, interprocedural array-bounds check elimination, and the automatic distribution of multithreaded object-oriented programs onto resource-constrained embedded systems.

Biographical Sketch Martin Rinard received the Sc.B. in Computer Science, Magna cum Laude and with Honors, from Brown University in 1984. He spent the next several years working for two startup companies, Ikan Systems and Polygen Corporation. He then entered the Ph.D. program in Computer Science at Stanford University, and received the Ph.D. in Computer Science from Stanford University in 1994. He joined the Computer Science Department at the University of California, Santa Barbara as an Assistant Professor in 1994, then moved to MIT as an Assistant Professor in 1997.

Host: Mooly Sagiv (sagiv@math.tau.ac.il)

For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html