|
UNIT-IV |
||||||||||||||||
|
TOPIC: Code Generation |
||||||||||||||||
|
Unit-4/Lecture-01 |
||||||||||||||||
|
INTERMEDIATE CODE GENERATION In the analysis-synthesis model of a compiler, the front end analyzes
a source program and creates an intermediate representation, from which the
back end generates target code. This facilitates retargeting: enables
attaching a back end for the new machine to an existing front end. Intermediate Representations We could translate the source program directly into the target
language. However, there are benefits to having an intermediate,
machine-independent representation. · A clear distinction
between the machine-independent and machine-dependent parts of the compiler. · Retargeting is
facilitated the implementation of language processors for new machines will
require replacing only the back-end. · We could apply
machine independent code optimization techniques Intermediate representations span the gap between the source and
target languages. Ř High Level
Representations · closer to the
source language · easy to generate
from an input program · code optimizations
may not be straightforward Ř Low Level
Representations · closer to the
target machine · Suitable for
register allocation and instruction selection · easier for
optimizations, final code generation There are several options for intermediate code. They can be either Specific to the language being implemented ·
P-code for Pascal ·
Byte code for Java Issues in Design of Code generation (The various factors that affect
the code generation process): [RGPV, Dec 2013, Dec 2012] Code generator phase generates the target
code taking input as intermediate code. The output of intermediate code
generator may be given directly to code generation or may pass through code
optimization before generating code. Target code mainly depends on available
instruction set and efficient usage of registers. The main issues in design of code generation
(The various factors that affect the code generation process) are- 1. Input (Intermediate
code): The intermediate code produced by the
intermediate code generator or code optimizer of the compiler is given as
input to the code generator. At the time of code generation, the source
program is assumed to be scanned, parsed, and translated into a relatively
low-level intermediate representation. Type conversion operators are assumed
to be inserted wherever required, and that semantic errors have also been
detected. The code generation phase, therefore, proceeds on the assumption
that the input to the code generator is free from errors. We also assume that
the operators, data types, and the addressing modes appearing in the
intermediate representation can be directly mapped to the target machine
representation. If such straightforward mappings exist, then the code
generation is simple, otherwise a significant amount of translation effort is
required. 2. Structure of target
code: The efficient construction of a code generator
depends mainly on the structure of the target code which further depends on
the instruction-set architecture of the target machine. RISC (reduced
instruction set computer) and CISC (complex instruction set computer) are the
two most common target machine architectures. The target program code may be
absolute machine language code, relocatable machine language code, or
assembly language code. • If the target program code is absolute
machine language code, then it can be placed in a fixed memory location and
can be executed immediately. The fixed location of program variables and code
makes the absolute code generation relatively easier. • If the target program code is relocatable
machine language code (also known as object module), then the code
generation becomes a bit difficult as relocatable code may or may not be
supported by the underlying hardware. In case the target machine does not
support relocation automatically, it is the responsibility of compiler to
explicitly insert the code for ensuring smooth relocation. However, producing
a relocatable code requires subprograms to be compiled separately. After
compilation, all the relocatable object modules can be linked together and
loaded for execution by a linking loader. • If the output is assembly language
program, then it can be converted into an executable version by an assembler.
In this case, the code generation can be made simpler by utilizing the
features of assembler. That is, we can generate symbolic instruction code and
use the macro facilities of the assembler to help the code generation
process. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 463-465, 514-518}
|
||||||||||||||||
|
Unit-4/Lecture-02 |
||||||||||||||||
|
Issues in Design of Code generation: [Previous
Topic Continued…..] 3. Selection of
instruction: The nature of the instruction set of the
target machine is an important factor to determine the complexity of
instruction selection. The uniformity and completeness of the instruction
set, instruction speed, and machine idioms are the important factors that are
to be considered. If we are not concerned with the efficiency of the target
program, then instruction selection becomes easier and straightforward. The
two important factors that determine the quality of the generated code are
its speed and size. For example, the three-address
statement of the form, A = B + C X = A + Y can be translated into a code
sequence as given below: LD R0,B ADD R0,R0,C LD R0,A ADD R0,R0,Y ST X,R0 The main drawback of this statement by
statement code generation is that it produces redundant load and store
statements. For example, the fourth step in the above code is redundant as
the value that has been stored just before is loaded again. If the target
machine provides a rich set of instructions then there will be several ways
of implementing a given instruction. For example, if the target machine has
an increment instruction, X = X+1 then instead of multiple load and store
instructions, we can have simple instruction INC X. Note that deciding which machine-code
sequence is suitable for a given set of three-address instructions may
require knowledge about the context in which those instructions appear. 4. Allocation of
registers: Assigning the values to the registers is
the key problem during code generation. So, generation of a good code
requires the efficient utilization of registers. In general, the utilization
of registers is subdivided into two phases, namely, register allocation and
register assignment. Register allocation is the process of selecting a
set of variables that will reside in CPU registers. Register assignment
refers to the assignment of a variable to a specific register. Determining
the optimal assignment of registers to variables even with single register
values is difficult because the allocation problem is NP-complete. In certain
machines, even/odd register pairs are required for some operands and results
which make the problem further complicated. In integer multiplication, the
multiplicand is placed in the odd register, however, the multiplier can be
placed in any other single register, and the product (result) is placed in
the entire even/odd register pair. Register allocation becomes a nontrivial
task because of these architecture-specific issues. 5. Evaluation order: The performance of the target code is greatly affected by the order in
which computations are performed. For some computation order, only a fewer
registers are required to hold the intermediate results. Hence, deciding the
optimal computation order is again difficult since the problem is
NP-complete. The problem can be avoided initially by generating the code for
the three-address statements in the same order as that of produced by the
intermediate code generator. Back
patching: [RGPV, June 2006] Back patching is a technique to solve the
problem of replacing symbolic names in goto statements by the actual target
addresses. This problem comes up because of some
languages do not allow symbolic names in the branches. Idea: Maintain a list of branches that have
the same target label and replace them once they are defined. Example: Source:
if a or b then if c then
x= y+1 Translation:
if a go to L1
if b go to L1
go to L3 L1: if c goto L2 goto L3 L2: x= y+1 L3: After Backpatching: 100: if a goto 103 101:
if b goto 103 goto 106 Reference:
{Compilers: Principles, Techniques and Tools. Page No: 500-503, 516-518}
|
||||||||||||||||
|
Unit-4/Lecture-03 |
||||||||||||||||
|
LANGUAGE INDEPENDENT 3-ADDRESS CODE :[RGPV, DEC 2013] IR can be either an actual language or a group of internal data
structures that are shared by the phases of the compiler. C used as
intermediate language as it is flexible, compiles into efficient machine code
and its compilers are widely available. In all cases, the intermediate code
is a linearization of the syntax tree produced during syntax and semantic
analysis. It is formed by breaking down the tree structure into sequential
instructions, each of which is equivalent to a single or small number of
machine instructions. Machine code can then be generated (access might be
required to symbol tables etc). Three Address Code (TAC); can range from
high- to low-level, depending on the choice of operators. In general, it is a
statement containing at most 3 addresses or operands. The general form is x = y op z, where “op” is an operator, x is the
result, and y and z are operands. x, y, z are variables,
constants, or “temporaries”. A three-address instruction consists of at most 3 addresses
for each statement. e.g. x + y * z can be
translated as t1 = y * z t2 = x + t1 Where t1 & t2 are compiler–generated temporary names. Since it unravels multi-operator arithmetic expressions and nested
control-flow statements, it is useful for target code generation and
optimization. Example: Assignment instructions x = y op z OR x = op y OR x = y Syntax-Directed
Translation scheme for assignment into Three-Address Code: [RGPV, DEC 2013]
Where, E.place, the name that will hold the
value of E, and E.code, the sequence of three-address
statements evaluating E. Types of three address code There are different types of statements in source program to which
three address code has to be generated. Along with operands and operators,
three address code also use labels to provide flow of control for statements
like if-then-else, for and while. The different types of three address code
statements are: Assignment statement a = b op c In the above case b and c are operands, while op is binary or logical
operator. The result of applying op on b and c is stored in a. Unary operation a = op b This is used for unary minus or logical negation. Example: a = b * (- c) + d Three address code for the above example will be t1 = -c t2 = t1 * b t3 = t2 + d a = t3 Copy Statement a = b The value of b is stored in variable a. Unconditional jump goto L Creates label L and generates three-address code ‘goto L’ Creates label L, generate code for expression exp, If the exp returns
value true then go to the statement labelled L. exp returns a value false go
to the statement immediately following the if statement. Function call For a function fun with n arguments a1,a2,a3….an
ie., fun(a1, a2, a3,…an), the three address code will be Param a1 Param a2 … Param an Call fun, n Where param defines the arguments to function. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 466-470}
|
||||||||||||||||
|
Unit-4/Lecture-04 |
||||||||||||||||
|
QUADRUPLES, TRIPLES
AND INDIRECT TRIPLES:[RGPV,
June-2007] Three address codes are represented as record structure with fields
for operator and operands. These records can be stored as array or linked list. Most common implementations of three
address code are- Quadruples, Triples
and Indirect triples. 1.
QUADRUPLES Quadruples consist of four fields in the record structure. One field
to store operator op, two fields to store operands or arguments arg1and arg2
and one field to store result res. res = arg1 op arg2 Example: a = b + c b is represented as arg1, c is represented as arg2, + as op and a as
res. Unary operators like ‘-‘do not use agr2. Operators like param do not use
agr2 nor result. For conditional and unconditional statements res is label.
Arg1, arg2 and res are pointers to symbol table or literal table for the
names. Example: a = -b * d + c +
(-b) * d Three address code for the above statement is as follows t1 = - b t2 = t1 * d t3 = t2 + c t4 = - b t5 = t4 * d t6 = t3 + t5 a = t6 Quadruples for the above example is as follows 2.
TRIPLES [RGPV, Dec 2012] Triples use only three fields in the record structure. One field for
operator, two fields for operands named as arg1 and arg2. Value of temporary
variable can be accessed by the position of the statement the computes it and
not by location as in quadruples. Example: a = -b * d + c + (-b) * d Triples is as follows Arg1 and arg2 may be pointers to symbol table for program variables or
literal table for constant or pointers into triple structure for intermediate
results. Example: Triples for statement x[i] = y which generates two records is
as follows Triples for statement x = y[i] which generates two records is as
follows Triples are alternative ways for representing syntax tree or Directed
acyclic graph for program defined names. 3.
Indirect Triples Indirect triples are used to achieve indirection in listing of
pointers. That is, it uses pointers to triples than listing of triples
themselves. Example: a = -b * d + c + (-b) * d Conditional operator and operands. Representations include quadruples,
triples and indirect triples. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 470-472}
|
||||||||||||||||
|
Unit-4/Lecture-05 |
||||||||||||||||
|
SYNTAX TREES: Syntax trees are high level IR. They depict the natural hierarchical
structure of the source program. Nodes represent constructs in source program
and the children of a node represent meaningful components of the construct.
Syntax trees are suited for static type checking. modification of Syntax Trees: DAG [RGPV,
June-2007] A directed acyclic graph (DAG) for an expression identifies the common
sub expressions (sub expressions that occur more than once) of the
expression. DAG's can be constructed by using the same techniques that
construct syntax trees. A DAG has leaves corresponding to atomic operands and
interior nodes corresponding to operators. A node N in a DAG has more than
one parent if N represents a common sub expression, so a DAG represents expressions
concisely. It gives clues to compiler about the generating efficient code to
evaluate expressions. Applications of
DAG: 1.
DAGs are generally used for intermediate code representation in
compiler design. 2.
DAGs may
be used to model many different kinds of information. A collection of tasks
that must be ordered into a sequence, subject to constraints that certain
tasks must be performed earlier than others, may be represented as a DAG with
a vertex for each task and an edge for each constraint; algorithms for topological ordering may be used to generate a
valid sequence. 3.
DAGs may
also be used to model processes in which data flows in a consistent direction
through a network of processors. The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using
reachability. 4.
DAGs may be used as a space-efficient
representation of a collection of sequences with overlapping sub-sequences. 5.
DAGs are
increasingly used to show explicitly fundamental relationships. Example 1: Given the grammar
below, for the input string id + id * id , the parse tree, syntax tree and
the DAG are as shown. Example: DAG for the expression a + a * (b - c) + ( b - c ) * d is
shown below. Using the SDD to draw syntax tree or DAG for a given expression:- • Draw the parse tree • Perform a post order traversal of the parse tree • Perform the semantic actions at every node during the traversal – Constructs a DAG if before creating a new node, these functions
check whether an identical node already exists. If yes, the existing node is
returned. SDD to produce Syntax trees or DAG is shown below. For the expression a + a * ( b – c) + (b - c) * d, steps for
constructing the DAG is as below. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 287-290, 290-293,
464-466}
|
||||||||||||||||
|
Unit-4/Lecture-6 |
||||||||||||||||
|
Code Generation Algorithm: It Consisting of Two phases 1. Labeling phase 2. Code generation phase 1.
The Labeling Algorithm: Ř
Labels each
node of the tree with an integer: ·
fewest no. of
registers required to evaluate the tree with no intermediate stores to memory ·
Ř For leaf nodes
if n is the leftmost child of its parent then
label(n) := 1 else label(n) := 0 Ř For internal nodes
label(n) = max (l1, l2), if l1<> l2 = l1 + 1, if l1 = l2 2. Code Generation Algorithm: Procedure GENCODE(n) RSTACK – stack of registers, R0,...,R(r-1) TSTACK – stack of temporaries, T0,T1,... A call to Gencode(n) generates code to
evaluate a tree T, rooted at node n, into the register top(RSTACK) ,and the
rest of RSTACK remains in the same state as the one before the call A swap of
the top two registers of RSTACK is needed at some points in the algorithm to
ensure that a node is evaluated into the same register as its left child.
{ /* case 0 */ if n is a leaf representing operand N and is the leftmost child of its parent then print(LOAD N, top(RSTACK)) /* case 1 */
n is an interior node with operator OP, left child n1, and right child n2 then if label(n2) == 0 then { let N be the operand for n2; gencode(n1); print(OP N, top(RSTACK)); }
else if ((1 < label(n1) < label(n2)) and( label(n1) < r)) then { swap(RSTACK); gencode(n2); R := pop(RSTACK); gencode(n1); The
swap() function ensures that a node is evaluated into the same register
as its left child print(OP R, top(RSTACK)); push (RSTACK,R); swap(RSTACK); }
else if ((1 < label(n2) < label(n1)) and( label(n2) < r)) then { gencode(n1); R := pop(RSTACK); gencode(n2); /* R holds the result of n1 */ print(OP top(RSTACK), R); push (RSTACK,R); }
else { gencode(n2); T:= pop(TSTACK); print(LOAD top(RSTACK), T); gencode(n1); print(OP T, top(RSTACK)); push(TSTACK, T); } } Reference:
{Compilers: Principles, Techniques and Tools. Page No: 537-540}
|
||||||||||||||||
|
Unit-4/Lecture-07 |
||||||||||||||||
|
BASIC BLOCKS AND FLOW GRAPHS: A graph representation of three-address statements, called a flow
graph, is useful for understanding code-generation algorithms, even if the
graph is not explicitly constructed by a code-generation algorithm. Nodes in
the flow graph represent computations, and the edges represent the flow of
control. Flow graph of a program can be used as a vehicle to collect
information about the intermediate program. Some register-assignment
algorithms use flow graphs to find the inner loops where a program is
expected to spend most of its time. BASIC BLOCKS A basic block is a sequence of consecutive statements in which flow of
control enters at the beginning and leaves at the end without halt or
possibility of branching except at the end. The following sequence of
three-address statements forms a basic block: t1 := a*a t2 := a*b t3 := 2*t2 t4 := t1+t3 t5 := b*b t6 := t4+t5 A three-address statement x := y+z is said to define x and to use y or
z. A name in a basic block is said to live at a given point if its value is
used after that point in the program, perhaps in another basic block. The following algorithm can be used to partition a sequence of
three-address statements into basic blocks. Algorithm: Partition into
basic blocks. Input: A sequence of three-address statements. Output: A list of basic blocks with each three-address statement in
exactly one block. Method: 1. We first determine the set of leaders, the first statements of
basic blocks. The rules we use are the following: I) The first statement is a leader. II) Any statement that is the target of a conditional or unconditional
goto is a leader. III) Any statement that immediately follows a goto or conditional goto
statement is a leader. 2. For each leader, its basic block consists of the leader and all
statements up to but not including the next leader or the end of the program.
Example: Consider the
fragment of source code shown in fig. 7; it computes the dot product of two
vectors a & b of length 20. A list of three-address statements performing
this computation on our target machine is shown in fig. 8. begin prod := 0; i := 1; do begin prod := prod + a[i] * b[i]; i := i+1; end while i<= 20 end Let us apply Algorithm 1 to the three-address code in fig 8 to
determine its basic blocks. Statement (1) is a leader by rule (I) and
statement (3) is a leader by rule (II), since the last statement can jump to
it. By rule (III) the statement following (12) is a leader. Therefore,
statements (1) and (2) form a basic block. The remainder of the program
beginning with statement (3) forms a second basic block. (1) prod := 0 (2) i := 1 (3) t1 := 4*i (4) t2 := a [ t1 ] (5) t3 := 4*i (6) t4 :=b [ t3 ] (7) t5 := t2*t4 (8) t6 := prod +t5 (9) prod := t6 (10) t7 := i+1 (11) i := t7 (12) if i<=20 goto (3) BASIC BLOCK: Reference:
{Compilers: Principles, Techniques and Tools. Page No: 528-533} |
||||||||||||||||
|
Unit-4/Lecture-08 |
||||||||||||||||
|
DAG REPRESENTATION OF BASIC BLOCKS The goal is to obtain a visual picture of how information flows
through the block. The leaves will show the values entering the block and as
we proceed up the DAG we encounter uses of these values defs (and redefs) of
values and uses of the new values. Formally, this is defined as follows. 1. Create a leaf for the initial value of each variable appearing in
the block. (We do not know what that the value is, not even if the variable
has ever been given a value). 2. Create a node N for each statement s in the block. i. Label N with the operator of s. This label is drawn inside the
node. ii. Attach to N those variables for which N is the last def in the
block. These additional labels are drawn along side of N. iii. Draw edges from N to each statement that is the last def of an
operand used by N. 3. Designate as output nodes those N whose values are live on exit, an
officially-mysterious term meaning values possibly used in another block.
(Determining the live on exit values requires global, i.e., inter-block, flow
analysis.) As we shall see in the next few sections various basic-block
optimizations are facilitated by using the DAG. Finding Local Common Sub-expressions As we create nodes for each statement, proceeding in the static order
of the statements, we might notice that a new node is just like one already
in the DAG in which case we don't need a new node and can use the old node to
compute the new value in addition to the one it already was computing.
Specifically, we do not construct a new node if an existing node has the same
children in the same order and is labeled with the same operation. Consider computing the DAG for the following block of code. a = b + c c = a + x d = b + c b = a + x The DAG construction is explain as follows (the movie on the right
accompanies the explanation). 1. First we construct leaves with the initial values. 2. Next we process a = b + c. This produces a node labeled + with a
attached and having b0 and c0 as children. 3. Next we process c = a + x. 4. Next we process d = b + c. Although we have already computed b + c
in the first statement, the c's are not the same, so we produce a new node. 5. Then we process b = a + x. Since we have already computed a + x in
statement 2, we do not produce a new node, but instead attach b to the old
node. 6. Finally, we tidy up and erase the unused initial values. You might think that with only three computation nodes in the DAG, the
block could be reduced to three statements (dropping the computation of b).
However, this is wrong. Only if b is dead on exit can we omit the computation
of b. We can, however, replace the last statement with the simpler b = c.
Sometimes a combination of techniques finds improvements that no single
technique would find. For example if a-b is computed, then both a & b are
incremented by one, and then a-b is computed again, it will not be recognized
as a common sub-expression even though the value has not changed. However,
when combined with various algebraic transformations, the common value can be
recognized. To rearrange the final computation order for more-efficient
code-generation, we first obtain a DAG representation of the basic block, and
then we order the nodes of the DAG using heuristics. Heuristics attempts to
order the nodes of a DAG so that, if possible, a node immediately follows the
evaluation of its left-most operand. Heuristic DAG Algorithm: [RGPV, June 2007] This heuristic algorithm lists the nodes of a DAG such that the node's
reverse listing results in the computation order. { while there exists a
left-most child m of n that has no m = n } } order = reverse of the order of listing of nodes } Reference:
{Compilers: Principles, Techniques and Tools. Page No: 546-551}
|
||||||||||||||||
|
Unit-4/Lecture-09 |
||||||||||||||||
|
PEEPHOLE OPTIMIZATION: [RGPV Dec-2013, June-2007, June-2006] Peephole optimization is an efficient technique for optimizing either the target code or
the intermediate code. In this technique, a small portion of the code (known
as peephole) is taken into consideration and optimization is done by
replacing the code by the equivalent code with shorter or faster sequence of
execution. The quality of target code can be improved by applying
“optimizing” transformations to the target program. A simple but effective
technique for improving the target code is peephole optimization, a method
for trying to improving the performance of the target program by examining a
short sequence of target instructions (called the peephole) and replacing
these instructions by a shorter or faster sequence, whenever possible. The
peephole is a small, moving window on the target program. The code in the
peephole need not contiguous, although some implementations do require this. Some characteristics of the
peephole optimization are: redundant-
instruction elimination, unreachable code elimination, flow of control optimizations,
strength reduction and use of
machine idioms: 1.
Redundant-instruction elimination: Consider the following
instructions: MOV R0 , X MOV X, R0 The second instruction can be deleted since the first instruction
ensures that the value of X is already loaded into register R0.
However, it cannot be deleted in a situation when, it has a label which makes
it difficult to identify that whether the first instruction is always
executed before the second. To ensure that this kind of transformation in the
target code would be safe, the two instructions must be in the same basic
block. 2.
Unreachable code elimination: Removing an unlabeled instruction that immediately follows an
unconditional jump is possible. This process eliminates a sequence of
instructions when repeated. Consider the following intermediate code
representation: if error == 1 goto L1 goto L2 L1: Print error information L2: Here, the code is executed only if the variable error is equal to 1.
Peephole optimization allows the elimination of jumps over jumps. Hence, the
above code is replaced as follows irrespective of the value of the variable
debug. if error ! = 1 goto L2 Print error information L2: Now, if the value of the variable is set to 0, the
code becomes: if 0! = 1 goto L2 Print error information L2: Here, the first statement always evaluates to true. Hence, the
statement printing the error information is unreachable and can be
eliminated. 3.
Flow of control optimizations: The peephole optimization helps to
eliminate the unnecessary jumps in the intermediate code. For example,
consider the following code sequence: goto L1 … L1: goto L2 This sequence can be replaced by goto L2 … L1: goto L2 Now, if there are no jumps to L1 and the statement L1:
goto L2 is preceded by an unconditional jump, then this statement
can be eliminated. Similarly, consider the following code sequence: if (x < y) goto L1 … L1: goto L2 This sequence can be rewritten as follows: if (x < y) goto L2 … L1: goto L2 4.
Strength reduction: Peephole optimization also allows applying strength reduction
transformations to replace expensive operations by the equivalent cheaper
ones. For example, the expression X2 can be replaced by an
equivalent cheaper expression X * X.\ 5.
Use of machine idioms: Some target machines provide hardware instructions to implement
certain operations in a better and efficient way. Thus, identifying the
situations that permit the use of hardware instructions to implement certain
operations may reduce the execution time significantly. For example, some
machines provide auto-increment and auto-decrement addressing modes, which
add and subtract one respectively from an operand. These modes can be used
while pushing or popping a stack, or for the statements of the form X = X+1 OR X = X-1. These transformations greatly improve
the quality of the code. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 554-557}
|