10. Global Optimization

Previous

Table of Contents

Next

Chapter 9
Advanced Techniques

Here is the disappointing chapter, which I refer to as the black box chapter. Due to space and time considerations, the book cannot include information on dependence-analysis-based transformations and interprocedural analysis. However, this is the place in the compiler where these techniques are applied. So we will outline the ideas of these phases and refer the reader to the work of Wolfe (1996), Cooper (1988 and 1989), Torczon (1985), Callahan, Cooper, Kennedy, and Torczon (1986), and Hall (1991) for the details.¹

---

¹If a cohesive set of algorithms is not published by one of the researchers, this may be grounds for a second book to complete these ideas. I would rather see a book by one of the researchers that addressed these issues in sufficient detail. But if they do not, then we engineers must publish the work to help ourselves.

---

At this point the flow graph has been simplified by constant folding, elimination of most redundant expressions, and algebraic simplification. The compiler now can do the advanced transformations that are the basis of much recent research. These are the transformations for improving the use of the memory caches and identifying parallel computations.

9.1 Interprocedural Analysis

Initially the compiler compiles each procedure individually, one procedure or flow graph at a time. In fact, the compiler is organized as a production line: Each procedure is translated into a flow graph and fed through the compiler, one at a time, until the results are added to the object file. With this structure, the compiler does not know about the effects of any procedure or function calls. It does not know which variables might be modified by each procedure call, so it must assume the worst.

For interprocedural analysis, this organization must be changed. However the change can be hidden inside the interprocedural analysis phase if careful data abstractions are maintained. Interprocedural analysis requires information about multiple procedures within the application program, so the compile-one-at-a-time approach must be modified. Instead, the compiler must accumulate the flow graphs (and other data) for each procedure. When all of the flow graphs have been found, the whole program can be analyzed to find the effects of each procedure call more precisely. Then the rest of the compilation can occur, one flow graph at a time (see Figure 9.1).

Figure 9.1  Schematic of Interprocedural Phase

In other words, the interprocedural analysis phase can be thought of as the stomach of the compiler. It gathers together all of the flow graphs of the application, processes them, and passes each one along to the rest of the compiler to be processed. As each flow graph is passed along, the inter-procedural analysis information about its calls and where they are called are available for the optimizers and code generators.

There are many ways in which this repository of information can be stored. One approach is to keep a library of procedures and their flow graphs on the disk as a complex data structure that is updated each time a file in the application is compiled. Another approach is to keep the repository in memory. In our sample case, the whole application will be compiled together. Another alternative is to compile the flow graph into an intermediate form that is kept on the disk in place of the object module. Before linking, the rest of the compilation is completed on this predigested form.

9.1.1 The Call Graph

The important data structure during interprocedural analysis is the call graph. This is a directed graph built from the flow graphs of all of the procedures. Each node in the graph is one of the procedures or flow graphs being compiled. There is an arc in the graph between a node N₁ and N₂ if there is a procedure call in N₁ that might call N₂. The edge is annotated with information indicating the binding between formal parameters (dummy arguments) and actual parameters. More properly, this data structure is a multigraph since there may be more than one edge between two nodes.

The definition of the call graph used the word “might” because the compiler cannot always determine which procedure is being called. Each language has a mechanism for dealing with a procedure or function that is not known at compile time. Pascal has procedure/function parameters; C has function variables; Fortran allows the concept of function arguments. In these cases the compiler has more difficulty determining which procedure is being called. When there is a doubt, the compiler must assume that there is a call of each possible procedure.

When there are procedure parameters or variables, the construction of the call graph may be more complex than you might imagine. For normal procedure and function calls, the compiler need only construct an edge from the entry for one procedure to the other. When a procedure variable or parameter is involved, edges might need to be entered each time a new procedure is discovered in the application program. There are two excellent papers on computing the call graph, one by Ryder (1979) and one by Hall and Kennedy (1992).

9.1.2 Simple Interprocedural Analysis Information

Most interprocedural analysis information involves complex properties of the flow graph and usage patterns of variables. However, there is an important collection of simple interprocedural information that are also useful.

Remember our discussion of the three types of edges for a flow graph. To build a safe graph, the compiler is required to create an abnormal edge from blocks containing a procedure call to the Exit block. This edge is inserted to model the case in which the procedure call might execute a longjmp operation that will cause control flow to exit that procedure and cause the procedure that performed the call to arrive at one of the procedures involved in getting to this point in the application execution. If one knows that there are no longjmp or exit operations in a procedure or any of the procedures that it calls (a common case), then these edges need not be added.

Often all calls of a procedure will have one of the arguments the same in all calls. Usually, this argument represents some parameter that is always the same in this application, and the user is using some standard library of procedures for some resource. Although we will later allude to techniques to compute when arguments are constants, it is useful to compute the obvious ones initially.

Previous

Table of Contents

Next