UNIT 5: CODE GENERATION

Ques 1) what is Code Optimization? Describe its role in the compilation

process and provide example of common optimization techniques.

Definition:
Code optimization is a phase in the compilation process where the compiler tries to improve
the intermediate code so that the final output code is efficient in terms of execution time
and/or memory usage, without altering the functionality of the program.

Role in the Compilation Process:

The compilation process consists of several stages:

1. Lexical Analysis
2. Syntax Analysis
3. Semantic Analysis
4. Intermediate Code Generation
5. Code Optimization ← (This stage)
6. Code Generation
7. Linking and Loading

In the code optimization phase, the compiler takes the intermediate representation (IR) of
the source program and applies various transformations to produce a more optimized
version. This optimized IR is then translated into machine code during code generation.

Objectives of Code Optimization:

 To reduce execution time of the program

 To minimize memory usage
 To improve performance on the target hardware
 To avoid redundant calculations
 To generate efficient machine-level instructions

Common Code Optimization Techniques:

1. Constant Folding:
o Evaluates constant expressions at compile-time.
o Example:
o int x = 3 * 4; // Optimized to: int x = 12;
2. Dead Code Elimination:
o Removes code statements that do not affect the program result.
o Example:
o int x = 10;
o x = 20; // 'x = 10' is dead code and can be removed
3. Loop Optimization:
o Improves efficiency of loops.
o Types:
 Loop Invariant Code Motion: Move code that doesn’t change within
the loop to outside.
  Loop Unrolling: Reduce the overhead of loop control.
o Example:
o for(int i = 0; i < 10; i++) {
o int x = a * b; // invariant expression
o }

becomes:

int x = a * b;
for(int i = 0; i < 10; i++) {
// use x
}

4. Strength Reduction:
o Replaces costly operations with cheaper equivalents.
o Example:
o x = y * 2; // Replaced by: x = y + y;
5. Common Subexpression Elimination:
o Reuses the result of a previously computed expression.
o Example:
o int a = b * c + d;
o int e = b * c + f;

becomes:

temp = b * c;
int a = temp + d;
int e = temp + f;

6. Peephole Optimization:
o Performs small, localized improvements in machine code.
o Example:
o MOV R1, R2
o MOV R2, R1

→ Can be simplified or removed.

Ques 2) Explain different code generation techniques with benefit and example.

Definition:
Code generation is the process of converting the intermediate representation (IR) of the
source code into target machine code (assembly or binary). The main goal is to generate
efficient, correct, and optimized code that executes well on the target hardware.

1. Loop Optimization

Description:
Loop optimization improves the performance of programs by optimizing the way loops are
written or executed. Since loops are repeated many times, optimizing them can significantly
impact the overall performance.

Common Types:
  Loop Invariant Code Motion: Moves computations that do not change inside the
loop, outside of it.
 Loop Unrolling: Expands the loop body to reduce the number of iterations and loop
control instructions.

Example (Loop Invariant Code Motion):

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

int x = a * b; // Doesn't depend on 'i'
arr[i] = x + i;
}

Optimized To:

int x = a * b;
for(int i = 0; i < 10; i++) {
arr[i] = x + i;
}

Benefits:

 Reduces redundant computations

 Enhances execution speed
 Saves CPU cycles

2. Use of Register Principle

Description:
Registers are the fastest storage in a CPU. This technique tries to store frequently accessed
variables in registers instead of memory for faster access.

Strategy:

 Allocate high-priority variables (used often or in loops) to CPU registers.

 Use register allocation algorithms (like graph coloring).

Example:

int a = b + c;
int d = a + e;

Generated Assembly (using registers):

MOV R1, b
ADD R1, c ; R1 = a
MOV R2, R1
ADD R2, e ; R2 = d

Benefits:

 Faster execution due to register access

 Reduces memory access latency
3. Stack Allocation

Description:
Stack allocation is used to manage memory for function calls, local variables, parameters,
and return addresses using a LIFO (Last-In-First-Out) structure called the stack.

How it works:

 Every function call creates a stack frame.

 Parameters, return address, and local variables are pushed into the stack.
 When function returns, the stack is popped and cleaned.

Example (C Code):

int sum(int a, int b) {

int result = a + b;
return result;
}

Conceptual Stack:

| return address |
| value of b |
| value of a |
| local var |

Benefits:

 Supports recursion
 Provides memory isolation for each function call
 Efficient space management

4. Instruction Selection

Description:
This technique selects the most efficient machine instruction for a given intermediate
operation based on the target architecture.

Example:
Instead of:

x = y * 2;

The compiler may generate:

SHL x, y, 1 ; Shift Left is faster than Multiply

Benefits:

 Generates hardware-optimized instructions

  Improves execution speed

5. Instruction Scheduling

Description:
Instruction scheduling reorders the machine instructions to reduce stalls or delays due to
hardware issues like pipeline hazards or data dependency.

Example:
If instruction A depends on the result of instruction B, the compiler can insert independent
instructions in between to avoid waiting cycles.

Benefits:

 Maximizes CPU pipeline usage

 Avoids pipeline stalls and increases throughput

6. Address Calculation Optimization

Description:
This technique optimizes complex address calculations, especially in arrays and pointer
arithmetic, to reduce overhead during memory access.

Example:
Accessing an array element:

a[i][j] = x;

Instead of calculating the address again and again, the compiler computes a base address and
applies offset efficiently.

Optimized Form:

address = base + i*row_size + j;

Benefits:

 Reduces number of arithmetic operations

 Speeds up memory access in data structures

Ques 3) Explain the code generation for control flow statement in compiler.
Control flow statements like if, if-else, while, for, and switch allow a program to alter its
execution path based on conditions. In the code generation phase of a compiler, these high-
level constructs are converted into low-level instructions, typically using labels and jump
statements (conditional or unconditional). The goal is to preserve the logic and flow of the
original program in the target machine or assembly code.

Basic Elements Used in Control Flow Code Generation:

 1. Labels – Used to mark positions in the code for jumps.
2. Conditional Jumps (CJUMP) – Execute a jump only if a condition is true or false.
3. Unconditional Jumps (JUMP) – Always execute the jump regardless of condition.
4. Comparison Operations – Used to evaluate conditions like a < b, x == y, etc.

1. If Statement

High-Level Code:

if (condition) {
statement;
}

Generated Code:

Evaluate condition
CJUMP_FALSE L1 ; If condition is false, jump to label L1
statement ; Code block if condition is true
L1: Label after the if-block

Explanation:

 The condition is evaluated.

 If it’s false, the control jumps to L1, skipping the statement.
 If true, it executes statement.

2. If-Else Statement

High-Level Code:

if (condition) {
statement1;
} else {
statement2;
}

Generated Code:

Evaluate condition
CJUMP_FALSE L1 ; If false, go to else block
statement1 ; Executed if condition is true
JUMP L2 ; Jump to end
L1:
statement2 ; Else block
L2: End of if-else

Explanation:

 One label (L1) for the else-block.

 One label (L2) for the exit point.
 Prevents both blocks from executing together.

3. While Loop
High-Level Code:

while (condition) {
body;
}

Generated Code:

L1: Evaluate condition

CJUMP_FALSE L2 ; Exit loop if condition is false
body ; Loop body
JUMP L1 ; Repeat the loop
L2: Exit point after loop

Explanation:

 The loop condition is tested before entering the body.

 If false, jumps to the end label (L2).
 If true, executes the body and loops back to L1.

4. For Loop

High-Level Code:

for (init; condition; increment) {

body;
}

Generated Code:

init
L1: Evaluate condition
CJUMP_FALSE L2
body
increment
JUMP L1
L2:

Explanation:

 Initialization happens once before the loop.

 Loop condition is checked at the beginning of every iteration.
 Increments after the loop body, then jumps back to condition check.

5. Switch Statement

High-Level Code:

switch (expr) {
case 1: statement1; break;
case 2: statement2; break;
default: statement3;
 }

Generated Code:

Evaluate expr → R
CMP R, 1
JE L1
CMP R, 2
JE L2
JUMP L3 ; Default case

L1: statement1
JUMP L4
L2: statement2
JUMP L4
L3: statement3 ; Default
L4: Exit point

Explanation:

 The switch expression is compared to each case.

 When a match is found, control jumps to that label.
 The break is implemented using a jump to the end of the switch.

Ques 4) Explain the properties of code generation phase also explain the design
issue.
The code generation phase is the final phase in the compiler design process. It is responsible
for translating the intermediate representation (IR) of a program into target machine
code, such as assembly or binary instructions. This machine code should be efficient, correct,
and executable by the hardware. The code generation phase bridges the gap between high-
level language constructs and low-level hardware instructions.

A well-designed code generator is critical because poor code generation can drastically
reduce the performance of even well-written programs.

Properties of Code Generation Phase

For the code generation phase to be effective, it must fulfill the following essential properties:

1. Correctness

The most fundamental property of code generation is correctness. The machine code
generated must preserve the semantic meaning of the source program. This means the
compiled code must produce the same output and behavior for every valid input as the
original high-level program. Any deviation from the intended behavior is considered a
serious compiler error.

2. Efficiency
Efficiency refers to the performance of the generated code in terms of:

 Execution speed
 Memory usage
 Instruction count

Efficient code minimizes CPU cycles, memory access, and redundant operations. Efficient
register usage, minimal instructions, and reduced branching are all signs of good code
efficiency. This directly affects the runtime of programs and is especially important for real-
time or embedded systems.

3. Simplicity of Code Generation

The process of code generation should be simple, modular, and easy to implement.
Simplicity ensures that the code generator is:

 Maintainable
 Understandable
 Less prone to errors

A simple design also allows easier integration with other compiler phases such as
optimization or symbol management.

4. Speed of Compilation

The code generation phase must not slow down the entire compilation process. Especially in
large-scale software development or interactive development environments (IDEs), fast
compilation is important for better productivity. Therefore, code generation must be both fast
and efficient, even if it means sacrificing some optimization in simpler compilers.

5. Machine Independence and Portability

To support multiple hardware platforms, modern compilers aim to separate machine-

dependent and machine-independent parts. The front-end and middle-end (parser,
optimizer) remain the same, while the backend (code generator) is modified to suit different
machines. This allows for portability and reuse of the compiler infrastructure.

6. Support for Code Optimization

A good code generation phase should be compatible with optimization techniques. It must
allow:

 Loop optimization
 Constant folding
 Strength reduction
 Dead code elimination, etc.

Well-structured intermediate code and data flow analysis can make optimization more
effective during code generation.
Design Issues in Code Generation

Designing the code generation phase involves addressing several important issues and
decisions that affect the final machine code quality and performance.

1. Selection of Intermediate Code Format

The input to the code generator is typically intermediate code such as:

 Three-address code (TAC)

 Postfix notation
 Abstract syntax trees (AST)
 Directed Acyclic Graphs (DAG)

The choice of intermediate format greatly affects how easily and effectively code can be
generated. A good IR allows for easy mapping to machine instructions.

2. Target Program Form

A key design issue is the format of the output machine code. It can be:

 Absolute code (with fixed memory addresses)

 Relocatable code (can be moved during linking/loading)
 Assembly code (textual instructions)

Most compilers generate assembly code first because it is readable, editable, and allows
debugging before final binary translation.

3. Instruction Selection

Instruction selection involves choosing the appropriate machine instruction for each
intermediate code operation. This selection must consider:

 Instruction availability on the hardware

 Efficiency (e.g., use of shift instead of multiply)
 Special instructions like INC, DEC, MOV, etc.

Incorrect or inefficient selection can lead to suboptimal or even faulty machine code.

4. Register Allocation and Assignment

Registers are limited in number and are the fastest memory locations. A key challenge is to:

 Allocate variables and temporaries to registers

 Avoid register spilling to memory

Various algorithms like graph coloring or linear scan allocation are used for efficient
register management.
 5. Evaluation Order of Instructions

The order in which expressions and statements are evaluated can affect:

 The number of registers needed

 Instruction reordering
 Intermediate results

For example, evaluating a common subexpression first may reduce redundancy and register
use.

6. Handling Control Structures

Translating control flow statements such as if, while, for, and switch into jumps, labels, and
branches is another major concern. Efficient control flow code must:

 Minimize the number of jumps

 Avoid unnecessary labels
 Be structured and readable

Poor handling of control flow can degrade performance and increase code size.

7. Memory Management and Stack Allocation

The code generator must handle memory for:

 Local variables
 Parameters
 Return addresses
 Temporaries

Using the stack and activation records, the compiler must manage memory in a structured
way, especially to support function calls and recursion.

Ques 5) Explain code optimization with the concept of machine dependent and
independent code optimization.

Code optimization is the phase of the compiler in which the intermediate code is improved
to make the final target code more efficient in terms of execution speed, memory usage, or
other resources, without altering the program's output or behavior.

The goal is to generate better quality code that:

 Executes faster
 Uses fewer instructions
 Reduces memory usage
 Improves overall program performance

Types of Code Optimization

Code optimization techniques are broadly classified into two categories:

1. Machine Independent Optimization

➤ Definition:

Machine-independent optimizations are those that are not tied to the architecture of any
specific hardware. They are applied to the intermediate representation (IR) of the code and
are focused on improving logic and structure.

➤ Features:

 Performed before target code generation

 Focuses on reducing redundancy and improving code structure
 Applicable across all machines

➤ Common Techniques:

🔹 Constant Folding:

Evaluate constant expressions at compile time.

int x = 2 * 3; // Replaced with int x = 6;

🔹 Common Subexpression Elimination:

Avoid recomputing the same expression multiple times.

a = b + c;
d = b + c; → Reuse value of b + c from a
🔹 Dead Code Elimination:

Remove code that never affects the program output.

if (false) { x = 5; } // Eliminated
🔹 Loop Invariant Code Motion:

Move calculations outside the loop if they do not change inside the loop.

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

x = a + b; // moved outside loop
}
🔹 Strength Reduction:

Replace expensive operations with cheaper ones.

x = y * 2; → x = y + y;
2. Machine Dependent Optimization

➤ Definition:

Machine-dependent optimizations are applied after target code generation and depend on
the hardware architecture, such as the number of registers, instruction set, and pipeline
design.

➤ Features:

 Specific to the target machine (e.g., x86, ARM)

 Applied during or after code generation
 Uses hardware characteristics for optimization

➤ Common Techniques:

🔹 Register Allocation:

Assign frequently used variables to CPU registers instead of memory to improve speed.

🔹 Instruction Scheduling:

Reorder instructions to avoid pipeline stalls in modern CPUs.

🔹 Peephole Optimization:

Small, local optimizations by examining a few instructions at a time (a "peephole").

Example:

MOV A, B
MOV B, A → Can be removed or optimized
🔹 Address Mode Optimization:

Use more efficient addressing modes supported by hardware.

Example: Use ADD AX, [BX] instead of multiple instructions to fetch and add.

Comparison Table

Aspect Machine Independent Machine Dependent

Depends on hardware? No Yes

Phase applied During intermediate code phase During/after target code generation

Portable Yes, across machines No, specific to target machine

Examples Constant folding, dead code Peephole, instruction scheduling

Ques 6) Explain the process of instruction selection in code generation. How
does the choice of target machine instruction impact the performance of
generation code.

Instruction selection is an essential part of the code generation phase in a compiler. It

involves translating intermediate code (IR) into machine-level instructions for a specific
target architecture. The objective is to choose the most efficient machine instructions that
correctly implement the logic of the source code.

This phase directly affects the performance, size, and speed of the generated program.

Process of Instruction Selection

The instruction selection process typically follows these steps:

1. Input from Intermediate Representation (IR)

 The compiler first translates source code into an intermediate form (like three-address
code, syntax tree, or DAG).
 This IR is machine-independent and needs to be mapped to actual hardware
instructions.

2. Pattern Matching

 The code generator compares parts of the IR with predefined instruction patterns
that correspond to machine-level instructions.
 Each IR operation is matched with one or more potential machine instructions.

Example:
x=a+b
Could match:

 ADD a, b, x (3-address instruction)

 MOV a, R1; ADD b, R1 (2-address machine)

3. Instruction Mapping / Selection

 Among the available matching instructions, the compiler chooses the one that:
o Uses fewer CPU cycles
o Consumes less memory
o Requires fewer instructions
 Often guided by a cost model that assigns weights to instructions based on execution
time or size.

4. Use of Instruction Set Architecture (ISA)

 The compiler uses information about the target machine’s ISA:

o Number and type of registers
o Available instruction formats (e.g., arithmetic, logical, branch)
 o Special-purpose instructions (like multiply-accumulate or shift)

5. Handling Complex Expressions

 For expressions with multiple operators, the compiler may generate a sequence of
instructions based on evaluation order and register availability.

6. Code Generation and Emission

 After selecting instructions, the compiler emits the machine or assembly code.
 The code is further passed through register allocation and possibly machine-
dependent optimization.

Impact of Instruction Selection on Performance

The choice of instructions has a significant impact on the performance of the generated
code:

1. Execution Speed

 Some instructions are faster than others.

o Using INC x is faster than ADD x, 1
o SHL (shift left) is faster than MUL (multiply) by 2
 Choosing efficient instructions leads to faster execution.

2. Code Size

 Compact instructions lead to smaller executables, which are faster to load and use
less memory.
 Reducing unnecessary instructions improves overall code density.

3. Register Usage

 Efficient instruction selection can reduce the need for extra registers.
 Poor selection may increase register pressure, leading to more memory accesses
(slower).

4. Pipeline Performance

 Modern CPUs use instruction pipelines. Some instructions cause stalls or hazards.
 Instruction selection helps in scheduling operations to minimize pipeline stalls.

5. Power Consumption

 In embedded systems, selecting low-power instructions or fewer instructions helps

reduce battery usage.
 Example

Suppose the IR operation is:

x = y * 2;

 Poor instruction choice:

o MOV y, R1
o MOV 2, R2
o MUL R1, R2 → 3 instructions
 Optimized instruction choice:
o MOV y, R1
o SHL R1, 1 → Shift left = Multiply by 2 → Faster and uses 2 instructions

Ques 7) What is basic block in context of a compiler? Describe the process of

construction basic block from a given intermediate code.
A Basic Block (BB) is a sequence of consecutive statements or instructions in a program’s
intermediate code such that:

 Control enters at the beginning of the block (only at the first instruction).
 Control leaves at the end of the block without any possibility of branching or
stopping in between.
 There are no jumps or branch instructions inside the block, except possibly at the
end.
 There are no labels (jump targets) inside the block, except at the beginning.

In simple terms, a basic block is a straight-line code sequence with no branches except into
the entry and out of the exit.

Importance of Basic Blocks

 Basic blocks are the fundamental units for many compiler optimizations.
 Control flow analysis and data flow analysis are easier on basic blocks.
 They help in constructing control flow graphs (CFG).

Characteristics of a Basic Block

 Single entry point

 Single exit point
 No branches inside except at the end
 No labels inside except at the start

Process of Constructing Basic Blocks from Intermediate Code

Given intermediate code (e.g., three-address code), the compiler divides it into basic blocks
in the following steps:

Step 1: Identify Leaders

A leader is the first instruction of a basic block. Rules to identify leaders:

1. The first instruction in the program is always a leader.

2. Any instruction that is the target of a jump or branch (i.e., a label) is a leader.
3. Any instruction that immediately follows a jump or branch instruction is a
leader.

Step 2: Form Basic Blocks

 Once leaders are identified, each leader marks the start of a new basic block.
 The basic block includes the leader and all instructions that follow it until the next
leader or the end of the program.
 This means the block contains instructions from the leader up to (but not including)
the next leader.

Step 3: Repeat for all leaders

 Continue this process for all leaders to partition the entire intermediate code into a
sequence of basic blocks.

Example

Consider this intermediate code snippet:

1: a = 5
2: b = 10
3: if a < b goto 7
4: c = a + b
5: goto 8
6: d = c - a
7: e = d * 2
8: print e

 Step 1: Identify leaders:

o Instruction 1 is the first instruction → leader
o Instruction 3 has a jump to instruction 7 → instruction 7 is leader
o Instruction after jump at 5 → instruction 6 is leader
 Step 2: Form blocks:
o Block 1: Instructions 1, 2, 3
o Block 2: Instructions 4, 5
o Block 3: Instruction 6
o Block 4: Instructions 7, 8

Flowchart: Basic Block Construction

Start
|
v
Identify first instruction as leader
|
v
For each instruction in code:
 Is it a jump/branch target? ---> Yes ---> Mark as leader
|
No
|
Is it immediately after jump/branch? ---> Yes ---> Mark as leader
|
No
|
v
Partition code into basic blocks from each leader till next leader or end
|
v
End

Diagram: Example of Basic Blocks

Consider the intermediate code example:

1: a = 5
2: b = 10
3: if a < b goto 7
4: c = a + b
5: goto 8
6: d = c - a
7: e = d * 2
8: print e

Identified Leaders:

 Instruction 1 (first instruction)

 Instruction 6 (after jump at 5)
 Instruction 7 (jump target of 3)

Basic Blocks formed:

Block 1: [1, 2, 3]
a=5
b = 10
if a < b goto 7

Block 2: [4, 5]
c=a+b
goto 8

Block 3: [6]
d=c-a

Block 4: [7, 8]
e=d*2
print e
Ques 8) explain the concept of DAG representation of baic block. What is the
optimization of basic block?

1. Introduction

In compiler design, a basic block is a straight-line code sequence with no branches except at
the end. To optimize such a block efficiently, the compiler uses an intermediate
representation called a Directed Acyclic Graph (DAG).

2. What is DAG Representation?

 A DAG (Directed Acyclic Graph) is a graph structure with directed edges and no
cycles.
 In the context of a basic block, a DAG is used to represent expressions and their
computations.
 Each node in the DAG corresponds to either:
o An operator (e.g., +, -, *, /),
o A variable, or
o A constant (leaf nodes).
 The edges represent the operands of the operators.

3. Purpose of DAG in Basic Block

 To capture dependencies between computations.

 To detect common subexpressions (same expressions computed multiple times).
 To facilitate code optimization by eliminating redundant calculations.
 To assist in generating efficient target code.

4. How to Construct a DAG for a Basic Block

 Process each statement in the basic block sequentially.

 For each expression:
o Check if a node representing the same operator and operands already exists.
 If yes, reuse that node (this identifies common subexpressions).
 If no, create a new node.
 Leaf nodes are created for variables or constants.
 Assign names or variables to nodes representing expressions to track results.

5. Example

Consider the basic block:

1) t1 = a + b
2) t2 = a + b
3) t3 = t1 * c
4) t4 = t2 * c

DAG Construction:
  Create leaf nodes for a, b, and c.
 Create an operator node for a + b (used in both t1 and t2).
 Create an operator node for (a + b) * c (used in t3 and t4).
 Nodes for t1 and t2 point to the same (a + b) node.
 Nodes for t3 and t4 point to the same ((a + b) * c) node.

Diagram:
(*)
/ \
(+) c
/ \
a b

 The node (+) represents a + b.

 The node (*) represents (a + b) * c.
 Both t1 and t2 use the (+) node.
 Both t3 and t4 use the (*) node.

6. What is Basic Block Optimization?

 Optimization within a basic block aims to reduce redundant computations, remove

dead code, and simplify expressions.
 Because there are no branches inside, it is safe and straightforward to apply local
optimizations.

7. Common Basic Block Optimizations

 Common Subexpression Elimination: Avoid recomputing the same expression by

reusing the DAG node.
 Constant Folding: Compute constant expressions at compile time.
 Dead Code Elimination: Remove instructions whose results are never used.
 Strength Reduction: Replace expensive operations by cheaper equivalents (e.g.,
multiply by 2 replaced by addition).
 Copy Propagation: Replace variables that are copies of others with their originals.

8. Role of DAG in Optimization

 DAG explicitly shows common subexpressions and dependencies.

 Allows the compiler to identify opportunities to reuse computation results.
 Helps in generating minimal code without redundant instructions.
 Supports effective code generation for optimized machine instructions.

Points Explanation

DAG Directed Acyclic Graph representing expressions & dependencies

 Points Explanation

Nodes Operators, variables, or constants

Edges Operand relationships

Construction Create or reuse nodes for expressions

Basic Block Optimization Improve code within a block using techniques like common subexpr

Benefits Removes redundant computation, improves efficiency

Ques 9) Define basic block and flow graph with example. How given
program can be converted into flow graph.

1. Definition of Basic Block

 A Basic Block is a sequence of consecutive statements or instructions in a program

such that:
o Control enters at the first instruction only.
o Control leaves at the last instruction only.
o There are no jump or branch instructions inside the block except possibly at
the end.
o There are no labels (jump targets) inside the block except possibly at the
beginning.

In simple words: It is a straight-line code sequence with no branches in or out except at the
entry and exit points.

2. Definition of Flow Graph (Control Flow Graph)

 A Flow Graph (or Control Flow Graph - CFG) is a directed graph that represents
the flow of control in a program.
 Each node in the graph represents a basic block.
 A directed edge from one node to another represents possible flow of control from
the first block to the second.
 It shows all possible paths that the execution may take through the program.

3. Example Program

Consider the following simple program:

1. a = 5;
2. b = 10;
3. if (a < b) goto L1;
4. c = a + b;
5. goto L2;
L1:
6. c = a - b;
L2:
7. print(c);

4. Identification of Basic Blocks

 Block 1: Instructions 1, 2, 3 (includes the conditional jump)

 Block 2: Instruction 4, 5 (includes unconditional jump)
 Block 3: Instruction 6 (label L1)
 Block 4: Instruction 7 (label L2)

5. Constructing the Flow Graph

 Nodes are basic blocks: B1, B2, B3, B4.

 Edges:
o From B1 to B2 (if a < b condition is false, the jump is not taken)
o From B1 to B3 (if a < b condition is true, jump to L1)
o From B2 to B4 (unconditional jump after block 2)
o From B3 to B4 (fall-through after block 3)

6. Flow Graph Diagram

+-------+
| B1 | (a=5; b=10; if a<b goto L1)
+-------+
/ \
true false
/ \
+-------+ +-------+
| B3 | | B2 | (c = a-b) (c = a+b; goto L2)
+-------+ +-------+
\ /
\ /
+-------+
| B4 | (print(c))
+-------+

7. Steps to Convert a Program into a Flow Graph

 Step 1: Divide the program into basic blocks by identifying leaders:

o First statement is a leader.
o Statements that are targets of jumps are leaders.
o Statements immediately after jumps are leaders.
 Step 2: Create a node for each basic block.
 Step 3: Draw directed edges to show possible control flow between blocks:
o For conditional jumps, edges represent the true and false paths.
o For unconditional jumps, edges go to the target block.
o For sequential flow, edges connect consecutive blocks.

Summary
 Term Definition

Basic Block Straight-line sequence of instructions with single entry/exit

Flow Graph Directed graph with basic blocks as nodes and control flow as edges

Ques 10) Explain the concept of runtime environment in a compiler.

Discuss the stack allocation and heap allocation strategies. Used to manage
memory during program.

1. Concept of Runtime Environment

The runtime environment is an essential component that supports the execution of a

compiled program. It encompasses the collection of data structures, memory management
schemes, control flow mechanisms, and system resources used during the program’s
execution phase.

Specifically, the runtime environment handles:

 Storage management for variables and data.

 Control of procedure calls and returns.
 Dynamic memory management.
 Input/output management and other support services.

The runtime environment is dynamically active when the program is running, providing the
context and infrastructure necessary for executing instructions generated by the compiler.

2. Memory Management in the Runtime Environment

Memory management is a critical aspect of the runtime environment and is primarily divided
into two regions:

 The Stack: used for static or temporary memory allocation related to procedure calls.
 The Heap: used for dynamic memory allocation during program execution.

3. Stack Allocation

The stack is a contiguous block of memory that functions according to the Last-In-First-
Out (LIFO) principle.

 Each function call creates an activation record (or stack frame) that stores:
o Function parameters,
o Local variables,
o Return address (to resume after function execution),
o Saved processor registers.
 When a function is invoked, its activation record is pushed onto the stack.
 When the function completes, its activation record is popped off, freeing that memory
instantly.
  This automatic memory management ensures fast allocation and deallocation.

Advantages of stack allocation:

 High efficiency due to simple push/pop operations.

 Clear lifetime of variables bound to the execution of functions.
 No fragmentation, as the stack grows and shrinks in a well-defined manner.

Limitations:

 The size of the stack is limited and fixed at program start.

 Cannot be used for objects whose lifetime extends beyond the function call.
 Recursive calls require careful management to avoid stack overflow.

4. Heap Allocation

The heap is a large, unstructured memory region used for dynamic memory allocation. It
supports objects and data structures whose sizes or lifetimes are not known at compile time.

 Memory on the heap is explicitly allocated and freed by the program, using language-
specific operations (e.g., malloc and free in C, new and delete in C++).
 Unlike the stack, heap allocation is flexible but slower, due to the need for searching
free blocks and managing fragmentation.
 Heap memory is suitable for:
o Objects whose size cannot be determined at compile time.
o Data structures that persist beyond the scope of a single function.
o Complex structures like linked lists, trees, graphs.

Advantages of heap allocation:

 Flexible and dynamic memory management.

 Allows sharing and persistence of data beyond individual functions.
 Supports large amounts of memory.

Limitations:

 Slower allocation and deallocation compared to the stack.

 Risk of memory leaks if allocated memory is not freed.
 Potential for fragmentation, where free memory is split into small, unusable blocks.

5. Summary and Relationship

The runtime environment manages memory by combining stack allocation for predictable,
temporary data and heap allocation for flexible, dynamic data needs.

Feature Stack Allocation Heap Allocation

Local variables, function call

Usage Dynamic data structures, objects
management
 Feature Stack Allocation Heap Allocation

Allocation/Deallocation Automatic (push/pop) Manual (programmer controlled)

Programmer-defined or garbage
Lifetime Limited to function execution
collected

Speed Faster Slower

Memory Fragmentation No fragmentation Possible fragmentation

Size Limit Limited stack size Larger, system-dependent