Symbol Table

Definition:
A symbol table is a data structure maintained by the compiler to store all identifiers’ names
along with their type, scope, size, and other relevant attributes. It facilitates smooth compiler
operations by allowing quick lookups during compilation.

Purpose:

 Tracks variables, arrays, records, procedures, and functions across the program.
 Provides information required by all phases of the compiler.

Information Stored in Symbol Table:

1. Name of the identifier

2. Type (int, float, char, etc.)
3. Scope (local, global)
4. Size (memory required)
5. Offset (location relative to memory frame)
6. Array size (if applicable)
7. Record/column size
8. Input/output information (actual/formal parameters)

Interaction with Compiler Phases:

 Front-end: Fills the symbol table during analysis.

 Back-end: Uses the symbol table for efficient code generation (synthesis).

Example Table Layout:

Line No. Keyword Identifier Constant Operator

1 int x 10 ;

Data Structures for Symbol Table Implementation

1. Linked List
o Each entry points to the next; stored in non-contiguous memory.
o Structure: Head → [E1] → [E2] → [E3] → null

Advantages:

o Simple to implement
o Suitable for small programs
o Used in one-pass compilers
 Disadvantages:

oSlow lookup (O(n))

oInefficient for large tables
2. Hash Table
o Stores entries in buckets using a hash function that converts symbol names to
indexes.
o Collision handling: Chaining or open addressing

Advantages:

o Very fast lookup (O(1) average)

o Efficient for large programs
o Used in GCC, Clang

Disadvantages:

oCollisions require handling

oComplex implementation
3. Binary Search Tree (BST)
o Identifiers are stored in sorted order: left child < parent < right child
o Lookup, insert, delete: O(log n) average

Advantages:

o Ordered traversal possible

o Efficient lookup (if balanced)

Disadvantages:

o Worst case O(n)

o Harder to implement than hash table

Operations on Symbol Table:

1. Insert: Add new identifiers

2. Lookup/Search: Retrieve information
3. Modify: Update existing entries
4. Delete: Remove an identifier

Error Analysis
Definition:
Any failure occurring in any phase of compilation is an error. Error analysis ensures
compilation continues despite errors, allowing programmers to correct them.
Classification:

1. Compile-Time Errors:

 Lexical Errors: Invalid sequences of characters (e.g., spelling mistakes, invalid numeric
constants).
 Syntax Errors: Violation of grammar rules (e.g., missing semicolons, unbalanced
parentheses).
 Semantic Errors: Meaning errors detected after parsing (e.g., type mismatch, undeclared
variables).

2. Run-Time Errors:

 Exceptions
 Fatal errors

Examples & Recovery Techniques:

 Lexical Errors:
 x = 9a; // invalid token

Recovery: Skip symbols until delimiter, insert/delete characters.

 Syntax Errors:
 if (x = y) printf("Hi"); // should be ==

Recovery: Issue warning, suggest corrections.

 Semantic Errors:
 int x = "HELLO"; // type mismatch
 printf("%d", y); // undeclared

Recovery: Skip erroneous line, continue compilation.

Code Optimization Techniques

Purpose: Improve intermediate code to make object code faster, smaller, and efficient without
changing semantics.

1. Constant Folding

 Evaluate constant expressions at compile time.

 Example: x = a + b + 2*3 + 4 → x = a + b + 10
Advantages: Reduces runtime operations, CPU time, enables further optimization.
Limitation: Only for compile-time constants.

2. Constant Propagation

 Substitute known constant values in expressions.

 Example: pi = 3.1415; x = 360/pi; → x = 360/3.1415

3. Strength Reduction

 Replace expensive operations with cheaper equivalents.

 Example: y = 2*x → y = x + x, x/2 → x >> 1

4. Algebraic Simplification

 Apply mathematical identities to simplify code.

 Examples:
o a*b*1 → a*b
o x*0 → 0

5. Common Subexpression Elimination (CSE)

 Compute repeated expressions once and reuse.

 Example: x = a+b; y = b+a; → x = a+b; y = x;

6. Loop Optimization

1. Loop Fusion

Definition:
Loop fusion is the process of combining two or more loops that iterate over the same range into a
single loop. This reduces loop overhead and may improve cache performance.

Example:

Before loop fusion:

for (int i = 0; i < n; i++) {

a[i] = b[i] + 1;
}

for (int i = 0; i < n; i++) {

c[i] = d[i] * 2;
}

After loop fusion:

for (int i = 0; i < n; i++) {
a[i] = b[i] + 1;
c[i] = d[i] * 2;
}

Advantages:

 Fewer loop control instructions.

 Better cache locality.

2. Loop Unrolling

Definition:
Loop unrolling replicates the loop body multiple times to reduce the number of iterations. This
decreases loop overhead (like incrementing counters and checking conditions) and can improve
performance, especially in compute-heavy loops.

Example:

Original loop:

for (int i = 0; i < 8; i++) {

a[i] = a[i] * 2;
}

Unrolled loop (factor of 2):

for (int i = 0; i < 8; i += 2) {

a[i] = a[i] * 2;
a[i+1] = a[i+1] * 2;
}

Advantages:

 Reduces the number of iterations.

 Can enable better instruction-level parallelism.

3. Loop-Invariant Code Motion (Code Motion)

Definition:
Loop-invariant code motion is a technique where computations that do not change within a loop
are moved outside the loop. This avoids repeated calculations and improves performance.

Key Idea:
If an expression inside a loop produces the same result in every iteration, compute it once before
the loop instead of in every iteration.

Example:
Original code:

for (int i = 0; i < n; i++) {

y[i] = x[i] * (a + b);
}

Here, (a + b) does not change during the loop.

Optimized using loop-invariant code motion:

int temp = a + b; // Moved outside the loop

for (int i = 0; i < n; i++) {
y[i] = x[i] * temp;
}

Advantages:

 Reduces redundant computations.

 Improves runtime, especially for expensive operations like function calls or complex
arithmetic.

Another example with function calls:

Original code:

for (int i = 0; i < n; i++) {

arr[i] = sin(PI/4) * values[i];
}

Optimized:

double factor = sin(PI/4); // Computed once

for (int i = 0; i < n; i++) {
arr[i] = factor * values[i];
}

7. Dead Code Elimination

 Remove statements that do not affect output.

 Example: x=5; x=10; → remove x=5

Q. What is a basic block?

A basic block is a sequence of consecutive statements in a program where:

 Control enters only at the beginning, and

 Control leaves only at the end, without any jump or halt in between.
In simple terms, it is a straight-line code sequence with no branches except at the entry and exit
points.

How to Identify Basic Blocks?

To form basic blocks, leaders (starting points of blocks) must be identified.

Rules for Leaders:

1. The first statement of the program is a leader.

2. Any statement that is the target of a jump (label) is a leader.
3. Any statement immediately following a jump or branch is a leader.

DAG (Directed Acyclic Graph) Representation of Basic Blocks

A DAG (Directed Acyclic Graph) represents the computations within a basic block.

It helps the compiler identify:

 Common subexpressions
 Dead code
 Order of evaluation
 Optimizable operations

Structure of a DAG:

 Leaves (terminal nodes) represent operands/variables/constants.

 Interior nodes represent operators.
 Edges connect operands to operations.

Q. Draw a Directed Acyclic Graph:

i. ((a+a)+(a+a))+ ((a+a)+(a+a))
Peephole Optimization
Definition

Peephole optimization is a local code optimization technique applied in the final phases of a
compiler, typically after generating intermediate or target code. It involves examining a small
sequence (window) of consecutive instructions, called a "peephole," and replacing inefficient
or redundant patterns with optimized equivalents.

The term “peephole” reflects the small size of the instruction window examined at one time,
usually 3 to 15 instructions. By focusing on a narrow portion of code, the compiler can apply
target-specific improvements efficiently without analyzing the entire program.

Objectives of Peephole Optimization

The main goals are:

1. Produce shorter and faster code – reduce code size and execution time.
2. Remove redundant operations – eliminate unnecessary instructions that do not affect
program behavior.
3. Simplify instruction sequences – make sequences of instructions more efficient while
maintaining correctness.
4. Reduce memory and register usage – minimize loads, stores, and temporary variable
usage.
5. Perform machine-dependent optimizations – improve performance based on specific
architecture features.

Characteristics of Peephole Optimization

1. Local Scope
o Operates only on a small section of code at a time (the peephole).
o Does not analyze the entire program, only the instructions inside the window.
o Typical peephole size: 3–15 instructions.
2. Pattern Matching
o Uses predefined patterns of inefficient code sequences.
o Scans the code inside the peephole window to detect matches.
o When a match is found, it is replaced with a more efficient sequence.
3. Code Transformation
o Substitutes inefficient code fragments with optimized instructions.
o Ensures program semantics are preserved while improving performance.
o Example: Replace a redundant load-store sequence with a single instruction.
4. Iterative Process
o Optimization is typically performed in multiple passes.
o After each pass, the peephole slides forward and rescans the code.
o Continues until no further transformations are possible.
Common Types of Peephole Optimizations

1. Redundant Load/Store Elimination

Removes unnecessary memory operations.
2. MOV R1, A
3. MOV A, R1 ; redundant if A is unchanged

Optimized:

MOV R1, A

4. Constant Folding
Evaluates constant expressions at compile time instead of runtime.
5. MOV R1, #5
6. MOV R2, #3
7. ADD R3, R1, R2

Optimized:

MOV R3, #8

8. Strength Reduction
Replaces expensive operations with cheaper equivalents.
9. MUL R1, R2, #8

Optimized:

SHL R1, R2, #3 ; left shift by 3 is equivalent to multiply by 8

10. Dead Code Elimination

Removes instructions that do not affect the program’s output.
11. MOV R1, #5
12. MOV R1, #6 ; overwrites previous value

Optimized:

MOV R1, #6

13. Control Flow / Branch Optimization

Simplifies jumps and conditional branches.
14. JMP L1
15. L1: JMP L2 ; redundant jump

Optimized:

JMP L2

Conditional branch example:

 CMP R1, #0
JE L1
JMP L2

Optimized:

JNE L2

16. Register Usage Optimization

Reduces unnecessary load/store operations with registers.
17. MOV R1, A
18. MOV A, R1
19. MOV R2, A

Optimized:

MOV R1, A
MOV R2, R1

20. Algebraic Simplification

Eliminates operations with neutral elements (0 or 1).
21. ADD R1, R1, #0 ; R1 = R1 + 0
22. MUL R2, R2, #1 ; R2 = R2 * 1

Optimized: remove both instructions.

Working of Peephole Optimization

1. Input: Object code or intermediate code from the compiler.

2. Select a small peephole window of consecutive instructions.
3. Compare instructions against known inefficient patterns.
4. If a match is found, replace the sequence with optimized instructions.
5. Slide the peephole forward and repeat the process.
6. Iterate until no further patterns can be applied.

Advantages of Peephole Optimization

 Produces compact and efficient code.

 Easy to implement as a post-pass optimization.
 Works independently of high-level language constructs.
 Improves performance without altering program semantics.
 Can be applied iteratively for incremental improvements.

Limitations

1. Limited Scope: Only detects inefficiencies in a small window; cannot optimize across
multiple functions or large code regions.
 2. Architecture Dependence: Some optimizations are machine-specific and may need
adjustments for different CPUs.
3. Increased Compilation Time: Multiple passes and repeated scanning may slow
compilation.
4. Redundant Transformations: If not carefully ordered, some optimizations can cancel
each other out or be applied unnecessarily.

Register Allocation and Assignment

Registers are the fastest storage locations in a CPU, and using them efficiently can
significantly improve program performance. However, registers are limited, so the compiler
must carefully manage which variables and intermediate values are stored in registers at any
given time.

This process consists of two main steps:

1. Register Allocation – deciding which variables should go into registers.

2. Register Assignment – mapping these variables to specific physical registers.

1. Register Allocation

Definition:
Register allocation is the process of assigning a limited number of CPU registers to program
variables to minimize memory accesses and maximize runtime efficiency.

Registers are typically used for:

 Frequently accessed variables

 Intermediate results in expressions
 Loop counters or indices

Types of Register Allocation

(a) Local Register Allocation

 Done within a single basic block (a straight-line sequence of instructions with no

branches).
 Simpler, but may cause redundant load/store instructions when moving across blocks.

Methods used:

 Graph coloring within the block

 Linear scan for short sequences

Example:
A basic block has variables a, b, c and only 2 registers are available.
  The compiler may allocate registers to a and b, while c is stored in memory temporarily.

(b) Global Register Allocation

 Considers the entire control flow graph (CFG) of a function or program.

 Takes into account variable lifetimes across multiple basic blocks.
 May involve:
o Interprocedural analysis (across functions)
o Spilling variables to memory when registers are full

Goal: Reduce the number of loads and stores between blocks.

Strategies for Register Allocation

1. Graph Coloring Technique

o Represent interference between variables using an interference graph:
 Node = variable
 Edge = two variables are live at the same time (cannot share a register)
o Register assignment = graph coloring problem
 Each color = one register
 Adjacent nodes must have different colors

Example:
If variables a and b are live simultaneously, an edge is drawn between them → they require
different registers.

Algorithm used:

 Chaitin’s Graph Coloring Algorithm (classical approach)

2. Spilling
o Occurs when the number of live variables exceeds the available registers.
o Some variables are moved (“spilled”) to main memory (stack) temporarily.
o Compiler decides:
 Which variable(s) to spill (usually least frequently used)
 Insert load and store instructions as needed

Example:

 4 registers available, 6 variables live

 Compiler spills 2 least-used variables to memory temporarily

2. Register Assignment

Definition:
After deciding which variables go into registers, the compiler assigns specific physical registers
to them. This mapping from symbolic (virtual) registers to actual machine registers is called
register assignment.

Types of Register Assignment

(a) Static Register Assignment

 Done at compile time

 Common in RISC architectures with fixed register roles (e.g., R1 for return values, R2 for
counters)

Advantages:

 Simple and deterministic

Disadvantages:

 Less flexible; cannot adapt to runtime variations

(b) Dynamic Register Assignment

 Performed at runtime, often by a Just-In-Time (JIT) compiler

 Useful where runtime behavior is unpredictable (e.g., Java Virtual Machine)

Example:

 A JIT compiler may assign “hot” variables to registers dynamically during execution

Advantages:

 Adaptable to runtime patterns

 Optimizes execution based on actual usage

Disadvantages:

 Adds runtime overhead and complexity

Live Range Analysis

 Determines the section of code where each variable is “alive” or needed

 Helps the compiler know when a register can be reused
 Critical for both local and global allocation

Importance of Register Allocation

 Aspect Impact

Execution Speed Fewer memory accesses → faster execu on

Memory Efficiency Reduced load/store instructions → less stack traffic

Pipeline Utilization Better instruction flow → fewer pipeline stalls

Power Consumption Fewer memory operations → reduced power usage

Summary

 Register Allocation decides which variables go into registers.

 Register Assignment maps these variables to specific physical registers.
 Strategies include graph coloring and spilling for allocation, and static vs dynamic
assignment for register mapping.
 Efficient register management improves speed, memory usage, and CPU pipeline
performance while reducing power consumption.

Code Generation
Definition:
Code generation is the compiler phase that converts optimized intermediate code into target
code (machine code or assembly).

Even though sometimes listed as “issues,” the points you mentioned are actually tasks or
considerations in code generation.

Key Considerations in Code Generation

1. Input to Code Generator:

o Intermediate code from the front-end compiler
o Symbol table info (type, scope, memory location)
2. Target Program:
o Output can be:
 Assembly language
 Relocatable machine code (can move in memory)
 Absolute machine code (fixed memory locations)
3. Memory Management:
o Assign addresses to instructions and variables
o Keep track of memory efficiently
4. Instruction Selection:
o Choose the correct machine instructions for operations
o Optimize the order of instructions
 5. Register Allocation:
o Decide which variables go into registers (limited number of fast CPU registers)
o Two steps:
1. Register Allocation – choose the set of variables to keep in registers
2. Register Assignment – assign specific registers to variables
6. Evaluation Order:
o Determine the order of executing instructions to respect operator precedence and
dependencies

Simple Code Generation Example

We are solving:

[
X = (a + b) - (c + d - e)
]

We will use a hypothetical getreg() function which returns a free register, e.g., R1, R2, etc.

Step 1: Break the expression into sub-expressions

1. t1 = a + b
2. t2 = c + d
3. t3 = t2 - e
4. X = t1 - t3

Step 2: Generate code using getreg()

Assume we have LOAD and ADD/SUB instructions:

R1 = getreg() ; Get register for t1

MOV R1, a ; Load a into R1
ADD R1, b ; R1 = a + b (t1)

R2 = getreg() ; Get register for t2

MOV R2, c ; Load c into R2
ADD R2, d ; R2 = c + d (t2)
SUB R2, e ; R2 = t2 - e (t3)

SUB R1, R2 ; t1 - t3
MOV X, R1 ; Store result into X

Step 3: Explanation

 Registers: R1 for left-hand side (a+b), R2 for right-hand side (c+d-e)

 Operations order: We calculate inner parentheses first
 Final subtraction: t1 - t3
  Store result: Move from register to memory variable X

This is exactly how a simple code generator works step by step using registers and evaluation
order.