Intermediate Code Generation

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.

Logical Structure of a Compiler Front End



A compiler front end is organized as in figure above, where parsing, static checking, and intermediate-code generation are done sequentially; sometimes they can be combined and folded into parsing. All schemes can be implemented by creating a syntax tree and then walking the tree.

Static Checking
This includes type checking which ensures that operators are applied to compatible operands. It also includes any syntactic checks that remain after parsing like
• Flow–of-control checks
– Ex: Break statement within a loop construct
• Uniqueness checks
– Labels in case statements
• Name-related checks

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
? Bytecode for Java
• Language independent:
? 3-address code

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).

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.


Variants of Syntax Trees: DAG
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.