Program Analysis via Graph Sparseness

PhD Qualifying Examination


Title: "Program Analysis via Graph Sparseness"

by

Mr. Ahmed Khaled Abdelfattah ZAHER


Abstract:

Program analysis is concerned with determining certain properties of a program 
without exhaustively enumerating all of its possible executions, and it has 
found numerous applications in compiler optimization and software engineering. 
A wide range of program analysis tasks can be formulated as graph problems, 
which enables borrowing techniques and algorithms from the literature on graph 
algorithms to solve those problems. Unfortunately, the graph problems of 
interest usually have high computational complexity, and hence scalability 
issues arise even when using state-of-the-art algorithmic techniques.

We explore an exciting line of research which is based on the following 
observation: in the program analysis domain, the programs and properties under 
consideration often have certain structures which are naturally reflected in 
the corresponding graphs, often in the form of desirable sparsity properties. 
Using an appropriate notion of structuredness and sparseness, one can show, 
formally or empirically, that the resulting graphs are indeed sparse and 
subsequently use parameterized graph algorithms that exploit this sparseness, 
yielding a significantly faster solution compared to solving the same problem 
on arbitrarily complex graphs.

Results following this framework are surveyed in two parts: the first part is 
concerned with graphs in program analysis and their sparsity properties, and 
the second shows parameterized algorithms on those sparse graphs. Two program 
analysis problems are surveyed: register allocation and answering algebraic 
path queries within the framework of algebraic program analysis.


Date:                   Thursday, 16 May 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 2463
                        Lifts 25/26

Committee Members:      Dr. Amir Goharshady (Supervisor)
                        Dr. Sunil Arya (Chairperson)
                        Dr. Lionel Parreaux
                        Prof. Ke Yi