Syntax-Directed Construction of Program Dependence Graphs

Abstract

We present an algorithm that constructs program dependence graphs as a program is parsed. For programs that contain only structured transfers of control, our algorithm does not require explicit control flow or postdominator information to compute exact control dependencies. For programs that contain explicit transfers of control, our algorithm can determine whether these transfers of control are used in a structured way, and if so, compute control dependencies without explicit control flow or postdominator information. When transfers of control are ill-behaved, our algorithm adjusts the control dependence information computed during the parse, to obtain exact control dependencies. For many programs, our algorithm provides savings in time and memory, because it does not require prior computation of control flow or postdominator information. However, our algorithm also calculates control flow information during the parse, and incorporates this information into the program dependence graphs that it constructs; the resulting graphs have a wider range of applicability than graphs that do not contain this information.


Related research categories:
(1) Program Analysis
(2) Control Dependence
(3) Control Flow

Go To Publications