Program Optimization - Crafting a Compiler - page 636

Exercises

1. Using a common programming language, construct a program whose
control flow graph is the one shown in Figure 14.41.

2. Cycles in a procedure call graph do not necessarily indicate recursion.
Write code for methods P , Q ,and R so that the methods are not recursive,
yet they have Figure 14.8(b) as their procedure call graph.

3. Arguments concerning the likely structure of control flow graphs do not
easily extend to procedure call graphs. In general, we should not expect
structured or reducible procedure call graphs. Consider the recursive-
descent parser shown in Figure 5.7 on page 151. Build its procedure call
graph and analyze its structure.

4. For a procedure call graph, invocation of procedure P implies that all
DFST ancestors of P have been invoked. Thus, at runtime, the maximum
depth of a method-call stack is at least the height of a graph's DFST.
Given a cycle-free call graph for a program P , devise an algorithm that
computes the maximum depth of a method-call stack for P .

5. The algorithm in Figure 14.9 creates a DFST by picking a node Y at
Marker 26 such that ( X , Y )isanedgeintheDFSTif Y has not previously
been discovered.

(a) For an irreducible flow graph (e.g., Figure 14.8(b)), show that the
edges of the flow graph that are identified as back edges depend
on the order in which edges are considered by Marker 26 .
(b) Prove that for a reducible flowgraph, the same back edges are found
in any depth-first traversal that starts at the flow graph's root node.
(c) How many distinct DFSTs can be found for a flow graph G f =

( N f ,E f )?

6. Prove the following theorem:

Theorem 14.27 A flow graph G f is reducible i ff for all back edges ( X , Y ) ,
Y dominates X

7. Analyze the worst-case time complexity for the dominators algorithm
given in Figure 14.17.