UNIT 4 – INTERMEDIATE CODE GENERATION AND RUNTIME ENVIRONMENTS
4.1 PREPROCESSING THE INTERMEDIATE CODE
Intermediate code is the form between the high-level source code and the machine code. It helps make
the compiler modular, portable, and optimizable.
Definition:
Preprocessing intermediate code means transforming or optimizing intermediate code before code
generation to make later stages more efficient.
Key Concepts:
1. Intermediate Code Generation:
2. Generated after parsing.
3. Platform-independent.
4. Forms include:
◦ Three Address Code (TAC)
◦ Abstract Syntax Tree (AST)
◦ Control Flow Graph (CFG)
5. Techniques Used:
6. Simplification: Remove unnecessary operations.
7. Common Subexpression Elimination (CSE): Avoid repeated expressions.
8. Constant Folding: Evaluate constant expressions at compile time.
9. Constant Propagation: Replace variable with constant value.
10. Dead Code Elimination: Remove code that never executes.
11. Strength Reduction: Replace costly operations (like * or /) with cheaper ones (like + or bit shifts).
12. Loop Invariant Code Motion: Move computations outside loops.
13. Why Preprocess?
14. Simplifies code generation.
15. Improves efficiency and optimization.
16. Reduces execution time and memory.
Example:
int a = 5, b = 10;
int c = a*b + 2*a;
Intermediate Code:
1
t1 = a * b
t2 = 2 * a
t3 = t1 + t2
c = t3
After Preprocessing:
c = 60
4.2 PREPROCESSING OF EXPRESSIONS
Preprocessing expressions means simplifying or optimizing mathematical and logical expressions
before optimization or code generation.
Why Preprocess?
• Reduce redundant computations.
• Simplify code structure.
• Improve speed and memory efficiency.
Techniques:
1. Constant Folding – Evaluate constants at compile time.
2. Constant Propagation – Replace variable with known constant.
3. Simplification – Apply identity rules (x*1=x, x+0=x, etc.).
4. Common Subexpression Elimination (CSE) – Reuse computed results.
5. Dead Code Elimination – Remove unused expressions.
6. Strength Reduction – Replace costly ops (×, ÷) with cheaper ops (<<, >>).
7. Loop Invariant Code Motion – Move fixed computations out of loops.
Example:
a = 5;
b = a * 3; → b = 15;
4.3 PREPROCESSING OF IF AND GOTO STATEMENTS
Control statements (if/goto) affect how execution flows. Preprocessing simplifies them.
For IF Statements:
1. Constant Folding: Evaluate conditions like (5>10) at compile time.
2. Constant Propagation: Replace variables with known constants.
3. Dead Code Elimination: Remove blocks that will never execute.
4. Simplify Nested IFs: Merge or simplify where possible.
2
For GOTO Statements:
1. Remove unnecessary GOTO.
2. Convert GOTO to structured loops (while/for).
3. Remove unreachable code after GOTO.
4. Simplify or hoist GOTOs when possible.
4.4 PREPROCESSING OF ROUTINES (FUNCTIONS)
Preprocessing routines = optimizing functions before code generation.
Techniques:
1. Inlining: Replace function calls with actual function body.
2. Function Call Simplification: Replace constant-returning functions with direct values.
3. Tail Call Optimization: Reuse stack for recursive calls.
4. Dead Routine Elimination: Remove unused functions.
5. Parameter Passing Optimization: Simplify parameter handling.
6. Recursion Preprocessing: Convert recursion to iteration.
7. Library Function Inlining: Inline frequently used small library functions.
Example:
int add(int a, int b) { return a+b; }
result = add(2,3); → result = 2+3;
4.5 VARIANTS OF SYNTAX TREES
Syntax trees represent program structure. There are different types based on compiler phase.
1. Abstract Syntax Tree (AST):
• Simplified tree (no parentheses).
• Focus on logic and meaning.
Example for a+(b*c) :
+
/
a *
/
b c
3
2. Concrete Syntax Tree (CST):
• Full parse tree with all grammar details.
• Used by the parser.
3. Syntax Directed Translation Tree (SDT):
• AST with semantic actions (like code generation hints).
4. Control Flow Graph (CFG):
• Represents flow between basic blocks.
• Used for optimization and loop analysis.
5. Intermediate Representation (IR) Tree:
• Closer to machine code.
• Used in optimization and backend phases.
4.6 THREE ADDRESS CODE (TAC)
TAC is an intermediate representation where each statement has ≤3 operands.
Format:
x = y op z
Example:
a = b + c * d
TAC:
t1 = c * d
t2 = b + t1
a = t2
Benefits:
• Easy for optimization.
• Machine-independent.
• Simplifies translation.
4
4.7 BOOLEAN EXPRESSIONS IN TAC
Boolean expressions are translated using temporary variables.
Example:
a = (b AND c) OR (d AND e)
TAC:
t1 = b AND c
t2 = d AND e
a = t1 OR t2
Operators handled: - AND → t1 = x AND y - OR → t1 = x OR y - NOT → t1 = NOT x - XOR →
t1 = x XOR y
4.8 FLOW-OF-CONTROL STATEMENTS IN TAC
Used to handle program flow: IF, GOTO, WHILE, FOR, BREAK, CONTINUE.
Conditional Jump:
if a > b goto L1
x = 20
goto L2
L1: x = 10
L2:
Loop Example:
L1: if a >= b goto L2
a = a + 1
goto L1
L2:
Break / Continue:
Break → goto ExitLabel Continue → goto StartLabel
4.9 CONTROL FLOW TRANSLATION OF BOOLEAN EXPRESSIONS
Boolean expressions are converted into if-goto style control flow.
5
Examples:
A AND B:
if A == 0 goto L1
if B == 0 goto L1
// True path
L1:
A OR B:
if A != 0 goto L1
if B != 0 goto L1
goto L2
L1:
// True block
L2:
NOT A:
if A != 0 goto L1
// Code for NOT A
L1:
Short-Circuiting: Stop evaluating once result known → improves efficiency.
4.10 RUNTIME ENVIRONMENTS
Definition:
Runtime environment = memory + structures used during program execution.
It includes: - Stack - Heap - Data segment - Code segment
Memory Layout:
Segment Description
Code Segment Program instructions
Data Segment Global & static variables
Stack Segment Local vars, parameters
Heap Segment Dynamically allocated memory
6
Static vs Dynamic Allocation:
• Static: fixed size at compile time
• Dynamic: created/deleted during runtime
Stack vs Heap:
Stack Heap
Fast, automatic Slower, manual
Temporary vars Persistent vars
LIFO structure Random access
4.10.2 STACK ALLOCATION OF SPACE
Stack is used for local variables and function calls.
Features:
• Follows LIFO order.
• Automatically allocates/deallocates memory.
• Each function call → creates activation record (stack frame).
Activation Record Contains:
Part Description
Return Address Where to return after function call
Parameters Arguments passed
Local Variables Declared inside function
Saved Registers For context switching
Advantages:
• Fast and automatic
• No fragmentation
• Memory freed automatically
Disadvantages:
• Limited size
• Variables live only till function runs
7
4.10.3 ACCESS TO NONLOCAL DATA ON THE STACK
Nonlocal data = variables not local to current function.
Types:
1. Caller’s local variables
2. Global variables
3. Static variables
Access Methods:
1. Caller’s Locals: Use frame pointer (FP) to reach caller’s frame.
2. Global Variables: Accessed directly from data segment.
3. Static Variables: Stored in static memory, persist across calls.
Example:
int global = 42;
void funcA() {
int x = 10;
funcB(x);
}
void funcB(int y) {
printf("%d %d", y, global);
}
- x passed via stack (caller’s data) - global accessed directly (global data)
✅ Overall Summary of UNIT 4:
• Intermediate code generation simplifies compilation.
• Preprocessing improves performance.
• TAC is central to compiler intermediate representation.
• Boolean & control statements translated using labels and jumps.
• Runtime environment manages program memory efficiently with stack & heap.