Print

Blaisdell, Jeffrey O.

Computer Science

2006

MS

Information obtained from static software analyses is valuable to applications ranging from compiler optimizations to program understanding tools, from software validation to security. One such analysis is flow analysis. Traditionally, program flow analysis has been modeled using directed graphs called control flow graphs. Though they provide natural flow sensitivity, control flow graphs are unable to provide complete context sensitivity. This thesis describes a new representation of control flow information termed path grammars. Path grammars, being inherently both flow and context sensitive, overcome the limitations of standard control flow graphs and permit the incorporation of both intraprocedural and interprocedural analyses into a single comprehensive model. The algorithm for the generation of path grammars from an abstract syntax tree or intermediate representation is described, and numerous examples are presented. Reaching definitions, a classic data flow analysis problem, was implemented in both path grammar and control flow graph frameworks. Empirical tests with both frameworks are compared for a number of SPEC2000 benchmark programs, and numerous statistics are collected. For the benchmarks tested, a thirty fold speedup on average and approximate three fold savings in maximum memory usage was seen using path grammars, demonstrating their practicality in both time and space.