Expression data flow graph: precise flow-sensitive pointer analysis for C programs
Date
Author
Institution
Degree Level
Degree
Department
Supervisor / Co-Supervisor and Their Department(s)
Examining Committee Member(s) and Their Department(s)
Citation for Previous Publication
Link to Related Item
Abstract
Pointer analysis is a program analysis that determines the memory locations pointed to by individual pointers. Imprecise pointer information is a major impediment to data-flow analyses and back-end optimizations that depend on pointer information.
Most pointer analyses are based on a points-to abstraction, which is an abstraction of memory that partitions the conceptually infinite number of memory locations into a finite number of abstract objects. In a flow-sensitive pointer-analysis, a points-to relationship between abstract objects is computed at each program point.
Our pointer analysis is based on another abstraction called the Expression Data Flow graph, which expresses the memory dependencies between expressions that appear in a program. This abstraction represents pointer information in a more compact and more precise way than a points-to abstraction.
We present a flow-sensitive and field-sensitive algorithm that computes a precise Expression Data Flow graph of a program in a negligible amount of time.