A Survey on Sparse Program Analysis

PhD Qualifying Examination


Title: "A Survey on Sparse Program Analysis"

by

Mr. Qingkai SHI


Abstract:

Sparse program analysis is known to be more efficient than traditional dataflow 
analysis as it eliminates unnecessary propagation of data-flow facts by 
skipping irrelevant instructions in a program. Therefore, sparse program 
analysis has been widely used to speed up static program analysis.

Because program analysis performs on a program intermediate representation 
(IR), a fundamental data structures standing for relations among program 
elements, we first study the evolution of program IRs supporting sparse program 
analysis. The development of these program IRs can be tracked with three 
interweaving plotlines. The first plotline is about static single assignment 
(SSA) form and its extensions, in which SSA form gives birth to the initial 
idea of sparse program analysis. In the face of some drawbacks of SSA form, 
researchers proposed many graphical program IRs, which make the second 
plotline. The third line is related to program dependence graph (PDG) and its 
extensions. Although PDG is initially proposed independent on SSA form, it then 
gradually draws advantages from SSA form.

To show the capability of the above program IRs, applications of them are 
introduced. The applications mainly include compiling optimization, pointer 
analysis and program verification. We believe our survey will shed light to our 
future work on sparse program analysis


Date:			Tuesday, 12 September 2017

Time:                  	3:00pm - 5:00pm

Venue:                  Room 4475
                         Lifts 25/26

Committee Members:	Dr. Charles Zhang (Supervisor)
 			Prof. Shing-Chi Cheung (Chairperson)
 			Prof. Fangzhen Lin
 			Dr. Wei Wang


**** ALL are Welcome ****