Code Generation

Code Generation

The last phase of the compiler is code generation. It is the compiler's back-end that makes multiple passes over the IR before generating the target program. The code generator's main task is instruction selection, registers allocation and assignment, and instruction ordering.

Code Generator Design Issue

A good code generator should produce the correct code, which is the benchmark for any code generator. There are many special cases available that the code generator can face. Due to the special case, correctness has special significance. A code generator should be designed with taking correctness in mind. The main goal of designing a code generator is its easy implementation, testing, and maintenance.

1) Input to the Code Generator

The input for the code generator is the intermediate representation (IR) of the source code generated by the compiler's front-end and symbol table's information. This input is used to know the run-time addresses of the data objects denoted by the names in the IR.

The intermediate representation has several choices such as three address codes like quadruple, triple, and indirect triples, virtual representations such as bytecodes and stack-machine code, linear representation like postfix notation and graphical representation like syntax tree and DAG representations.

We have assumed that the front-end of the compiler will be scanned, parsed, and translate the source code program into a low-level IR. So the target machine can easily manipulate the values of the names visible in the IR.

We will also assume that the intermediate code as input requires for code generation is error-free.

2) Target Program

The target program is known as the output of the code generator. The output can be any one of the following:

  • Absolute machine language: This kind of output can be placed at any particular location in memory and executed immediately.
  • Relocatable machine language: Thistype of output is also known as an object module. It allows the subprogram to be compiled separately.
  • Assembly language: Thistype of output makes the activity of code generation somewhat easier.

3) Instruction Selection

The target machine will execute the IR program mapped into a code sequence by a code generator.

The following factors determine the difficulty of performing this mapping:

  • The level of the intermediate representations
  • The nature of the instruction-set architecture
  • The quality of the generated code
  • When the IR level is high, the code generator can translate each IR statement into a sequence of machine instructions with the help of a template code.
  • When the IR level is low, the code generator can use this information to generate more efficient code sequences.
  • The difficulty of instruction selection is determined by the nature of the instruction set of the target machine. The instruction set should be uniform and complete.
  • If the target machine does not uniformly support each data type, then each exception to the general rule requires special handling.
  • If we consider the efficiency of the target program, the instruction speeds and machine idioms are other important factors.
  • The speed and size are criteria to detect the quality of the generated code.

Example:

a = b + c

d = a + e

The set of three-address statements will be translated into:

LD R0, b                                // R0 = b

ADD, R0, R0, c                     // R0 = R0 + c

ST, a, R0                               // a = R0

LD R0, a                               // R0 = a

ADD, R0, R0, e                   // R0 = R0 + e

ST d, R0                              // d = R0

Register Allocation

A key problem in code generation is to decide what values should be assigned to which registers. Those instructions that involve register operands are invariably shorter and faster than those instructions which involve memory operand.

The use of register can raise some sub-problem mentioned below:

  1. Register allocation: During register allocation, we will select the set of variables that reside in registers.
  2. Register assignment: During the register assignment, we will pick the specific register that holds a variable.

Certain machines require register-pairs (even-odd pair of register) for some operands and results. 

Example

Consider the following form of multiplication instruction:

M x, y 

Where x is the multiplicand odd register in the even/odd register pair and y is the multiplier. The odd/ even register occupies entire products.

Evaluation Order

The efficiency of the target code can be affected by the order in which computations are performed. Some other computation orders require fewer registers to hold intermediate results than others.                                                                             


Related Topics

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Ambiguity Elimination Compiler Design

Ambiguity Elimination Ambiguity elimination makes the sentence clear and readable. A sentence is grammatically ambiguous if it can produce more than one parse tree for a particular grammar. In this article,...

3 minutes read.

LR Parser Compiler Design

LR Parser LR parsing is a type of bottom-up parsing that is used to parse the large class of grammars. Here "L" stands for left-to-right scanning of the input "R" stands...

6 minutes read.

Data Flow Analysis in Compiler Design

Data Flow Analysis All the optimization techniques we have learned earlier depend on data flow analysis. DFA is a technique used to know about how the data is flowing in any...

3 minutes read.

LALR 1 Parsing | Compiler Design

LALR (1) Parsing The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical...

6 minutes read.

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

3 minutes read.

YACC in Compiler Design

YACC  YACC is known as Yet Another Compiler Compiler. It is used to produce the source code of the syntactic analyzer of the language produced by LALR (1) grammar. The input...

5 minutes read.

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say...

2 minutes read.

Machine-Independent Optimizations in Compiler Design

Machine-Independent Optimizations The main aim of machine-independent optimization is to improve the generated intermediate code so that compiler can get better target code. Eliminating unwanted code from the object code or replacing...

8 minutes read.

Shift Reduce Parsing in Compiler Design

Like the bottom-up parsing, the shift reduce parser also builds the parse tree from the leaves (bottom) to the root (up). The LR parser is a more versatile variation of...

4 minutes read.

Syntax-Directed Translation

Syntax-Directed Translation A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can...

3 minutes read.

Derivation and Parse Tree in Compiler Design

Derivation and Parse Tree In this article, we will learn Derivation and Parse Tree. Derivations The parse tree can be constructed by taking a derivational view in which production is treated as rewriting...

4 minutes read.

Three-Address Code

Three-Address Code If there is at most one operator on the right side of the instruction, then the instruction will be the three-address code so that no arithmetic expressions are permitted....

2 minutes read.

Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is...

6 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.

LEX

LEX Lex is a tool/computer program that generates a Lexical analyzer. Lex is developed by Vern Paxson in C around 1987. Lex works together with the YACC parser generator. It allows...

3 minutes read.

Stack Allocation of Space

Stack Allocation of Space Almost all compilers for languages that use procedure, functions, or methods manage their run-time memory as a stack. Whenever a procedure is called, the local variable's space...

2 minutes read.

Errors in Compiler Design

Introduction Errors in compiler design refer to mistakes or issues that arise during the process of execution of the program. A compiler is a program that translates source code written in...

4 minutes read.

Target Machine

Target Machine A target machine is a byte-addressable machine. This machine has n general-purpose registers, R0, R1,.....Rn-1. A Simple Target Machine Model has three-address instruction. A full-edged assembly language would have...

3 minutes read.

Storage Allocation

Storage Allocation The storage allocation represents memory management. The allocation of memory can be done in the following ways: Static AllocationStack AllocationHeap Management Static Allocation: It is a procedure used for the allocation of...

1 minute read.