ABSTRACT
A program graph is a directed graph G with a distinguished vertex s such that there is a directed path from s to every other vertex of G. In other words, every vertex in G is reachable from s. The vertex s is called the start vertex of G. We assume that there are no parallel edges in a program graph. The flow of control in a computer program can be modeled by a program graph in which each vertex represents a block of instructions which can be executed sequentially. Such a representation of computer programs has proved very useful in the study of several questions relating to what is known as the code-optimization problem. For many of the code-optimization methods to work, the program graph must have a special property called reducibility (see [1-9]). Two other concepts of interest in the study of program graphs are: dominators and dominator tree. The dominator tree of a program graph provides information about what kinds of code motion are safe. In this chapter we discuss algorithms to test the reducibility of a program graph and to generate a dominator tree. These algorithms make extensive use of depth-first search (DFS). For background information on DFS see Chapter 3.
