Home | | **Compiler Design** | | **Compilers Principles, Techniques, & Tools** | | **Compiler Design** | Basic Blocks and Flow Graphs

1 Basic Blocks
2 Next-Use Information
3 Flow Graphs
4 Representation of Flow Graphs
5 Loops
6 Exercises for Section 8.4

**Basic Blocks and Flow Graphs**

*1 Basic
Blocks*

*2
Next-Use Information*

*3 Flow
Graphs*

*4
Representation of Flow Graphs*

*5 Loops*

*6
Exercises for Section 8.4*

This section introduces a graph representation of
intermediate code that is help-ful for discussing code generation even if the
graph is not constructed explicitly by a code-generation algorithm. Code
generation benefits from context. We can do a better job of register allocation
if we know how values are defined and used, as we shall see in Section 8.8. We
can do a better job of instruction selection by looking at sequences of
three-address statements, as we shall see in Section 8.9.

The representation is constructed as follows:

**
**Partition the intermediate code into
*basic blocks,* which are maximal
se-quences of consecutive three-address instructions with the properties that

The flow of control can only
enter the basic block through the first instruction in the block. That is,
there are no jumps into the middle of the block.

Control will leave the block
without halting or branching, except possibly at the last instruction in the
block.

The basic blocks become the nodes of a *flow graph,* whose edges indicate which blocks can follow which
other blocks.

**The Effect of Interrupts**

The
notion that control, once it reaches the beginning of a basic block is certain
to continue through to the end requires a bit of thought. There are many
reasons why an interrupt, not reflected explicitly in the code, could cause
control to leave the block, perhaps never to return. For example, an
instruction like x = y / z appears not to affect control flow, but
if z is 0 it could actually cause the program to abort.

We shall not worry about such possibilities. The
reason is as follows. The purpose of constructing basic blocks is to optimize
the code. Gener-ally, when an interrupt occurs, either it will be handled and
control will come back to the instruction that caused the interrupt, as if
control had never deviated, or the program will halt with an error. In the
latter case, it doesn't matter how we optimized the code, even if we depended
on control reaching the end of the basic block, because the program didn't
produce its intended result anyway.

Starting in Chapter **9,** we discuss transformations on flow
graphs that turn the original intermediate code into "optimized"
intermediate code from which better target code can be generated. The
"optimized" intermediate code is turned into machine code using the
code-generation techniques in this chapter.

**1. Basic Blocks**

Our first job is to partition a
sequence of three-address instructions into basic blocks. We begin a new basic
block with the first instruction and keep adding instructions until we meet
either a jump, a conditional jump, or a label on the following instruction. In
the absence of jumps and labels, control proceeds sequentially from one
instruction to the next. This idea is formalized in the following algorithm.

A l g o r i t h m 8.5 : Partitioning three-address instructions into
basic blocks.

**INPUT: **A sequence of three-address instructions.

**OUTPUT: **A list of the basic blocks for
that sequence in which each instruction** **is
assigned to exactly one basic block.

**METHOD: **First, we determine those instructions in the intermediate code that** **are *leaders,* that is, the first instructions in some basic block. The
instruction just past the end of the intermediate program is not included as a
leader. The rules for finding leaders are:

1. The first three-address instruction in the intermediate code is a
leader.

2. Any instruction that is the target of a conditional or unconditional
jump is a leader.

Any instruction that immediately
follows a conditional or unconditional jump is a leader.

Then, for each leader, its basic block consists of itself and all
instructions up to but not including the next leader or the end of the
intermediate program.

Example 8 . 6 : The intermediate code in Fig. 8.7 turns a 10 x 10
matrix a into an identity matrix. Although it is not important where this code
comes from, it might be the translation of the pseudocode in Fig. 8.8. In
generating the intermediate code, we have assumed that the real-valued array
elements take 8 bytes each, and that the matrix a is stored in row-major form.

First, instruction 1 is a leader
by rule (1) of Algorithm 8.5. To find the other leaders, we first need to find
the jumps. In this example, there are three jumps, all conditional, at
instructions 9, 11, and 17. By rule (2), the targets of these jumps are
leaders; they are instructions 3, 2, and 13, respectively. Then, by rule (3),
each instruction following a jump is a leader; those are instructions 10 and
12. Note that no instruction follows 17 in this code, but if there were code
following, the 18th instruction would also be a leader.

We conclude that the leaders are
instructions 1, 2, 3, 10, 12, and 13. The basic block of each leader contains
all the instructions from itself until just before the next leader. Thus, the
basic block of 1 is just 1, for leader 2 the block is just 2. Leader 3,
however, has a basic block consisting of instructions 3 through 9, inclusive.
Instruction 10's block is 10 and 11; instruction 12's block is just 12, and
instruction 13's block is 13 through 17. •

**2. Next-Use Information**

Knowing when the value of a variable will be used
next is essential for generating good code. If the value of a variable that is
currently in a register will never be referenced subsequently, then that
register can be assigned to another variable.

The *use* of a name in a
three-address statement is defined as follows. Suppose three-address statement *i* assigns a value to *x.* If statement *j* has *x* as an operand,
and control can flow from statement i to j along a path that has no intervening
assignments to x, then we say statement j uses the value of x computed at
statement i. We further say that x is live at statement i.

We wish to determine for each three-address statement x = y + z what the
next uses of x, y, and z are. For the present, we do not concern ourselves with
uses outside the basic block containing this three-address statement.

Our algorithm to determine liveness and next-use
information makes a back-ward pass over each basic block. We store the
information in the symbol table. We can easily scan a stream of three-address
statements to find the ends of ba-sic blocks as in Algorithm 8.5. Since
procedures can have arbitrary side effects, we assume for convenience that each
procedure call starts a new basic block.

Algorithm 8 . 7 : Determining the liveness and
next-use information for each statement in a basic block.

**INPUT: **A basic block** ***B***
**of three-address statements. We assume that the** **symbol table initially shows all nontemporary variables in *B* as being live on exit.

**OUTPUT: **At each statement** ***i: x = y + z*** **in** ***B,*** **we attach to** ***i*** **the liveness and** **next-use information of *x,
y,* and *z.*

**METHOD: **We start at the last statement in**
***B*** **and scan backwards to the** **beginning
of *B.* At each statement *i: x = y + z* in *B,* we do the following:

1. Attach to statement *i* the
information currently found in the symbol table regarding the next use and
liveness of *x, y,* and *y.*

2. In the symbol table, set x to "not live" and "no next use."

3. In the symbol table, set y and z to "live" and the next
uses of y and z to i.

Here we have used + as a symbol
representing any operator. If the three-address statement *i* is of the form *x* = + *y* or *x
= y,* the steps are the same as above, ignoring *z.* Note that the order of steps (2) and (3) may not be interchanged
because *x* may be *y* or *z. •*

**3. Flow Graphs**

Once an intermediate-code program
is partitioned into basic blocks, we repre-sent the flow of control between
them by a flow graph. The nodes of the flow graph are the basic blocks. There
is an edge from block *B* to block *C* if and only if it is possible for the
first instruction in block *C* to
immediately follow the last instruction in block *B.* There are two ways that such an edge could be justified:

There is a conditional or unconditional jump from the end of *B* to the beginning of *C.*

*C *immediately follows* B *in the
original order of the three-address instruc-tions, and *B* does not end in an unconditional jump .

We say that *B* is a *predecessor* of *C,* and *C*
is a *successor* of *B.*

Often we add two nodes, called
the *entry* and *exit,* that do not correspond to executable intermediate
instructions. There is an edge from the entry to the first executable node of
the flow graph, that is, to the basic block that comes from the first
instruction of the intermediate code. There is an edge to the exit from any
basic block that contains an instruction that could be the last executed
instruction of the program. If the final instruction of the program is not an
unconditional jump, then the block containing the final instruction of the
program is one predecessor of the exit, but so is any basic block that has a
jump to code that is not part of the program.

Example 8 . 8 : The set of basic
blocks constructed in Example 8.6 yields the flow graph of Fig. 8.9. The entry points to basic block B1, since B1 contains the first instruction of
the program. The only successor of B1 is B2, because B1 does not end in an unconditional jump, and the leader of B2 immediately follows
the end of B1.

Block B3 has two
successors. One is itself, because the
leader of B3, instruction 3, is the target of the conditional jump at the end
of £3, instruction 9. The other successor is B4, because control can fall
through the conditional jump at the end of B3 and next enter the leader of B±.

Only B*6* points to the exit of
the flow graph, since the only way to get to code that follows the program from
which we constructed the flow graph is to fall through the conditional jump
that ends *B*_{6}*.*

**4. Representation of Flow Graphs**

First, note from Fig. 8.9 that in the flow graph, it is normal to
replace the jumps to instruction numbers or labels by jumps to basic blocks.
Recall that every conditional or unconditional jump is to the leader of some
basic block, and it is to this block that the jump will now refer.

The reason for this change is that after constructing the flow graph, it
is common to make substantial changes to the instructions in the various basic
blocks. If jumps were to instructions,
we would have to fix the targets of the jumps every time one of the target
instructions was changed.

Flow graphs, being quite ordinary graphs, can be
represented by any of the data structures appropriate for graphs. The content
of nodes (basic blocks) need their own representation. We might represent the
content of a node by a pointer to the leader in the array of three-address
instructions, together with a count of the number of instructions or a second
pointer to the last instruction. However, since we may be changing the number
of instructions in a basic block frequently, it is likely to be more efficient
to create a linked list of instructions for each basic block.

5. **Loops**

Programming-language constructs
like while-statements, do-while-statements, and for-statements naturally give
rise to loops in programs. Since virtually every program spends most of its
time in executing its loops, it is especially important for a compiler to
generate good code for loops. Many code transformations depend upon the
identification of "loops" in a flow graph. We say that a set of nodes
*L* in a flow graph is a *loop* if

There is a node in *L* called the *loop entry* with the property that no other node in *L* has a predecessor outside *L.* That is, every path from the entry

of the entire flow graph to any node in *L* goes through the loop entry.

Every node in *L* has a nonempty path, completely within
L, to the entry of *L.*

Example 8 . 9 :
The flow graph of Fig. 8.9 has three loops:

1. B3 by itself.

2. B6 by itself.

3. {B2, B3,
B4}.

The first two are single nodes with an edge to the
node itself. For instance, B3 forms a loop with B3 as its entry. Note that the second requirement for a loop
is that there be a nonempty path from B3 to itself. Thus, a single node like
B2, which does not have an edge B2 ->• B2, is not a loop, since there is no
nonempty path from B2 to
itself within {B2}.

The third loop, L = {B2, B3, B4}, has B2 as its
loop entry. Note that among these three
nodes, only B2 has a predecessor, Bi, that is not in L. Further, each of the
three nodes has a nonempty path to B2
staying within L. For instance, B2
has the path B2 ->• B3
->• B4 -> B2.

**6. Exercises for Section 8.4**

Exercise 8 . 4 **.
1** : Figure 8.10 is a simple
matrix-multiplication program.

a) Translate the program into three-address statements
of the type we have been using in this section. Assume the matrix entries are
numbers that require 8 bytes, and that matrices are stored in row-major order.

Construct the flow graph for your
code from (a).

Identify the loops in your flow
graph from (b).

**for (i=0;
i<n; i++)**

**for
(j=0; j<n; j++) c[i] [j] = 0.0;**

**for (i=0;
i<n; i++)**

**for (j=0;
j<n; j++)**

**for (k=0;
k<n; k++)**

**c[i][j] = c[i][j]
+ a[i][k]*b[k][j];**

Figure 8**.10:** A matrix-multiplication algorithm

Exercise 8.4.2: Figure 8.11 is code to count the
number of primes from 2 to n, using the sieve method on a suitably large array
a. That is, a[i] is TRUE at the end only
if there is no prime Vi or less that evenly divides i. We initialize all a[i] to TRUE and then set a1j]
to FALSE if we find a divisor of j.

Translate the program into
three-address statements of the type we have been using in this section. Assume
integers require 4 bytes.

b) Construct the flow graph for your code from (a).

c) Identify the loops in your flow graph from (b).

**for
(i=2; i<=n; i++) a[i] = TRUE;**

**count = 0;**

**s =
sqrt(n);**

**for (i=2;
i<=s;** **i++)**

**if (a[i])
/* i has been found to be a prime
*/ {**

**count++;**

**for (j=2*i;
j<=n; j = j+i)**

**a[j] = FALSE;
/* no multiple of i is a prime */**

**}**

Figure **8.11:** Code to sieve for primes

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.