Control Flow Infrastructure

February 26, 1998

Richard Henderson of Cygnus Solutions has donated a major rewrite of the control flow analysis pass in the compiler.

The fundamental goal of this rewrite is to provide data structures to represent the control flow graph that are more easily manipulated by optimization passes in the compiler.

The rewrite consists of building and maintaining two primary data structures, basic blocks and control edges between basic blocks. Each data structure contains information about the block/edge, pointers to the other data structure and the ability to attach pass specific information to either blocks or edges.

That basic framework makes certain analysis much easier, such as control dependence analysis, which is used by aggressive dead code elimination algorithms.

The basic framework also includes routines to allow global optimizers to insert instructions onto an edge in the flow graph. This is a key operation in global optimizers to expose maximum redundancies and to find optimal insertion points for expressions in the flow graph.