this is part 4 of a series of videos
about compilers and the compilation of
computer programs for some compilers an
abstract syntax tree is the only
intermediate representation of the
source code the abstract syntax tree is
the output of the syntax analyzer and
the ultimate output of the compilers
front-end the abstract syntax tree is
then converted directly into binary
machine code
however some compilers do more work in
the front end they combine information
obtained by traversing the abstract
syntax tree with information from the
symbol table and generate another
intermediate representation of the
source code a sequence of elementary
program steps that looks rather like
assembly code some compilers create this
low-level code after building an
abstract syntax tree while others will
omit intermediate code at the same time
as building the abstract syntax tree in
fact some compilers go through the
motions of building a tree with all of
the syntax checking and semantic
checking that this allows for but only
intermediate code is left behind three
address code is one such example of an
intermediate code representation
low-level intermediate code provides
opportunities for significant
optimization optimization which is not
specific to the target machine and of
course low-level intermediate code
brings the program even closer to the
compilers ultimate goal efficient
error-free
machine code so let's say a little more
about three address code three address
code is an intermediate representation
common to many compilers because three
address code is not machine specific its
generation can be thought of as a
front-end task there's no single
language when it comes to three address
code rather different compilers might
generate their own variations of this
intermediate form but there's one
characteristic that all variations of
three address code
in common mainly that each assignment
instruction can only have one operator
on the right hand side and up to three
addresses in total the high-level
instruction X equals y plus Z times W
therefore becomes these three lines of
code instead which make use of temporary
variables t1 and t2 for what was
originally a complex expression in the
source code 3 address code
fixes the order in which operations must
be performed in reality a compiler might
implement three address instructions in
an object-oriented fashion in which
classes are used for different
instruction types alternatively each 3
address instruction may be implemented
as a record data structure with fields
for the addresses records known as
triples and quadruples are often used
for readability you can see source code
variable names in these three address
instructions however in reality each
source code name will have been replaced
with a pointer to an entry in the symbol
table 3 address code instructions that
alter the flow of control rely on
symbolic labels here's an if construct
in a high-level programming language
when converted into 3 address code this
fragment becomes a test with a
conditional jump to a label an
alternative implementation might use if
false as shown here this 3 address code
does the same job but a redundant go-to
instruction has been left out some
implementations of 3 address code used
jumps to line numbers rather than code
labels 3 a dress code is particularly
appropriate because it greatly
simplifies nested flow of control
statements like nested if blocks and
loops the high-level code fragment on
the left is clearly more compact than
the 3 address code on the right but the
relative simplicity of this 3 address
code lends itself well to optimization
again you can see that each complex
arithmetic expression has been reduced
to a sequence of much simpler
operations and that the iteration and
branching constructs have been replaced
with conditional and unconditional jump
instructions 3 a dress code can
represent complex boolean expressions
with sequences of tests in this
high-level code fragment X must be less
than 10 or X must be both bigger than 20
and less than y so that Z can be
assigned a value of 0 when this
expression is evaluated if X is found to
be less than 10 then there's no need to
evaluate the rest of the expression the
criteria have been met in 3 a dress code
we can perform a sequence of separate
tests if the output of the first test is
true that is if X is less than 10 then
we can jump straight to label l3
short-circuiting the other tests
generating 3a dress code for
instructions that alter the flow of
control and for complex boolean
expressions is problematic the compiler
walks the syntax tree and generates one
intermediate code instruction at a time
so it doesn't know which label of
forward to jump instruction should pass
control 2 while at jump instruction is
being generated for that reason the
compiler might generate a sequence of
jump instructions in which the targets
of those jumps are left unspecified
temporarily at least the compiler will
also maintain a list of jump
instructions whose targets have yet to
be specified when the targets of those
jumps are eventually known they can be
inserted into the 3 address code
sequence in effect the compiler can
create sequences of 3 address
instructions with only one pass over the
source code this technique is called
batter patching prior to the final step
of machine code generation a compiler
might partition 3 address code into
basic blocks basic blocks are sequences
of instructions that are always executed
together as you'll see they provide the
compiler with opportunities for various
types of optimization that don't depend
on the architecture of the
target machine basic blocks also allow
the compiler to analyze and improve the
flow of control in a program for example
by eliminating superfluous jump
instructions from the three address code
basic block optimizations can make it
easier to allocate and assign variables
to registers when the binary machine
code is finally generated deciding which
variables should be allocated to CPU
registers and which ones should go into
main memory can have a huge impact on
the performance of a program CPU
registers provide much faster access to
data than main memory but they're in
short supply a program will almost
certainly perform better if frequently
used variables reside in registers and
those which he used less often are held
in main memory consider this high-level
source code fragment again a condition
controlled while loop with an if block
inside it this is what it might look
like once it's been transformed into
three address code these are the basic
blocks a compiler will identify look at
the labels in goto statements and you'll
see that the flow of control can only
enter a basic block through the first
instruction of the block and control can
only leave a block via the last
instruction there are never any jumps
into or out of the middle of a basic
block generating basic blocks is
actually a fairly simple process the
compiler scans the intermediate code
looking for block boundaries that is
instructions that either transfer
control to another place in the program
or accept control from another place in
the program once the basic blocks have
been identified jump instructions can be
modified so that they jump to basic
blocks rather than labels or line
numbers this is important because the
order of the instructions within the
basic block may now be changed in an
attempt to optimize the code if this
happens the jump instructions will still
work behind the scenes the flow of
control between basic blocks is
represented using a graph data structure
this so-called flow graph includes a
node for each basic block
and the edges of the graph define how
control might pass from one block to
another each node of the flow graph
contains a linked list of three address
code instructions that make up the block
storing the instructions of each basic
block as a linked list is particularly
appropriate because as said before the
order of the instructions within the
basic block might now be changed the
linked list data structure allows the
implicit order of items to be changed
quickly
by simply manipulating pointers for
various reasons programmers don't always
write the most efficient source code
some programmers write more code than
strictly necessary for the sake of
clarity there's a lot to be said for
self documenting source code especially
if you're working in a team programmers
often search online for code fragments
which they copy into their own programs
as simply tweak to get things working
who is it once said I will always choose
a lazy person to do a hard job because a
lazy person will find an easy way to do
it many programmers unwittingly misuse
the features and constructs of a
language without considering the
possible side-effects for example it's
not uncommon for a programmer to
increment a loop counter one more time
than necessary or even to write code
inside a loop that could have easily
been placed outside but even the most
elegant programming style can result in
inefficient intermediate code the very
process of generating intermediate code
can produce long winded instruction
sequences basic blocks allow for
considerable optimization by the
compiler it should be said however that
the word optimization is something of a
misnomer optimization implies that the
final code will be optimal this can
never be optimization is an intractable
problem but the code can be improved
dramatically what's important is that
the compiler should never change what
the program actually does from the users
point of view the intermediate code
should be as efficient as possible
within reason
and the compiler should not take too
long getting their optimizations that
can be performed on a block-by-block
basis that is local optimizations
include the reordering of instructions
that don't depend on each other this
could potentially reduce the timer
variables value is held in the CPU
register freeing up that register for
something else for that reason if an
instruction that uses a variable can be
placed earlier in the block without
impacting on other instructions then it
might well be moved to a new position
the elimination of duplicate sub
expressions means less processing and
this can present opportunities for
further improvements later look at this
example the code calculates a value for
T by adding x and y together then later
calculates a value for u by adding
together x and y as long as the values
of x and y haven't changed in the
meantime
the second calculation can be eliminated
and replaced with an instruction that
simply copies the value of T to you of
course
deciding if x and y have changed in the
meantime is not trivial
one way to do this is to use a directed
acyclic graph if a complex expression in
the source code has been previously
represented as a directed acyclic graph
then a compiler may have already
exploited the opportunity to leave out
duplicate sub expressions when the three
address code was generated in the first
place many compilers on the other hand
will construct a directed acyclic graph
at this stage using the basic block code
as input while building this graph the
compiler will notice if there is already
a node with the same operator and the
same children as the one it's about to
add indicating a common sub-expression
consider this sequence of three address
code instructions a compiler will start
by creating three nodes for the first
statement like this the second statement
is also straightforward a new value for
B is calculated by subtracting D from
the third statement calculates a new
value for C by adding the most recent
value of B to the existing value of C
the final statement calculates D by
subtracting the current value of D from
the value of a since there's already a
node in the graph with the same children
and the same operator an existing part
of the tree can be reused once the
directed acyclic graph has been built
the three address code can be
reconstructed by doing a post order
traversal of the graph for each
operation with one or more variable
attached a three address instruction can
be constructed notice that in the new
sequence of instructions we still need
to calculate C using the new value of B
this is apparent in the graph the final
expression of the sequence however can
be replaced with a simple copy operation
this is also apparent in the graph in
fact the compiler can now replace any
subsequent uses of B in the program with
D this is known as copy propagation in
this basic block the value 3 is copied
to X then this is propagated to the next
statement this allows for an improvement
known as constant folding the value of y
can now be calculated by the compiler
which means less work for the compiled
program the calculation of Zed can also
be done by the compiler now which means
that the assignment of Zed is also a
simple copy operation in fact the copy
propagation and constant folding can
continue until there are no more
calculations to be done by the compiled
program only assignments of constant
values when the basic block ends some of
the variables may be used again within
the program these variables are said to
be live on exit if on the other hand an
instruction assigns a value to a
variable but that value is never used by
the rest of the program this is known as
dead code and
struction can be safely eliminated as
you'll see in a moment when the flow of
control between basic blocks is examined
the compiler may find large sections of
dead code algebraic transformations are
another type of optimization that can be
performed on a basic block for example
adding or subtracting zero from a
variable or multiplying it by one has no
effect these lines of code can all be
replaced with the same copy operation
some instructions are more processor
intensive than others that do the same
job for example rather than square a
number it's cheaper to multiply it by
itself to multiply a number by 2 it can
be added to itself instead to divide a
number by 2 it can be multiplied by
naught point 5 if an implementation of 3
a dress code supports left and right
shifts then these can be used to
multiply or divide repeatedly by 2 3
left shifts can replace multiplying by 8
for example in addition to block by
block local optimizations it might also
be possible for a compiler to optimize
the way information flows between blocks
for example if the flow graph reveals
that a basic block is not the target of
a jump and that it can't be reached by
falling through from another basic block
then the whole block can be eliminated
sometimes the intermediate code
generator itself will produce
unnecessary jumps and inadvertently
sequences of instructions that are
unreachable a sliding window known as a
people can be used to examine short
sequences of code across basic blocks
and this can reveal opportunities for
optimization in this example there's an
unconditional jump to label l1 followed
immediately by an unconditional jump to
l2 the first jump instruction can be
replaced with an unconditional jump
directly to l2
this means less processing some of the
time in fact if all of the instructions
between these jumps are unlabeled
they'll never be executed therefore all
of the instructions preceding the second
jump could be removed this example is
similar there's a conditional jump to L
1 and at L 1 there's an unconditional
jump to L 2 there might as well be a
conditional jump straight to L 2 which
means less processing some of the time
at least another flow of control
optimization worthy of mention is to
eliminate jumps over jumps for example
the condition in this conditional jump
can be adjusted to allow for a shorter
and more efficient code sequence
to summarize intermediate code is a
low-level linearized representation of
the high-level source code and
intermediate code is independent of the
target machine it's created by the
compilers front-end 3 a dress code is a
form of intermediate code implemented by
many compilers back patching is a
technique used to generate forward jump
instructions because the target of a
forward jump isn't known immediately
intermediate code instructions are
grouped into basic blocks each with only
one way in and one way out basic blocks
make it possible to perform various
machine independent optimizations on a
block by block basis peephole
optimization can be used to improve code
across basic blocks by examining several
instructions at a time through a sliding
window optimization may require several
passes over the intermediate code and
even then it's unlikely that the
intermediate code will ever be perfect
nevertheless the compiler has now turned
the original source code into something
much closer to its ultimate goal that is
efficient object code the intermediate
code is now ready for the final stage of
compilation the generation of executable
binary machine code