BCSE307L

COMPILER DESIGN
 Issues in the Design of a Code Generator
They are dependent on specifics of

the intermediate representation,

the target language, and

the run-time system.

Tasks such as instruction selection, register allocation and

assignment, and instruction ordering are encountered in the design of

almost all code generators.

 Issues in the Design of a Code Generator

The most important criterion for a code generator is that it

produce correct code.

 1. Input to the Code Generator

Intermediate representation of the source program produced by the front end,

along with information in the symbol table.

IR include three-address representations such as quadruples, triples, indirect

triples.

Virtual machine representations such as bytecodes and stack-machine code;

Linear representations such as postfix notation and graphical representations

such as syntax trees and DAG's.

 1. Input to the Code Generator

We also assume that all syntactic and static semantic errors have

been detected.

The necessary type checking has taken place, and that type

conversion operators have been inserted wherever necessary.

We assume that the front end has scanned, parsed, and translated

the source program into a relatively low-level IR.

 2. The Target Program

The most common target-machine architectures are RISC (reduced

instruction set computer), CISC (complex instruction set computer),

and stack based.

RISC machine typically has many registers, three-address instructions,

simple addressing modes, and a relatively simple instruction-set

architecture.
 2. The Target Program

CISC machine typically has few registers, two-address

instructions, a variety of addressing modes, several register

classes, variable-length instructions, and instructions with side

effects.
 2. The Target Program

Stack-based machine, operations are done by pushing operands

onto a stack and then performing the operations on the

operands at the top of the stack.

Stack-based architectures were revived with the introduction of

the Java Virtual Machine (JVM).

The JVM is a software interpreter for Java bytecodes, an

intermediate language produced by Java compilers.

 2. The Target Program

Producing an absolute machine-language program as output has

the advantage that it can be placed in a fixed location in

memory and immediately executed.

Producing a relocatable machine-language program (often called

an object module) as output allows subprograms to be compiled

separately.
 2. The Target Program

A set of relocatable object modules can be linked together and

loaded for execution by a linking loader.

If the target machine does not handle relocation automatically, the

compiler must provide explicit relocation information to the

loader to link the separately compiled program modules.

 3. Instruction Selection

The code generator must map the IR program into a code sequence that

can be executed by the target machine.

The complexity of performing this mapping is determined by a factors

such as

the level of the IR

the nature of the instruction-set architecture

the desired quality of the generated code.

 3. Instruction Selection

Instruction speeds and machine idioms are other important

factors.

For example, every three-address statement of the form x = y + z,

where x, y, and z are statically allocated, can be translated into

the code sequence.

3. Instruction Selection
3. Instruction Selection
 3. Instruction Selection

If the target machine has an "increment" instruction (INC), then

the three-address statement a = a + 1 may be implemented more

efficiently by the single instruction INC

 4. Register Allocation

A key problem in code generation is deciding what values to hold

in what registers.

Registers are the fastest computational unit on the target machine,

but we usually do not have enough of them to hold all values.

Instructions involving register operands are invariably shorter

and faster than those involving operands in memory.

 4. Register Allocation

The use of registers is often subdivided into two sub-problems:

1. Register allocation: during which we select the set of variables

that will reside in registers at each point in the program.

2. Register assignment: during which we pick the specific register

that a variable will reside in.

 4. Register Allocation

Finding an optimal assignment of registers to variables is difficult, even

with single-register machines.

Mathematically, the problem is NP-complete.

Certain machines require register-pairs (an even and next odd

numbered register) for some operands and results.

For example, on some machines, integer multiplication and integer

division involve register pairs.

 5. Evaluation Order

The order in which computations are performed can affect the

efficiency of the target code.

Picking the best order in the general case is a difficult NP-

complete problem.
 The Target Language

Our target computer models a three-address machine with

load and store operations,

computation operations,

jump operations, and

conditional jumps.
 1. A Simple Target Machine Model

We assume the following kinds of instructions are available:

Load operations: The instruction LD dst, addr loads the value in

location addr into location dst.

This instruction denotes the assignment dst = addr.

The most common form of this instruction is LD r, x which

loads the value in location x into register r.

 1. A Simple Target Machine Model

Store operations:
The instruction ST x, r stores the value in
register r into the location x.
This instruction denotes the assignment x = r.

LOAD ➔ memory to register

STOR ➔ register to memory
 1. A Simple Target Machine Model

Computation operations of the form OP dst, src1, src2, where OP

is a operator like ADD or SUB, and dst, srcl , and src2 are

locations, not necessarily distinct.

ADD R1, R2, R3 // R1 = R2 + R3

INC X // X = X + 1
 1. A Simple Target Machine Model

Unconditional jumps: The instruction BR L causes control to

branch to the machine instruction with label L. (BR stands for

branch.)

Conditional jumps of the form Bcond r, L, where r is a register, L

is a label, and cond stands for any of the common tests on

values in the register r. BLTZ r, L

 1. A Simple Target Machine Model

We assume our target machine has a variety of addressing modes:

MODE Form Address

(appears in
ALL)
AbsoluteM M M

Register R R R

Indexed C(R) C + Contents (R)

Indirect Register *R Contents(R)

Indirect Index *C(R) Contents (C + Contents (R))

Immediate #C NA
 1. A Simple Target Machine Model

1) Absolute:

MOV a, R0

Contents(a) ➔ R0
 1. A Simple Target Machine Model

2) Register

MOV R0 , a

Contents(R0) ➔ a
 1. A Simple Target Machine Model

3) Indexed C(R) C + Contents (R)

MOV 4(R0), a

Contents (4 + Contents(R0)) ➔ a
 1. A Simple Target Machine Model

4) Indirect Register *R Contents(R)

MOV *R0, a

Contents (Contents (R0)) ➔ a

 1. A Simple Target Machine Model

5) Indirect Index *C(R) Contents (C + Contents (R))

MOV *4(R0), a

Contents (Contents (4+ Contents(R0))) ➔ a

 2. Program and Instruction Costs
Mode Form Address Address
Cost
Absolute M M 1
Register R R 0
Indexed C(R) C+Contents(R) 1
Indirect *R Contents(R) 0
Register
Indirect *C(R) Contents (C + 1
Indexed Contentes(R))
Immediate #C NA 1
 2. Program and Instruction Costs

1 + Cost of source & Destination addressing Mode.

MOV R0 , R1 cost = 1 + 0 + 0

MOV R0, M cost = 1 + 0 + 1

ADD #1, R0 cost = 1 + 1 + 1

SUB 2(R0), * 8 (R1) cost = 1 + 1 + 1

 2. Program and Instruction Costs

A= B + C

A, B, C distinct memory locations

MOV B, R0 cost = 1 + 1 + 0

ADD C, R0 cost = 1 + 1 + 0

MOV R0, A cost = 1 + 0 + 1

MOV B, A
Cost = 2 + 2 + 2 = 6
ADD C, A
 Register Allocation and Assignment
Instructions involving only register operands are faster than

those involving memory operands.

Efficient utilization of registers is vitally important in

generating good code.

In a program, what values should reside in registers (register

allocation) and in which register each value should reside

(register assignment).
 Register Allocation and Assignment

Register allocation and assignment is to assign specific values

in the target program to certain registers.

Decide to assign

base addresses to one group of registers,

arithmetic computations to another,

the top of the stack to a fixed register, and so on….

 1. Global Register Allocation

Registers are used to hold values for the duration of a single

basic block.

All live variables were stored at the end of each block.

Programs spend most of their time in inner loops.

A natural approach to global register assignment is to try to

keep a frequently used value in a fixed register throughout

a loop.
 2. Usage Counts

Assume that the savings to be realized by keeping a

variable x in a register for the duration of a loop L is

one unit of cost for each reference

we count a savings of one for each use of x in loop L that

is not preceded by an assignment to x in the same

block.
 2. Usage Counts

use(x, B) is the number of times x is used in B prior to any

definition of x;

live(x, B) is 1 if x is live on exit from B and is assigned a

value in B, and live(x, B) is 0 otherwise.

2. Usage Counts
 2. Usage Counts

use(a, B1) + 2 * live (a, B1) = 0 + (2 * 1) = 2

use(a, B2) + 2 * live (a, B2) = 1 + (2 * 0) = 1

use(a, B3) + 2 * live (a, B3) = 1 + (2 * 0) = 1

use(a, B4) + 2 * live (a, B4) = 0 + (2 * 0) = 0

Total = 4
 2. Usage Counts

a =4
b=6
c=3
d=6
e=4
f=4
 3. Register Assignment for Outer Loops

If an outer loop L1 contains an inner loop L2, the names

allocated registers in L2 need not be allocated registers

in L1 - L2.

If we choose to allocate x a register in L2 but not L1, we

must load x on entrance to L2 and store x on exit from

L2.
 4. Register Allocation by Graph Coloring

When a register is needed for a computation but all

available registers are in use.

The contents of one of the used registers must be stored

(spilled) into a memory location in order to free up a

register.
 4. Register Allocation by Graph Coloring
Graph coloring is a simple, systematic technique for allocating

registers and managing register spills.

Two passes are used:

Target-machine ➔ instructions are selected

Register-interference graph is constructed in which the nodes are

symbolic registers and an edge connects two nodes if one is live

at a point where the other is defined.

 4. Register Allocation by Graph Coloring

k-coloring of G by assigning n a color not assigned to any

of its neighbors.
 Run-Time Environments

The compiler creates and manages a run-time

environment in which it assumes its target programs

are being executed.

 Run-Time Environments
The environment deals with a variety of issues:

The layout and allocation of storage locations

Mechanisms used by the target program to access variables,

The linkages between procedures,

The mechanisms for passing parameters,

The interfaces to the operating system,

input/output devices, and

other programs.
 Storage Organization

The operating system maps the logical addresses into

physical addresses, which are usually spread

throughout memory.

The run-time representation of an object program in the

logical address space consists of data and program

areas.
Storage Organization
 Storage Organization

The run-time storage comes in blocks of contiguous bytes,

where a byte is the smallest unit of addressable

memory.
 Static Versus Dynamic Storage Allocation
The two adjectives static and dynamic distinguish between

compile time and run time, respectively.

A storage-allocation decision is static, if it can be made by the

compiler looking only at the text of the program, not at

what the program does when it executes.

Conversely, a decision is dynamic if it can be decided only

while the program is running.

 Static Versus Dynamic Storage Allocation

Stack storage: Names local to a procedure are allocated

space on a stack.

The stack supports the normal call/return policy for

procedures.
 Static Versus Dynamic Storage Allocation

Heap storage: Data that may outlive the call to the

procedure that created it is usually allocated on a

"heap" of reusable storage.

To support heap management, "garbage collection"

enables the run-time system to detect useless data

elements and reuse their storage.

 Stack Allocation of Space

void fact(int n)
void main()
{
{ int x // line 1; if(n==0) || (n==1) return 1; // line 4

x=fact(4); // line 2 int x=n; // line 5

int y=fact(n-1)); // line 6

printf(x); // line 3
return x*y; // line 7

} }
Activation:

The execution flow of procedure is called activation.

Activation records:

It contains all necessary information required to call a

procedure.
 Activation Trees

Each time a procedure is called, space for its

local variables is pushed onto a stack, and

when the procedure terminates, that space is

popped off the stack.

Activation Trees
Activation Trees
Activation Trees
 Activation Records

Procedure calls and returns are usually managed by a

run-time stack called the control stack.

Each live activation has an activation record (sometimes

called a frame).
Activation Records
Activation Records
Activation Records
Activation Records
Activation Records
Activation Records
Activation Records – Calling sequence
Consider the following assembly code snippet.
Assume a single-issue processor and the number of instruction cycles for

load➔ 3,
mul ➔ 4,
other instructions ➔ 1

Load I 5 ➔ r1
Load x ➔ r2
Add r1, r2 ➔ r3
Load I 7 ➔ r4
Load y ➔ r5
Mul r4, r5 ➔ T6
Add r3, r6 ➔ r7

(a) Calculate the minimum number of cycles required to execute the following
program in its original instruction order.
(b) Using the List Scheduling approach, perform instruction scheduling and
compute the number of cycles taken to execute the program after instruction
scheduling.
Critical path distance➔
longest distance b/w
instruction & leaf
instruction in the DDG.
Module 7

78
 Parallel Computers
• Parallelism: Doing multiple things at a time
• Things: instructions, operations, tasks
• Main Goal
– Improve performance (Execution time or task
throughput)
• Other Goals
– Reduce power consumption
– Improve cost efficiency and scalability, reduce
complexity
– Improve dependability: Redundant execution in space
81
 Types of Parallelism and How to Exploit Them

• Instruction Level Parallelism

– Different instructions within a stream can be executed in parallel
– Pipelining, out-of-order execution, Dataflow

• Data Parallelism
– Different pieces of data can be operated on in parallel
– Vector processing, array processing

• Task Level Parallelism

– Different “tasks/threads” can be executed in parallel
– Multithreading
– Multiprocessing (multi-core)
82
 Task-Level Parallelism: Creating Tasks
• Partition a single problem into multiple related tasks
(threads)
– Explicitly: Parallel programming
• Easy when tasks are natural in the problem
– Web/database queries

• Difficult when natural task boundaries are unclear

– Transparently/implicitly: Thread level speculation

• Partition a single thread speculatively

• Run many independent tasks (processes) together

– Easy when there are many processes
• Batch simulations, different users, cloud computing workloads

– Does not improve the performance of a single task

83
FLYNN’S TAXONOMY – OVERVIEW

• Proposed by Michael Flynn (1966)

• Classifies systems by instruction/data streams

• Four types: SISD, SIMD, MISD, MIMD

• Defines basic models of parallel processing

• Still widely referenced today

SISD – SINGLE INSTRUCTION, SINGLE DATA

• Traditional sequential processing

• One instruction operates on one data unit

• No parallelism

• Simple architecture (e.g., early CPUs)

• Limited performance for modern needs

SIMD – SINGLE INSTRUCTION, MULTIPLE DATA

• Same instruction on multiple data

simultaneously

• Efficient for data-parallel tasks

• Ideal for image/audio/video processing

• Examples: GPUs, Intel AVX/SSE

MISD – MULTIPLE INSTRUCTIONS, SINGLE DATA

• Multiple instructions on the same data stream

• Rarely implemented in practice

• Useful for redundancy and fault tolerance

• Mostly theoretical model

• Limited real-world applications

MIMD – MULTIPLE INSTRUCTIONS, MULTIPLE DATA

• Independent processors execute different instructions

• Supports both data and task parallelism

• Scalable and flexible architecture

• Common in multicore CPUs and clusters

• Used in general-purpose and supercomputing

 SHARED VS. DISTRIBUTED MEMORY

Shared Memory: Distributed Memory:

• All processors access a global memory • Each processor has its own local
memory
• Easy to program using threads
• Communication via message passing
• Risk of data races and contention • High scalability

• Fast communication but limited • Complex programming (e.g., MPI)

• Example: Cluster computing
scalability

• Example: SMP systems

Automatic Parallelization

94
• Automatic parallelization, also auto parallelization, or auto
parallelization refers to converting sequential code into multi-
threaded and/or vectorized code in order to use multiple
processors simultaneously in a shared-memory multiprocessor
(SMP) machine.
• Automatic parallelization technique
– Parse
– Analyze
– Schedule
– Code Generation

95
 void loop_test(int u) { #pragma loop(hint_parallel(8))
for (int i=0; i<u; ++i) for (int i=0; i<upper_bound(); ++i)
A[i] = B[i] * C[i]; A[i] = B[i] * C[i];

}
The function upper_bound() might change every time
If u could be a small value, the
it's called. Because the upper bound cannot be known,
compiler won't automatically
parallelize this loop. the compiler can emit a diagnostic message that
explains why it can't parallelize this loop. The
following example demonstrates a loop that can be
parallelized, a loop that cannot be parallelized, the
compiler syntax to use at the command prompt, and
the compiler output for each command line option:

96
Optimizations for cache locality and
vectorization

97
 Optimizations for cache locality
• Optimizations for cache locality and vectorization
are crucial for improving the performance of
programs, especially in modern computing
architectures where memory access and data
parallelism play significant roles.
• Some common techniques used by compilers to
optimize for cache locality and vectorization:

98
• Loop Tiling/Blocking: This technique divides large loops into smaller
blocks that fit into the cache more efficiently. By processing data in smaller
chunks, it reduces cache misses and enhances cache locality.

99
• Loop Interchange: Reordering loop nests to improve spatial
locality, ensuring that consecutive memory accesses are more
likely to access nearby memory locations.
• Loop Unrolling: This optimization technique duplicates loop
bodies to reduce loop overhead and expose more opportunities
for instruction-level parallelism and vectorization.

100
• Data Alignment: Aligning data structures and arrays to
cache line boundaries ensures that data elements are
fetched in optimal-sized chunks, reducing memory
access latency.
• Prefetching: Compiler-generated or hardware-assisted
prefetching techniques can be employed to bring data
into the cache before it is actually accessed by the
program, reducing cache misses.

101
 Vectorization
• vectorization, in parallel computing, is a special
case of automatic parallelization, where a
computer program is converted from a scalar
implementation, which processes a single pair of
operands at a time, to a vector implementation,
which processes one operation on multiple pairs
of operands at once.

102
 Vectorization

• Exploiting SIMD (Single Instruction, Multiple Data) instructions

to perform parallel computations on multiple data elements
simultaneously. This can significantly enhance performance by
reducing the number of instructions executed per data element.
• Compilers automatically detect opportunities for vectorization
and generate SIMD instructions when appropriate. This can be
augmented by providing hints to the compiler through attributes.

103
• For example, modern conventional computers, including
specialized supercomputers, typically have vector operations that
simultaneously perform operations such as the following four additions
(via SIMD hardware):

Here is an example of such a loop, written in C:

• A vectorizing compiler transforms such loops into sequences of vector operations.
• These vector operations perform additions on blocks of elements from the arrays a,
b and c.

104
Software Pipelining

106
107
108
109
110
111
In every clock cycle, it can initiate
new cycle.

112
Effective Initial interval ➔ 1

113
114
115
116
117
118