Unit-IV III-CSE
Compiler Design
Chapter-8
Code Optimization
Flow Graphs
Professor
Malineni Suseelamma Women’s Engineering College
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE
Contents
• 8.4.3 Flow Graphs
• 8.4.4 Representation of Flow Graphs
• 8.4.5 Loops
• 8.4.6 Exercises for Section 8.4
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 2
8.4.3 Flow Graphs
• Once an intermediate-code program is
partitioned into basic blocks, we represent 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:
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 3
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 instructions, 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.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 4
• 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.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 5
Figure 8.7: Intermediate code to set
a 10 x 10 matrix to an identity
matrix
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 6
• 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 B3,
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 B4.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 7
• Only B6 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 B6.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 8
8.4.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.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 9
• 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.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 10
8.4.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
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 11
• 1. 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.
• 2. 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.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 12
• 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, B1, 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.
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 13
8.4.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.
b) Construct the flow graph for your code from
(a).
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 14
c) Identify the loops in your flow graph from
(b).
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 15
• 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 i or less that evenly divides i.
• We initialize all a[i] to TRUE and then set a[j] to
FALSE if we find a divisor of j.
• a) 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).
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 16
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 17
V. Koteswara Rao, [Link]., [Ph.D]
SMIEEE, FIETE, PMACM, MACCS, MVSI, MISTE. 18