Lecture 36, Basic Blocks Etc.

Part of the notes for 22C:196:002 (CS:4908:0002)
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Basic Blocks

In code generators, a basic block is defined as a maximal block of instructions containing no labels and no branches. Each basic block begins, therefore, with a label and ends with a (possibly conditional) branch or a just before a label. Identifying basic blocks allows us to subdivide the optimization problem into two separate problems: Optimal code generation within a block, and interblock optimization.

Register Allocation Within a Basic Block

Each basic block takes some set of variables as inputs, processes these variables through some transformations, changes the values of some set of variables, and finally, makes some set of branch decisions.

Generating optimal code for a basic block generally involves building a data-flow graph for the block. The vertices in this graph are either variables or operators. The edges are directed, indicating the direction of data flow. Each operation may be documented with time constraints, and each edge represents the use of a register to hold an intermediate value.

The register allocation problem therefore involves slicing the graph into successive segments. If there are n available registers, no slice may cut more than n distinct edges.

Interblock Optimization