Lecture 36, Basic Blocks Etc.
Part of
the notes for 22C:196:002 (CS:4908:0002)
|
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.
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.