Issues in the design of a code generator

Code generator converts the intermediate representation of source code into a form that can
be readily executed by the machine. A code generator is expected to generate the correct code.
Designing of the code generator should be done in such a way that it can be easily
implemented, tested, and maintained.
The following issue arises during the code generation phase:
Input to code generator – The input to the code generator is the intermediate code generated
by the front end, along with information in the symbol table that determines the run-time
addresses of the data objects denoted by the names in the intermediate representation.
Intermediate codes may be represented mostly in quadruples, triples, indirect triples, Postfix
notation, syntax trees, DAGs, etc. The code generation phase just proceeds on an assumption
that the input is free from all syntactic and state semantic errors, the necessary type checking
has taken place and the type-conversion operators have been inserted wherever necessary.
 Target program: The target program is the output of the code generator. The output may
be absolute machine language, relocatable machine language, or assembly language.
o Absolute machine language as output has the advantages that it can be placed in a
fixed memory location and can be immediately executed. For example, WATFIV
is a compiler that produces the absolute machine code as output.
o Relocatable machine language as an output allows subprograms and subroutines
to be compiled separately. Relocatable object modules can be linked together and
loaded by a linking loader. But there is added expense of linking and loading.
o Assembly language as output makes the code generation easier. We can generate
symbolic instructions and use the macro-facilities of assemblers in generating
code. And we need an additional assembly step after code generation.
 Memory Management – Mapping the names in the source program to the addresses of data
objects is done by the front end and the code generator. A name in the three address
statements refers to the symbol table entry for the name. Then from the symbol table entry,
a relative address can be determined for the name.
Instruction selection – Selecting the best instructions will improve the efficiency of the
program. It includes the instructions that should be complete and uniform. Instruction speeds
and machine idioms also play a major role when efficiency is considered. But if we do not care
about the efficiency of the target program then instruction selection is straightforward. For
example, the respective three-address statements would be translated into the latter code
sequence as shown below:
P:=Q+R
S:=P+T

MOV Q, R0
ADD R, R0
MOV R0, P
MOV P, R0
ADD T, R0
MOV R0, S
Here the fourth statement is redundant as the value of the P is loaded again in that statement
that just has been stored in the previous statement. It leads to an inefficient code sequence. A
given intermediate representation can be translated into many code sequences, with significant
cost differences between the different implementations. Prior knowledge of instruction cost is
needed in order to design good sequences, but accurate cost information is difficult to predict.
 Register allocation issues – Use of registers make the computations faster in comparison to
that of memory, so efficient utilization of registers is important. The use of registers is
subdivided into two subproblems:
1. During Register allocation – we select only those sets of variables that will reside in the
registers at each point in the program.
2. During a subsequent Register assignment phase, the specific register is picked to access
the variable.
To understand the concept consider the following three address code sequence
t:=a+b
t:=t*c
t:=t/d
Their efficient machine code sequence is as follows:
MOV a,R0
ADD b,R0
MUL c,R0
DIV d,R0
MOV R0,t
1. Evaluation order – The code generator decides the order in which the instruction will be
executed. The order of computations affects the efficiency of the target code. Among many
computational orders, some will require only fewer registers to hold the intermediate
results. However, picking the best order in the general case is a difficult NP-complete
problem.
2. Approaches to code generation issues: Code generator must always generate the correct
code. It is essential because of the number of special cases that a code generator might face.
Some of the design goals of code generator are:
 Correct
 Easily maintainable
 Testable
 Efficient
 Disadvantages in the design of a code generator:

Limited flexibility: Code generators are typically designed to produce a specific type of code,
and as a result, they may not be flexible enough to handle a wide range of inputs or generate
code for different target platforms. This can limit the usefulness of the code generator in
certain situations.
Maintenance overhead: Code generators can add a significant maintenance overhead to a
project, as they need to be maintained and updated alongside the code they generate. This can
lead to additional complexity and potential errors.
Debugging difficulties: Debugging generated code can be more difficult than debugging hand-
written code, as the generated code may not always be easy to read or understand. This can
make it harder to identify and fix issues that arise during development.
Performance issues: Depending on the complexity of the code being generated, a code
generator may not be able to generate optimal code that is as performant as hand-written code.
This can be a concern in applications where performance is critical.
Learning curve: Code generators can have a steep learning curve, as they typically require a
deep understanding of the underlying code generation framework and the programming
languages being used. This can make it more difficult to onboard new developers onto a
project that uses a code generator.
Over-reliance: It’s important to ensure that the use of a code generator doesn’t lead to over-
reliance on generated code, to the point where developers are no longer able to write code
manually when necessary. This can limit the flexibility and creativity of a development team,
and may also result in lower quality code overall.

Global data flow analysis

o To efficiently optimize the code compiler collects all the information about the program
and distribute this information to each block of the flow graph. This process is known as
data-flow graph analysis.
o Certain optimization can only be achieved by examining the entire program. It can't be
achieve by examining just a portion of the program.
o For this kind of optimization user defined chaining is one particular problem.
o Here using the value of the variable, we try to find out that which definition of a variable
is applicable in a statement.
Based on the local information a compiler can perform some optimizations. For example,
consider the following code:

1. x = a + b;
2. x = 6 * 3

o In this code, the first assignment of x is useless. The value computer for x is never used in
the program.
 o At compile time the expression 6*3 will be computed, simplifying the second assignment
statement to x = 18;
Some optimization needs more global information. For example, consider the following code:

1. a = 1;
2. b = 2;
3. c = 3;
4. if (....) x = a + 5;
5. else x = b + 4;
6. c = x + 1;
In this code, at line 3 the initial assignment is useless and x +1 expression can be simplified as 7.

But it is less obvious that how a compiler can discover these facts by looking only at one or two
consecutive statements. A more global analysis is required so that the compiler knows the
following things at each point in the program:

o Which variables are guaranteed to have constant values

o Which variables will be used before being redefined
Data flow analysis is used to discover this kind of property. The data flow analysis can be
performed on the program's control flow graph (CFG).

The control flow graph of a program is used to determine those parts of a program to which a
particular value assigned to a variable might propagate.

Simple Code Generator

Compiler Design is an important component of compiler construction. It involves many
different tasks, such as analyzing the source code and producing an intermediate representation
(IR) from it, performing optimizations on the IR to produce a target machine code, and
generating external representations (ORs) for programs used in debugging or [Link]
improve the design of simple language generators,a new reusable component called “Simple
Code Generator” (SCG) is used which implements several functions that make it easy to create
simple code generators for any programming language. The SCG component consists of two
parts: firstly it contains a parser that transforms textual inputs into an abstract syntax tree;
secondly, its generated AST has expressions in a symbolic form wherever possible instead of
merely representing them as strings like most other compilers do today.
A code generator is a compiler that translates the intermediate representation of the source
program into the target program. In other words, a code generator translates an abstract syntax
tree into machine-dependent executable code. The process of generating machine-dependent
output from an abstract syntax tree involves two steps: one for constructing the abstract syntax
tree and another for generating its corresponding machine code.
The first step involves constructing an Abstract Syntax Tree (AST) by traversing all possible
paths through your input file(s). This tree will contain information about every bit of data in
your program as they are encountered during parsing or execution time; it’s important to note
that this can take place both at compile time (as part of compiling) or runtime (in some cases).
Register Descriptor

Register descriptors are data structures that store information about the registers used in the
program. This includes the registration number and its name, along with its type. The compiler
uses this information when generating machine code for your program, so it’s important to
keep it up-to-date while writing code.
The compiler uses the register file to determine what values will be available for use in your
program. This is done by walking through each of the registers and determining if they contain
valid data or not. If there’s nothing in a register, then it can be used for other purposes.

Address Descriptor

An address descriptor is used to represent the memory locations used by a program. Address
descriptors are created by the getReg function, which returns a structure containing
information about how to access memory. Address descriptors can be created for any
instruction in your program’s code and stored in registers or on the stack; however, only one
instance of an address descriptor will exist at any given time (unless another thread is
executing).
When the user wants to retrieve data from an arbitrary location within the program’s source
code using getReg, call this method with two arguments: The first argument specifies which
register contains your desired value (e.g., ‘M’), while the second argument specifies where
exactly within this register should it be placed back onto its original storage location on
disk/memory before returning it back up into main memory again after successfully accessing
its contents via indirect calls like LoadFromBuffer() or StoreToBuffer().

Code Generation Algorithm

The code generation algorithm is the core of the compiler. It sets up register and address
descriptors, then generates machine instructions that give you CPU-level control over your
program.
The algorithm is split into four parts: register descriptor set-up, basic block generation,
instruction generation for operations on registers (e.g., addition), and ending the basic block
with a jump statement or return command.
Register Descriptor Set Up: This part sets up an individual register’s value in memory space
by taking its index into an array of all possible values for that type of register (i32). It also
stores information about what kind of operation was performed on it so that subsequent steps
can identify which operation happened if they’re called multiple times during execution.
Basic Block Generation: This step involves creating individual blocks within each basic block
as well as lines between them so we can keep track of where things are happening at any given
moment during execution.
Instruction Generation For Operations On Registers: This step converts source code
statements into machine instructions using information from both our ELF file format files (the
ones generated by GCC) as well as other sources such as Bazel’s build system which knows
how to generate particular kind of machine code for particular CPUs. This is where we start to
see how compilers work in practice, as they’re able to generate code that’s optimized in
various ways based on the type of operation being performed (e.g., addition) and the registers
involved (i32). This step can also be thought of as “register allocation” because it’s where we
determine which registers will be used for each operation, and how many there are in total.
This step uses the information generated in the previous steps as well as other information such
as rules about how many registers are needed for certain operations. For example, we might
know that 32-bit addition requires two registers: one to hold the value being added, and one for
the result of this operation.
Instruction Scheduling: This step reorders instructions so that they’re executed efficiently on
a particular CPU architecture. This step uses information about the execution resources
available on each CPU architecture to determine the best order for executing operations. It also
considers things like whether or not we have enough registers to store values (if some are in
use), or if there’s a bottleneck somewhere else in the pipeline.

Design of the Function getReg

The getReg function is the main function that returns the value of a register passed in. It uses
two parameters: A register number, and an action to perform on it. When you call getReg with
no parameter, it will return all registers’ values (i.e., all registers).
If you want to return a specific register’s value, then you can call getReg with that register
number and nothing else; if there are other parameters after this one (ie: 2nd parameter), then
they’ll be searched for related to that first parameter’s type instead of being added as yet
another argument after everything else has been evaluated already — this way we don’t waste
any time processing data when nothing happens at all! If there isn’t anything after those two
types but just an empty string (” “); then nothing happens either.
The output of this phase is a sequence of machine instructions that can be executed, with the
help of a runtime system. This code generator generates assembly language for the target
computer and object code for the target computer. The code generator is responsible for
generating the assembly language for the target computer. It takes as input an intermediate
format (sometimes called a compiler IR), which has been processed by the parser and typed
checker but not yet lowered into machine code.
The code generator is also responsible for generating object code that can be executed on the
target computer. This object code is usually in a format specific to the target architecture, such
as Intel 8086 or Motorola 68000.
The compiler front end parses source code and performs some initial analysis on it. It then
passes this data through several phases of compilation which turns it into machine instructions
that can run on a computer processor.

Code generation from DAG

One of the ideas behind the DAG construction is code generation. The steps involved include
reordering of the instructions, labeling the nodes with the number of registers required and use
this information to generate target assembly language code.

The code generation algorithm uses a recursive procedure on a labeled DAG. Considers code
generation based on the labels assigned to the nodes. It uses two stacks, one register stack
“rstack” and another memory stack, “mstack”. Stack “rstack” is used to allocate registers.
Initially rstack contains all available registers. The algorithm retains the registers on rstack in the
same order it has found them. The typical functions of the stack, like push(), pop() is used to
rearrange the rstack and in addition, the algorithm uses a swap(rstack) function to interchange
the top two registers on rstack.

The algorithm, considers five different cases to generate code. They are discussed as follows:

• Case 0: This is a simple and terminating case of the recursive procedure. If, ’n’ is a leaf
and the leftmost child of its parent, we generate just a load instruction.
• Case 1: This is the situation when the right node is a leaf and the left node could be a sub-
tree. In this case, we generate code to evaluate n1 into register R=top(rstack) followed by the
instruction “op name R”.
• Case 2: The right sub-tree requires more registers than the left sub-tree. A sub-tree of the
form where n1 can be evaluated without stores but n2 is harder to evaluate than n1 as it requires
more registers. For this case, swap the top two registers on rsatck, then evaluate n2 into
R=top(rstack).We remove R from rstack and evaluate n1 into S = top(rstack). Then we generate
the instruction “op R, S”, which produce the value of “n” in register S. Another call to swap
leaves rstack as it was, upon this call code generation begins.

• Case 3: It is similar to case 2 except that here the left sub-tree is harder and is evaluated
first. There is no need to swap registers here.
• Case 4: It occurs when both sub-trees require r or more registers to evaluate without
stores. Since we must use a temporary memory location, we first evaluate the right sub-tree into
the temporary T, then the left sub-tree, and finally the root.

Symbol Table in Compiler

Every compiler uses a major tool called the symbol table to keep track of all the variables,
functions, and other identifiers a program may have. The symbol table will store the name, its
type, and perhaps its memory locations to support the compiler in error checking, scope
management, and the optimization of the code for runtime efficiency.

What is a Symbol Table?

A symbol table is one of the most important data structures within a compiler, where all the
identifiers used in a program are stored along with their type, scope, and memory locations.
The symbol table is built during the earliest stages of compilation. It helps ensure the correct
usage of all identifiers according to the language’s rules in order for efficient code generation
and error checking to be performed. It has built-in lexical and syntax analysis phases.
 The information is collected by the analysis phases of the compiler and is used by the
synthesis phases of the compiler to generate code.
 It is used by the compiler to achieve compile-time efficiency.
 It is used by various phases of the compiler as follows:-
o Lexical Analysis: Creates new table entries in the table, for example, entries
about tokens.
o Syntax Analysis: Adds information regarding attribute type, scope, dimension,
line of reference, use, etc in the table.
o Semantic Analysis: Uses available information in the table to check for
semantics i.e. to verify that expressions and assignments are semantically
correct(type checking) and update it accordingly.
o Intermediate Code Generation: Refers to symbol table for knowing how much
and what type of run-time is allocated and table helps in adding temporary
variable information.
o Code Optimization: Uses information present in the symbol table for machine-
dependent optimization.
o Target Code generation: Generates code by using the address information of
the identifier present in the table.
Symbol Table entries – Each entry in the symbol table is associated with attributes that
support the compiler in different phases.

Example of Use of Symbol Table

Imagine a program that includes a series of mathematical expressions, such as:
 A variable distance representing the distance traveled.
 A constant pi representing the value of Pi.
 A function calculate Area that computes the area of a circle.

Memory
Name Type scope address value Additional Info

distance variable Global 0x1000 Uninitialized Data type: float

Data type: float, read-

constant Global 0x1004 3.14159
pi only

calculateArea function Global 0x1008 N/A Return type: float

radius parameter Local 0x2000 0x1000 Data type: float

In this example:
 The symbol table records that distance is a global variable of type float that has not been
initialized.
 Pi is a global value of type float with a constant value of 3.14159 and is marked as read-
only.
 It registers the function calculateArea that returns a value of type float.
 The parameter radius is declared as a local variable – in the scope of the function – also of
type float.
 It is this organization that serves the compiler when it does various tasks, such as checking
for type errors, optimization of code, knowing the value of pi because it is a constant,
declaring and using variables according to its scope.
Use of Symbol Table
The symbol tables are typically used in compilers. Basically compiler is a program which
scans the application program (for instance: C program) and produces machine code.
During this scan compiler stores the identifiers of that application program in the symbol
table. These identifiers are stored in the form of name, value address, type.
Here the name represents the name of identifier, value represents the value stored in an
identifier, the address represents memory location of that identifier and type represents the data
type of identifier.
Thus compiler can keep track of all the identifiers with all the necessary information.
Items stored in Symbol table
 Variable names and constants
 Procedure and function names
 Literal constants and strings
 Compiler generated temporaries
 Labels in source languages
Information used by the compiler from Symbol table
 Data type and name
 Declaring procedures
 Offset in storage
 If structure or record then, a pointer to structure table.
 For parameters, whether parameter passing by value or by reference
 Number and type of arguments passed to function
 Base Address
Operations of Symbol table
The basic operations defined on a symbol table include
 Operations on Symbol Table
Following operations can be performed on symbol table-
 Insertion of an item in the symbol table.
 Deletion of any item from the symbol table.
 Searching of desired item from symbol table.

Implementation of Symbol table

Following are commonly used data structures for implementing symbol table
List
We use a single array or equivalently several arrays, to store names and their associated
information ,New names are added to the list in the order in which they are encountered . The
position of the end of the array is marked by the pointer available, pointing to where the next
symbol-table entry will go. The search for a name proceeds backwards from the end of the
array to the beginning. when the name is located the associated information can be found in the
words following next.
id1 info1 id2 info2 …….. id_n info_n

 In this method, an array is used to store names and associated information.

 A pointer “available” is maintained at end of all stored records and new names are added in
the order as they arrive
 To search for a name we start from the beginning of the list till available pointer and if not
found we get an error “use of the undeclared name”
 While inserting a new name we must ensure that it is not already present otherwise an error
occurs i.e. “Multiple defined names”
 Insertion is fast O(1), but lookup is slow for large tables – O(n) on average
 The advantage is that it takes a minimum amount of space.
 Linked List
 This implementation is using a linked list. A link field is added to each record.
 Searching of names is done in order pointed by the link of the link field.
 A pointer “First” is maintained to point to the first record of the symbol table.
 Insertion is fast O(1), but lookup is slow for large tables – O(n) on average

Hash Table
 In hashing scheme, two tables are maintained – a hash table and symbol table and are the
most commonly used method to implement symbol tables. A hash table is an array with an
index range: 0 to table size – 1. These entries are pointers pointing to the names of the
symbol table.
 To search for a name we use a hash function that will result in an integer between 0 to table
size – 1.
 Insertion and lookup can be made very fast – O(1).
 The advantage is quick to search is possible and the disadvantage is that hashing is
complicated to implement.
Binary Search Tree
 Another approach to implementing a symbol table is to use a binary search tree i.e. we add
two link fields i.e. left and right child.
 All names are created as child of the root node that always follows the property of the
binary search tree.
 Insertion and lookup are O(log 2 n) on average.
Basic blocks :