Intermediate Code
Generation
Logical structure of a compiler front end
Static checking includes type checking
An intermediate representation may
o either be an actual language
o or consist of internal data structures shared by phases of
the compiler.
Variants of Syntax Trees
Directed Acyclic Graphs for Expressions
o DAG identifies the common subexpressions (occur more than once)
o Constructed by using the same techniques of syntax trees.
o DAG for the expression of a+ a* (b - c) + (b - c) * d is
Directed Acyclic Graphs Steps for constructing the DAG
Syntax-directed definition to produce
syntax trees or DAG’s of
a+ a* (b - c) + (b - c) * d
Three-Address Code
There is at most one operator on the right side of an instruction
No built-up arithmetic expressions are permitted
For expression x+y*z, Three address instructions
o t1=y*z
o t2=x+t1, where t1 and t2 are temporaries.
It is a linearized representation of a syntax tree or a DAG
Addresses and Instructions
An address can be one of the following:
o A name
o A constant
o A compiler-generated temporary
Common three-address instruction forms:
o Assignment, x = y op z
o unary operation, x = op y
o Copy instructions, x=y
o An unconditional jump, go to L
o Conditional jumps, form if x go to L and if False x go to L
o Conditional jumps, if x relop y goto L
o Procedure calls and returns, y = call p, n
o Indexed copy, x = y [i] and x [i] = y.
o Address and pointer assignments, x = & y, x =* y, and * x = y.
Two possible translations of a statement
do i = i+1; while (a[i] < v);
Alternative representation of three address instructions
Three address instructions can be represented in a data
structure, like as objects or as records with fields for the
operator and the operands
Three alternatives are
o Quadruples
o Triples
o Indirect Triples
Quadruples (a = b* -c +b* -c )
Triples
Representations of a = b* -c +b* -c
Indirect triples
Consist of a listing of pointers to triples
Static Single-Assignment (SSA) Form
Two distinctive aspects distinguish SSA from three-address
code.
o All assignments in SSA are variables with distinct names;
o It (SSA) defines distinct variables (instead of same variable) in two
different control-flow paths.
Types and Declarations
Applications of types can be grouped under checking and
translation.
o Type checking
Uses logical rules to ensure the types of the operands match the type
expected by an operator
The && operator expects its two operands to be Boolean yielding type
Boolean
o Translation Applications
Type information is also needed to calculate the address (storage)
Type Expressions
Type Expressions represent the structure of types
A type expression is
o either a basic type
o or is formed by applying an operator called a type constructor
Following definition of type expressions
o A basic type is a type expression. int, void, char, etc..
o A type name is a type expression.
o Array: applying the array type constructor to a number is a type
expression.
o A record: record type constructor to the field names and their types.
o Function: type constructor
o If s and t are type expressions, then their Cartesian product s x t is a
type expression.
o Type expressions may contain variables whose values are type
expressions.
Type Expressions
Type expression for int [2][3]
Type Names and Recursive Types
Type Equivalence
When type expressions are represented by graphs, two
types are structurally equivalent if and only if one of the
following conditions is true:
o They are the same basic type.
o They are formed by applying the same constructor to
structurally equivalent types.
o One is a type name that denotes the other.
Declarations
D generates a sequence of
declarations
T generates basic, array, or record
types
B generates one of the basic types
int and float.
C generates strings of zero or more
integers, surrounded by brackets.
Storage Layout for Local Names
Type Checking
assign a type expression to each component of the source
program
type expressions conform to a collection of logical rules
Rules for Type Checking
Type checking can take on two forms:
o Type Synthesis: Builds up the type from its subexpressions.
Rule:
o Type Inference: Determines the type of a language construct from
the way it is used.
Rule:
Ex: null(x), length(x)
Type Conversions
Expressions like x + i, where x is float and i is integer.
For the expression 2 * 3.14:
o t1 = (float) 2
o t2 = t1 * 3.14
The rules for Java
o Widening
o Narrowing
Conversion
o Implicit: if it is done
automatically by the
compiler
o Explicit: if the programmer
must write something for the
conversion.
