Question: Demerits:

Explain various storage allocation strategies with its merits and demerits. [7M]
 Limited memory size (stack size is fixed).
Answer:  Data is lost when function ends.
 Cannot allocate variable size data at runtime.
Storage allocation refers to how memory is assigned to programs and data during execution.
There are three main storage allocation strategies: 3. Heap Allocation (Dynamic Allocation)

1. Static Allocation Definition:

Memory is allocated at runtime using functions like malloc(), calloc() in C.
Definition:
Memory is allocated at compile time before execution begins. Example:

Example: int *p = (int*)malloc(sizeof(int));

int a = 10; Merits:

Merits:  Flexible, allows variable size memory allocation.

 Can manage complex data structures like trees, graphs, etc.
 Easy to implement.  Memory can be freed when not required.
 Efficient access to memory using fixed addresses.
 No runtime overhead for allocation. Demerits:

Demerits:  Slower access compared to stack.

 Memory leak issues if not properly deallocated.
 Wastes memory if the allocated memory is not used.  Overhead of managing heap memory.
 Cannot handle dynamic data structures like linked lists.
 Size must be known at compile time.

2. Stack Allocation b) Define activation records. Explain how it is related with runtime storage allocation. (7M)

Definition: Answer:
Memory is allocated and deallocated in a Last In First Out (LIFO) manner during function calls.
Activation Record:
Example:
Local variables inside a function: An activation record is a block of memory that stores information about a single execution of a
procedure (function or method). It is created when a function is called and removed when the
void func() { function exits.
int x = 5;
}
It is also called a stack frame, and it is stored in the runtime stack.
Merits:
Contents of an Activation Record:
 Fast allocation and deallocation.
 Suitable for recursive function calls. 1. Return Address – Where to return after function execution.
 No fragmentation. 2. Parameters – Values passed to the function.
3. Local Variables – Variables declared inside the function.
 4. Temporary Values – Intermediate values used during evaluation. 2. Storage Allocation Strategies for Recursive Calls:
5. Saved Registers – If any registers are used, their values are saved.
Recursive procedures call themselves. So, each recursive call needs a separate memory to
Relation with Runtime Storage Allocation: store its data (like local variables and return address).
The main strategy used is:
 During program execution, memory is divided into:
o Code Area – For compiled code. a) Stack-based Allocation:
o Static Area – For global/static variables.
o Heap – For dynamically allocated memory.  Each time a recursive procedure is called, a new activation record is pushed onto the
o Stack – For activation records. runtime stack.
 Each function call creates a new activation record on the runtime stack.  This ensures that each call has its own separate copy of local variables and return
 When the function returns, its activation record is popped off the stack. address.
 When the call finishes, its activation record is removed (popped) from the stack.
Example:
✅Advantages:
void add(int x, int y) {
int sum = x + y;
printf("%d", sum);  Supports dynamic allocation during runtime.
}  Allows recursive and nested procedure calls efficiently.

When add(2, 3) is called: Example:

int factorial(int n) {
if (n == 0) return 1;
 An activation record is created with: else return n * factorial(n - 1);
o Parameters: x=2, y=3 }
o Local variable: sum
o Return address Calling factorial(3) will create a stack like this:

This activation record is pushed to the runtime stack. Top of Stack

--------------
Q. What is runtime stack? Explain the storage allocation strategies used for recursive factorial(1)
factorial(2)
procedure calls. [7M] factorial(3)
--------------
Answer: Bottom of Stack

1. Runtime Stack: Each call to factorial(n) has its own activation record, so recursive calls don’t overwrite
each other’s data.
 A runtime stack (also called call stack) is a memory area used to manage
function/procedure calls during program execution. Q. What is a flow graph? Explain how a flow graph can be constructed for a given
 It stores activation records (stack frames) of functions, including local variables, program.
return address, parameters, and saved registers. Also draw the flow graph for the below program:
 When a function is called, its activation record is pushed onto the stack. When the
Main()
function returns, the record is popped.
{
 It supports Last-In First-Out (LIFO) behavior, making it suitable for nested and int sum, n, i;
recursive calls. sum = 0;
for i := 1 to n do
sum := sum + i;
write(sum);
} +---------+ +---------+
| Block 3 | | Block 4 | --> write(sum)
+---------+ +---------+
Answer: |
v
Flow Graph: (Back to Block 2)

A flow graph is a diagram that represents the control flow of a program using nodes and edges. Explanation:

 Nodes represent statements or blocks of code.  Block 1 initializes sum.

 Edges (arrows) represent the flow of control (how execution moves).  Block 2 checks the loop condition (i := 1 to n).
 If true, goes to Block 3 (adds i to sum) then loops back.
Flow graphs help in:  If false, jumps to Block 4 to print the result.

 Understanding program flow Q) What are the principles associated with designing calling sequences and the
 Testing (like path testing or loop testing) layout of activation records? [7M]
 Debugging
Answer:
Steps to Construct Flow Graph:
Calling sequence and activation record layout are important concepts in the implementation of
1. Divide the program into basic blocks (each block has no jumps except at the end). procedures (functions). Their design affects the efficiency and correctness of function calls and
2. Number each block. returns.
3. Draw arrows showing the flow from one block to another.
Principles for Designing Calling Sequences and Activation Records:
Program Basic Blocks:
1. Simplicity:
Let’s break the program into blocks: o The design should be simple and easy to implement.
o Should support both recursive and non-recursive procedures.
 Block 1: sum = 0; 2. Efficiency:
 Block 2: i := 1 to n (loop condition) o Minimize the overhead of procedure calls.
 Block 3: sum = sum + i; o Optimize the usage of registers and memory.
 Block 4: write(sum); 3. Modularity:
o Each function should have its own isolated environment.
Flow Graph (ASCII Diagram): o Avoid interference between functions.
4. Support for Recursion:
o Activation records should be created dynamically during recursive calls.
5. Clear Division of Responsibilities:
+---------+ o Caller and callee should have clearly defined roles in saving and restoring values.
| Block 1 | --> sum = 0 6. Preservation of Registers:
+---------+
o Decide which registers are saved by the caller and which by the callee (caller-
|
v saves vs callee-saves).
+---------+ 7. Proper Access to Variables:
| Block 2 | --> for i := 1 to n o Ensure access to local, global, and non-local variables.
+---------+
/ \
Yes No Activation Record Layout (Example):
/ \
v v An Activation Record typically contains the following fields:
|------------------------| 1. Compile-Time Evaluation:
| Return Address | ← address to return after function ends o Perform operations during compilation.
|------------------------|
| Actual Parameters | ← arguments passed to function o Example:
|------------------------| o int x = 3 * 4; // Compiler changes it to int x = 12;
| Control Link (Dynamic) | ← pointer to caller's activation record 2. Constant Folding:
|------------------------| o Combine constant values at compile time.
| Local Variables | ← variables declared inside function o Example:
|------------------------| o int y = (2 + 5) * 3; // Optimized to int y = 21;
| Temporaries | ← intermediate values during computation
|------------------------|
3. Dead Code Elimination:
o Removes code that never affects the output.
o Example:
o if (false) {
Example (Calling Sequence): o x = 10;
o }
Suppose main() calls sum(a, b): o // The above block is removed.
4. Common Subexpression Elimination:
1. Caller (main) actions: o Avoids repeating the same expression.
o Example:
o Push arguments a, b.
o a = (b + c) + d;
o Save return address. o e = (b + c) * f;
o Transfer control to sum. o // (b + c) computed once and reused
2. Callee (sum) actions: 5. Loop Optimization:
o Save control link (dynamic link). o Improves the performance of loops.
o Allocate space for local variables. o Example:
3. On Return: Move invariant code outside the loop.
o sum removes its activation record. o for (int i = 0; i < 100; i++) {
o x = y * z; // If y and z are constant, move outside loop
o Control returns to main.
o }
6. Strength Reduction:
Question: o Replaces costly operations with cheaper ones.
What is the role of Code Optimizer in a compiler? Is it a mandatory phase? Explain the o Example:
various sources of optimization with example. [7M] o x = y * 2; // Optimized to x = y + y;\

Answer:
a) Explain how data flow equations are set up and solved for improving code.
Role of Code Optimizer in Compiler: [7M]
 The Code Optimizer is a phase in the compiler that improves the intermediate code to Answer:
make the final program run faster and consume less memory.
 It removes unnecessary code, reduces redundant operations, and improves execution Data flow analysis is used in compilers to collect information about how data values are used
speed. and modified in a program. This helps in code optimization like dead code elimination, constant
 Optimization is done without changing the output of the program. propagation, etc.

Is Code Optimization a Mandatory Phase? Steps to set up and solve data flow equations:

 No, it is not mandatory. 1. Identify basic blocks in the code.

 It is an optional phase, but very useful for generating efficient code. 2. Construct Control Flow Graph (CFG).
3. For each block, define:
Sources of Optimization:
 o
GEN[B]: Variables generated (defined) in B before any use. Steps to identify basic blocks:
o
KILL[B]: Variables whose previous definitions are killed in B.
4. Set up IN[B] and OUT[B] equations: 1. Start with the first instruction as a leader.
o IN[B] = ∪ OUT[P] for all predecessors P of B 2. Any target of a jump is a leader.
o OUT[B] = GEN[B] ∪ (IN[B] - KILL[B]) 3. Any instruction following a jump is a leader.
5. Use iteration until IN and OUT values stop changing (reaches a fixed point). 4. Each leader starts a new basic block.

Example: Example:
1: a = 5; 1: a = 1;
2: b = 10; 2: b = 2;
3: c = a + b; 3: if (a < b) goto L1;
4: a = 7; 4: c = a + b;
5: d = a + b; 5: goto L2;
L1:
Break into basic blocks: 6: c = a - b;
L2:
7: print(c);
 B1: 1, 2
 B2: 3 Basic Blocks:
 B3: 4, 5
 B1: 1, 2, 3
Now:  B2: 4, 5
 B3: 6
 GEN[B1] = {a=5, b=10}  B4: 7
 KILL[B3] = {a=5} (because a is redefined)
 GEN[B3] = {a=7} Flow Graph:

Apply equations to compute IN and OUT for optimization like constant propagation.  B1 → B2 (if condition false)
 B1 → B3 (if condition true)
b) Discuss basic blocks and flow graphs with an example. [7M]  B2 → B4
 B3 → B4
Answer:
The flow graph helps in optimization like dead code removal or loop analysis.
A Basic Block is a sequence of instructions with:
a) Give the general structure of an activation record? Explain the purpose of
 No branching in except at the beginning. each component involved in it. [7M]
 No branching out except at the end.
Answer:
Basic blocks help in identifying areas for optimization.
An activation record is a block of memory used by the compiler to store information about a
Flow Graph (Control Flow Graph): function (procedure) call.

A Flow Graph shows flow of control between basic blocks using nodes and edges. General Structure of Activation Record:
+---------------------+
 Nodes represent basic blocks. | Return Value |
 Edges show possible flow of control from one block to another. +---------------------+
| Actual Parameters |
+---------------------+
| Control Link |
+---------------------+ Techniques:
| Access Link |
+---------------------+
| Saved Machine Status| 1. Constant Folding:
+---------------------+ Compute constant expressions at compile time.
| Local Variables | Example:
+---------------------+
int x = 3 * 4; → replaced with int x = 12;
| Temporaries |
+---------------------+ 2. Constant Propagation:
Replace variables with known constant values.
Purpose of Each Component: Example:
int a = 5; int b = a + 2; → int b = 7;
1. Return Value: 3. Dead Code Elimination:
Stores the result to be returned to the caller. Remove code that never affects output.
2. Actual Parameters: Example:
Stores the arguments passed to the function. if(false) { x = 10; } → this block is removed.
3. Control Link: 4. Common Subexpression Elimination:
Points to the activation record of the caller function (helps in returning). Avoid re-evaluation of same expressions.
4. Access Link: Example:
Points to non-local variables in the static nesting (used in nested functions). a = b + c; d = b + c; → compute b + c once and reuse it.
5. Saved Machine Status: 5. Strength Reduction:
Stores registers and program counter before the function call. Replace costly operations with cheaper ones.
6. Local Variables: Example:
Stores variables declared inside the function. x = x * 2; → x = x + x;
7. Temporaries: 6. Copy Propagation:
Used to hold intermediate results during expression evaluation. Replace duplicate variable usage.
Example:
Example: a = b; c = a + 1; → c = b + 1;
int add(int a, int b) { 7. Loop Invariant Code Motion:
int sum = a + b; Move code out of loop if it doesn’t change.
return sum;
} Example:
for(int i=0; i<n; i++) { x = 5; y[i] = x + i; } → move x = 5 outside loop.
For the above function, activation record will contain:
Question:
 a, b → actual parameters
 sum → local variable a) Write a short note on peephole optimization and various operations used in it. [7M]
 return value → returned sum
 control & access links → for function call management Answer:

Peephole optimization is a technique used in compiler optimization to improve the performance

b) Explain various machine independent code optimization techniques. [7M]
of a program by making small, localized changes to its intermediate code or machine code. It
focuses on optimizing a small window of instructions (a "peephole") by replacing inefficient
Answer:
sequences with more efficient ones.
Machine Independent Code Optimization means optimizing code without depending on the
hardware. It helps improve performance and reduce code size. Key Operations in Peephole Optimization:

1. Redundant Instruction Removal:

 o Removes unnecessary instructions that do not contribute to the program's Answer:
outcome. Loop unrolling is an optimization technique used to improve the performance of loops in a
o Example: MOV R1, R2 followed by MOV R2, R3 can be replaced with MOV R1, program by reducing the overhead associated with loop control. This technique involves
R3. expanding the loop body so that multiple iterations are performed within a single loop iteration.
2. Constant Folding: By doing so, the number of loop control instructions (like incrementing the loop counter and
o Replaces expressions involving constants with their computed values during checking the loop condition) is reduced, leading to improved execution speed.
compilation.
o Example: 3 + 5 is replaced with 8. Advantages of Loop Unrolling:
3. Common Subexpression Elimination:
o Identifies and eliminates repeated expressions by computing the result once and 1. Reduced Loop Overhead:
reusing it. In a typical loop, there are instructions for updating the loop counter and checking the
o Example: If A + B appears multiple times, it can be computed once and stored in loop condition in every iteration. Loop unrolling minimizes these checks by executing
a register for reuse. multiple iterations within a single loop iteration.
4. Instruction Combination: 2. Improved CPU Pipelining:
o Combines multiple instructions into a single, more efficient one. Modern CPUs can execute multiple instructions simultaneously using pipelining.
o Example: Two consecutive additions can be combined into one operation using Unrolling a loop can help in better instruction-level parallelism, as it reduces the
the same operands. frequency of branch instructions, which can hinder the pipeline.
5. Strength Reduction: 3. Better Cache Utilization:
o Replaces costly operations like multiplication and division with cheaper By accessing data more frequently in a continuous block, loop unrolling improves data
operations such as addition or bit shifts. locality, which helps in better utilization of CPU caches.
o Example: X * 2 can be replaced by X << 1.
6. Jump Optimization: Example of Loop Unrolling:
o Reduces or eliminates unnecessary jumps or branch instructions in the code.
o Example: A jump to the next instruction can be removed if the flow of control is Consider the following simple loop that adds two arrays element by element:
straightforward.
for (int i = 0; i < n; i++) {
Example of Peephole Optimization: C[i] = A[i] + B[i];
}

Consider the following sequence of instructions:

This loop can be unrolled by processing two elements per iteration:
MOV R1, 0
ADD R1, R2 for (int i = 0; i < n; i += 2) {
MOV R3, R1 C[i] = A[i] + B[i];
ADD R3, 4 C[i+1] = A[i+1] + B[i+1];
}

After applying peephole optimization, the sequence could be optimized as:

Explanation:
MOV R3, R2
ADD R3, 4  In the unrolled loop, two additions are performed in each iteration instead of just one.
 The loop index i is incremented by 2, meaning the loop runs fewer times, reducing the
This optimization removes the redundant MOV R1, 0 and the unnecessary MOV R3, R1. loop control overhead.
 This optimization can make the loop execute faster on modern processors by exploiting
Peephole optimization is a simple yet effective way to improve the efficiency of code by making instruction-level parallelism and better cache behavior.
small, localized changes that can lead to significant performance improvements.
Question:
Question: Explain static and stack storage allocations with examples. [7M]
Describe loop unrolling and its advantages with your own examples. [7M]
Answer: Answer:
Static Storage Allocation: Syntax Tree:
In static storage allocation, the memory for variables is allocated at compile-time, and the
memory remains fixed throughout the program's execution. The size and address of the variable The syntax tree represents the expression's hierarchical structure. Here's how we can break it
are determined before the program runs, and it does not change while the program is running. down:

 Example: =
In a C program, global variables and constants are examples of static storage allocation. / \
For instance, if we declare a global variable like: a[i] -
/ \
 int x = 10; // Static allocation
* *
/ \ / \
The variable x will be allocated a fixed memory location before the program starts and b c b d
will retain its value throughout the program's lifetime.
Explanation:
Stack Storage Allocation:
In stack storage allocation, memory is dynamically allocated at runtime for local variables within  The root of the tree is the assignment operator =.
functions. When a function is called, its local variables are pushed onto the stack, and when the  Left side of = is a[i].
function ends, the memory is automatically freed. This memory allocation is temporary and  Right side of = is the subtraction (-) operator, which takes the results of two
managed using a stack structure. multiplications (*).

 Example: Quadruples:
In a C program, local variables within a function are allocated using the stack. For
example: In quadruples, we generate a list of four components: (operator, operand1, operand2, result).
 void function() { Here's how we translate the expression:
 int a = 5; // Stack allocation
 int b = 10; // Stack allocation
1. ( *, b, c, t1 )
 }
(b * c) is stored in temporary variable t1.
2. ( *, b, d, t2 )
Here, the variables a and b are stored in the stack memory, and their memory is released
(b * d) is stored in temporary variable t2.
when the function finishes execution.
3. ( -, t1, t2, t3 )
Subtract t1 from t2 and store the result in t3.
Key Differences:
4. ( =, t3, , a[i] )
The result t3 is assigned to a[i].
Feature Static Allocation Stack Allocation
Memory Allocation At compile time At runtime (during function call) Triples:
Lifetime of Variables Throughout the program Limited to the function's scope
Memory Release Manually, when program ends Automatically when function returns In triples, we only store the operator and its operands, and use indices for results. Here's the
Examples Global variables, constants Local variables in functions translation:

1. ( *, b, c ) → index 1
Question: 2. ( *, b, d ) → index 2
3. ( -, 1, 2 ) → index 3
Translate the arithmetic expression a[i] = b * c - b * d into a syntax tree, quadruples, and
4. ( =, 3, a[i] )
triples.
Explanation:
  In triples, the result of each operation is identified by an index, and the operands are 1. Node 1: Start of the program. Initializes sum to 0 and reads n.
referenced by their corresponding indices. 2. Node 2: The loop condition FOR i = 1 TO n is checked.
o If true, it moves to Node 3.
Summary: o If false, it moves to Node 4 to print the sum and terminate the program.
3. Node 3: The loop body where a number is read, and the sum is updated.
 Syntax Tree represents the hierarchical structure of the expression. 4. Node 2: After the loop body, control returns to check the loop condition again.
 Quadruples use four fields (operator, operand1, operand2, result). 5. Node 4: Print the final sum and exit.
 Triples use only three fields (operator, operand1, operand2), referencing previous results
by indices. Rules for Flow Graph Construction:

Question: 1. Basic Block Representation: Each block represents a sequence of statements without
any branches, i.e., a block that executes sequentially without any condition or decision.
Write the pseudocode for finding the sum of ‘n’ numbers. Identify the basic blocks and construct 2. Control Flow Edges: An edge is drawn from one basic block to another to indicate the
the flow graph for it. Explain the rules used for this. (7M) flow of control. This could be based on decisions (such as loops or conditions) or
sequential execution.
3. Loop Handling: For loops, we create two nodes: one for the loop condition and one for
the loop body. After executing the loop body, the control returns to the condition check.
Answer: 4. End Conditions: Once the loop condition fails, the flow graph moves to the block where
the result is printed, marking the end of the program.
Pseudocode to Find the Sum of ‘n’ Numbers:
Flow Graph for the Pseudocode:
START
Set sum = 0 +------+
Read n | Start|
FOR i = 1 TO n +------+
Read number |
sum = sum + number v
END FOR +------------+
Print sum | Initialize |
END | sum = 0, |
| Read n |
Basic Blocks: +------------+
|
v
1. Block 1: Initialization – The sum is initialized to 0 and the value of n is read. +------------+
o Statement: sum = 0 and Read n | i = 1 to n |
2. Block 2: Loop Setup – The loop is set up to iterate from 1 to n. | (Condition)|
+------------+
o Statement: FOR i = 1 TO n |
3. Block 3: Input and Sum Calculation – Inside the loop, the number is read, and the sum Yes / \ No
is updated. v v
o Statement: Read number and sum = sum + number +------------+ +------------+
| Read number| | Print sum |
4. Block 4: Output – The sum is printed after the loop ends. | sum = sum +|---->| END |
o Statement: Print sum | number | +------------+
+------------+
Flow Graph Construction: |
v
+------------+
The flow graph is a representation of the flow of control in the program. Each basic block is | i = i + 1 |
represented as a node, and edges represent the flow between them. +------------+
 | Here, we removed the redundant MOV R2, #5 and used ADD R3, R1, R1 instead, achieving the
v
same result with fewer instructions.
+------------+
| i = 1 to n |
| (Condition)| ii) Elimination of Unreachable Code:
+------------+
Unreachable code refers to parts of the program that cannot be executed due to the flow of
Explanation of Flow Graph Rules: control. These code segments are typically placed after a return, break, or goto statement that
ensures the program will never reach them. Removing such code helps in reducing the program
1. Start Node: Represents the beginning of the program. size and improving performance.
2. Condition Nodes: Used for loops or conditional checks. For example, the loop condition
FOR i = 1 TO n is represented as a decision node. Example: Consider the following code:
3. Action Nodes: Represent the actions being performed, such as reading input, updating
variables, or printing output. int example() {
4. End Nodes: Mark the end of the program or control flow, like the final step where the int a = 5;
return a;
sum is printed. int b = 10; // Unreachable code
}
This flow graph shows how the control flows through different parts of the program, based on
loop conditions and actions performed inside the loop. In the above example, the line int b = 10; is unreachable because the function returns before
it. This line will never be executed, and therefore, it is considered redundant.
Question: Explain the following peephole optimization techniques with examples: i) Elimination
of Redundant Code Optimized Code:
ii) Elimination of Unreachable Code
[7M] int example() {
int a = 5;
return a;
Answer: }

i) Elimination of Redundant Code:

Here, we have removed the unreachable code int b = 10;, as it will never be executed. This
makes the code more efficient and easier to maintain.
Redundant code refers to instructions or operations that produce the same result and do not
contribute to the final output. This code can be removed to improve the efficiency of the program
without affecting its correctness.
Question: Explain briefly about storage organization. [7M]
Example:
Consider the following code:
Answer:
MOV R1, #5
MOV R2, #5 In compiler design, storage organization refers to the method used by a compiler to manage
ADD R3, R1, R2 memory for storing various data such as variables, constants, and intermediate code during the
execution of a program. It involves efficient allocation, tracking, and deallocation of memory.
In the above code, both MOV R1, #5 and MOV R2, #5 are loading the same value into different
registers. Since both registers hold the same value and are used in the ADD instruction, we can There are mainly two types of storage organizations:
remove the second MOV instruction as it is redundant.
1. Static Storage Allocation:
Optimized Code: o In this method, memory is allocated at compile-time, and the size and location of
variables are determined before execution. The variables remain in memory
MOV R1, #5 throughout the program's lifetime.
ADD R3, R1, R1
 o
Example: Global variables in a program are statically allocated. For instance, in a o Constant Propagation: If a variable is assigned a constant value, that value can
C program, a global variable declared outside any function has static storage. be propagated throughout the code wherever the variable is used. For example:
2. Dynamic Storage Allocation: o int a = 5;
o Memory is allocated at runtime, and variables are created and destroyed o int b = a + 10;
dynamically. This allocation is handled through mechanisms like heap memory
and stack memory. After constant propagation, this becomes:
o Example: Local variables inside a function are dynamically allocated on the stack
int b = 15;
during the function's execution and are deallocated once the function exits.
o
Dead Code Elimination: This involves removing parts of the code that do not
Example in Compiler Design: During compilation, the compiler needs to manage both local
affect the program's output. For example, if a variable is assigned a value but is
variables (which are allocated dynamically on the stack) and global variables (which are
never used, it is removed.
statically allocated). For instance, in a function, a local variable int x will be allocated memory
4. Advantages:
on the stack, whereas a global variable int y will be allocated memory statically. o Increased Efficiency: By applying structure-preserving transformations,
compilers generate code that is more efficient in terms of time and space
complexity.
o Reduced Resource Usage: Unnecessary computations and redundant code are
Question: Discuss briefly about Structure Preserving Transformations. [7M] eliminated, reducing the overall size and execution time.

Answer: Example:
In compiler design, Structure Preserving Transformations (SPTs) refer to the techniques used Consider the following code snippet:
to modify the structure of a program while preserving its original semantics (meaning or
behavior). These transformations are crucial during intermediate code optimization phases, int x = 10;
where the goal is to improve the efficiency of the program without changing the output. SPTs int y = x * 2;
maintain the program's logical structure and correctness while optimizing its performance. int z = x + 5;

By applying constant folding and constant propagation, the optimized version can be:
Key points about Structure Preserving Transformations:
int x = 10;
1. Preservation of Semantics: The most important feature of an SPT is that it preserves the int y = 20; // x * 2 is evaluated at compile time
program’s behavior, meaning that after the transformation, the program should still int z = 15; // x + 5 is evaluated at compile time
produce the same output for the same input.
2. Optimization Techniques: These transformations are primarily applied to optimize the
intermediate code generated by the compiler. Optimizations can include removing Q: Describe in detail about Peephole Optimization. What is a flow graph? Explain with a
redundant code, simplifying expressions, and improving control flow. suitable example. [14M]
3. Examples of Structure Preserving Transformations:
o Constant Folding: This optimization involves evaluating constant expressions at Answer:
compile time rather than runtime. For example:
o int x = 3 + 4; Peephole Optimization

This can be transformed to: Peephole optimization is a type of code optimization technique in which a small window or
"peephole" of a few instructions is examined, and the unnecessary or redundant instructions are
int x = 7;
replaced with more efficient ones. This technique is often applied during the code generation
phase of compilers, and it focuses on small-scale improvements that can make a big impact on
The structure of the code remains intact, but the computation is simplified.
performance. The optimization is done by looking at a small set of instructions (usually 3 to 5)
and transforming them into a more optimized form.
Key objectives of Peephole Optimization: Consider the following simple code segment:

 Remove redundant code. 1. x = 10;

 Replace inefficient code with more efficient alternatives. 2. if (x > 5) {
3. y = 20;
 Reduce the size of the code without affecting the logic. 4. } else {
5. y = 30;
Common Peephole Optimizations include: 6. }
7. z = x + y;
1. Constant Folding: If an expression involves constants (e.g., 5 + 3), it can be simplified
to the result (8). The flow graph for the above code would look like this:
2. Dead Code Elimination: Removing code that doesn't affect the program (e.g., setting a
[Start]
variable and never using it). |
3. Sub-expression Elimination: Replacing expressions that appear multiple times with v
their computed value. [x = 10]
4. Strength Reduction: Replacing expensive operations like multiplication or division with |
v
cheaper operations like addition or subtraction.
[if (x > 5)]
/ \
Example of Peephole Optimization: / \
[y = 20] [y = 30]
Before Peephole Optimization: \ /
\ /
[z = x + y]
x = 5 + 3; // Constant Expression |
y = x * 2; // Multiplication v
[End]
After Peephole Optimization:
Explanation:
x = 8; // Constant Folding
y = x + x; // Strength Reduction (multiplication by 2 replaced with
addition)  The graph starts at the instruction x = 10 and follows through to the if statement.
 Depending on the condition x > 5, the control flow splits between the two branches (y =
Flow Graph 20 or y = 30).
 Finally, it reaches z = x + y and ends the program.
A Flow Graph is a directed graph that represents the control flow of a program. It consists of
nodes, where each node represents a basic block of instructions, and edges, which represent the Applications of Flow Graph:
flow of control from one block to another.
1. Control Flow Analysis: Understanding how control flows through a program.
In a flow graph: 2. Loop Detection: Identifying loops in the program for optimization purposes.
3. Reachability Analysis: Finding unreachable code that can be eliminated.
 Nodes represent basic blocks (a sequence of instructions with no branches).
 Edges represent possible execution paths, showing how control can move from one block Question:
to another.
Explain the contents of an activation record with an example.
Flow graphs are used in compilers for optimization and in program analysis to detect loops, dead
code, and unreachable statements. What is an induction variable and identify the induction variables in the following statements in
C:
Example of Flow Graph:
for( i=0,j=1,k=2,l=4 ; i< n ; i++){
j = j + 2;
 k = k + 3;  j, k, and l are not induction variables because they are updated by a fixed amount within
l = l + 4; the loop body but do not change directly with respect to the loop index in a regular, linear
sum = sum + i * j * k;
} fashion. They are modified based on constant values (e.g., j = j + 2).

Answer: Thus, i is the primary induction variable in this loop.

1. Contents of an Activation Record: Question:

An activation record (also known as a stack frame) is a data structure that holds information Consider the following intermediate code statements numbered from 1 to 12:
about a function call. It is created when a function is invoked and destroyed once the function
1 i = 0
execution completes. The activation record contains the following elements: 2 if i < n goto 4
3 goto 11
 Return Address: The address to return to after the function completes. 4 t1 = 4 * i
 Parameters: The values or references passed to the function. 5 t2 = a[t1]
 Local Variables: Variables declared inside the function. 6 t3 = t2 + 1
7 t4 = 4 * i
 Saved Registers: Registers that need to be preserved between function calls. 8 b[t4] = t3
 Control Link: A pointer to the activation record of the calling function (used for stack 9 i = i + 1
unwinding). 10 goto 2
 Data Link: A pointer to the activation record of the currently running function's stack (if 11 t5 = 4 * i
12 b[t5] = 0
needed).

Example: When a function is called, a new activation record is pushed onto the call stack. For (a) Construct a control flow graph for the given code and explain which of the 4 * i computations
instance, in the function int sum(int a, int b), the activation record will store a, b, return in statement 7 and statement 11 are redundant.
address, and any local variables used within the function.

2. Induction Variable:
Answer:
An induction variable is a loop variable that changes in a regular, predictable pattern, typically
incrementing or decrementing by a constant value in each iteration of a loop. Induction variables Control Flow Graph Construction:
help in analyzing the loop behavior and are important in optimization techniques like loop
unrolling. 1. Basic Blocks:
o Block 1: Statement 1.
o Block 2: Statement 2 (condition checking).
Induction Variables in the Given C Code: o Block 3: Statement 3 (goto 11).
o Block 4: Statements 4 to 8 (computation and assignments).
In the given loop:
o Block 5: Statement 9 (increment).
o Block 6: Statement 10 (goto 2).
for( i = 0, j = 1, k = 2, l = 4 ; i < n ; i++) {
j = j + 2; o Block 7: Statement 11.
k = k + 3; o Block 8: Statement 12.
l = l + 4; 2. Control Flow Edges:
sum = sum + i * j * k; o Block 1 → Block 2
}
o Block 2 → Block 3 (if i >= n)
o Block 2 → Block 4 (if i < n)
 i is the induction variable because it is being incremented by 1 in each iteration of the
o Block 4 → Block 5
loop (i++).
o Block 5 → Block 6
o Block 6 → Block 2 (loop continues)
 o Block 3 → Block 7 (exit condition) In static memory allocation, memory is allocated at compile time, and the size and number of
o Block 7 → Block 8 variables are fixed during the program's execution. This approach is not ideal for languages like
C for the following reasons:
Control Flow Graph:
1. Lack of Flexibility: In C, the size of arrays and variables cannot be changed during
+---------+ +---------+ program execution. This is problematic when the exact size of data is not known at
| Block 1| --->| Block 2| compile time. For example, consider a program that processes an unknown number of
+---------+ +---------+
| ^ student records. Using static memory allocation would require the programmer to decide
+------v--+----+ on a fixed array size at compile time, leading to either wasted memory or insufficient
| Block 3 | space.
+--------------+
|
+---------v----------+ +---------+
Example:
| Block 4 |<------| Block 7|
+-------------------+ +---------+ #include <stdio.h>
| ^ | #define MAX_STUDENTS 100
+--v---+----+ +---------v---------+
| Block 5 | -----> | Block 8 | int main() {
+-------------+ +-------------------+ int student_scores[MAX_STUDENTS];
// But if there are only 10 students, the rest of the array is
wasted
return 0;
Redundant Computations of 4 * i: }

The computation 4 * i is performed in Statement 4 and Statement 7. Let’s analyze: In this example, if there are fewer than 100 students, the remaining array memory goes
unused. On the other hand, if there are more than 100 students, the program will not have
1. Statement 4: The expression t1 = 4 * i computes the value of 4 * i for the current enough space, leading to errors.
value of i and stores it in t1. This value is then used in statement 5 (t2 = a[t1]).
2. Statement 7: The expression t4 = 4 * i computes 4 * i again for the same value of i, 2. Wasted Memory: In static allocation, memory for the largest possible case must be
but this time the result is used to update the array b at position b[t4] = t3. reserved. This often leads to wasted memory when the program doesn't require all the
3. Statement 11: The expression t5 = 4 * i computes 4 * i after the loop ends, and this space.
value is used to assign b[t5] = 0. 3. Inability to Handle Dynamic Data: If a program needs to handle dynamic or user-
defined data (like reading an unknown number of user inputs), static allocation fails
Redundancy: because it cannot adjust memory based on runtime conditions.

 The computation of 4 * i in Statement 7 is redundant because the same value (4 * i) Question:

is already computed in Statement 4 during the loop. Instead of recalculating it in
Statement 7, we could reuse the value stored in t1 from Statement 4. Show the contents of the activation record for the function call f(6) where the definition of f is
 The computation in Statement 11 of 4 * i is also redundant, as it is simply the value of given as follows, and f is called from the main function:
i at the end of the loop, which can be reused from previous calculations (i.e., the loop
int f(int n){
counter itself).
if (n == 0)
return 1;
Question: else
return n * f(n-1);
Explain with an example why the static allocation strategy is not appropriate for languages like }
C. [7M]
Answer:
Answer:
When the function f(6) is called, an activation record is created for each recursive call. Each After f(0) returns 1, the previous function calls return one by one, performing the multiplication
activation record stores the following details: at each level:

1. Return address – where the control should go after the function call is completed.  f(1) returns 1 * f(0) = 1 * 1 = 1
2. Parameters – the arguments passed to the function (in this case, n).  f(2) returns 2 * f(1) = 2 * 1 = 2
3. Local variables – any local variables used inside the function (if any).  f(3) returns 3 * f(2) = 3 * 2 = 6
4. Saved registers – storing the values of registers that will be used in the current function  f(4) returns 4 * f(3) = 4 * 6 = 24
call.  f(5) returns 5 * f(4) = 5 * 24 = 120
 f(6) returns 6 * f(5) = 6 * 120 = 720
Let's now break down the recursive calls and show how the activation records look.
Final Activation Record for f(6):
Function Call Stack for f(6):
The activation record for the final call f(6) looks like this:
1. Call to f(6):
o Return Address: Main function (where control should return after f(6) finishes).  Return Address: Main function (to return the result of f(6)).
o Parameter n: 6  Parameter n: 6
o Local Variable: None.  Local Variable: None (no local variables).
2. Call to f(5):  Return Value: 720
o Return Address: To the point where n * f(n-1) is evaluated in f(6).
o Parameter n: 5 Question:
o Local Variable: None.
3. Call to f(4): Explain in detail common sub-expression elimination, copy propagation, and dead code
o Return Address: To the point where n * f(n-1) is evaluated in f(5). elimination optimizations with examples. (7 Marks)
o Parameter n: 4
o Local Variable: None. Answer:
4. Call to f(3):
o Return Address: To the point where n * f(n-1) is evaluated in f(4). Optimizations in compilers aim to improve the efficiency of the generated code. Some of the
o Parameter n: 3 commonly used optimizations are:
o Local Variable: None.
5. Call to f(2): 1. Common Sub-expression Elimination (CSE)
o Return Address: To the point where n * f(n-1) is evaluated in f(3).
o Parameter n: 2 Definition:
o Local Variable: None. Common Sub-expression Elimination (CSE) is an optimization technique that identifies and
6. Call to f(1): eliminates expressions that are computed multiple times. It involves finding expressions that
o Return Address: To the point where n * f(n-1) is evaluated in f(2). appear more than once and replacing them with a temporary variable.
o Parameter n: 1
o Local Variable: None. Example:
7. Call to f(0): Consider the following code:
o Return Address: To the point where n * f(n-1) is evaluated in f(1).
o Parameter n: 0 a = b + c;
o Local Variable: None. d = b + c;
o Base Case Reached: Since n == 0, f(0) returns 1.
Here, the expression b + c is computed twice. With CSE, we can eliminate the redundancy:
Unwinding the Stack:
t = b + c;
a = t;
d = t;  Common Sub-expression Elimination (CSE) reduces repeated calculations by reusing
the results.
By storing the result of b + c in a temporary variable t, we avoid recalculating it.  Copy Propagation eliminates redundant assignments by replacing variables with their
equivalent values.
2. Copy Propagation  Dead Code Elimination removes code that doesn't contribute to the final result.

Definition: 1) Purpose of Live Variable Data Flow Analysis (7 Marks)

Copy Propagation is an optimization where assignments like a = b; are replaced with a
wherever b is used. This helps in eliminating unnecessary assignments and simplifies the code. Live Variable Analysis is a technique used in compilers to determine which variables in a
program hold values that are needed for future computations. A live variable is a variable that
Example: holds a value that may be used in the future (either directly or indirectly). This analysis is
Consider the following code: essential in optimizing programs by eliminating unnecessary computations, such as dead code
elimination, which reduces execution time and memory usage.
a = b;
c = a + 5;
Purpose of Live Variable Analysis:
Here, a is just a copy of b, so we can propagate the value of b directly:
 Dead Code Elimination: Identifies and removes code that does not contribute to the
c = b + 5;
final output, improving performance.
 Register Allocation: Helps in efficient register usage by identifying variables that are no
By replacing a with b, we simplify the code and remove the redundant assignment. longer needed.
 Optimization: Helps in optimizing the program by focusing on the variables that are live
3. Dead Code Elimination
and eliminating those that are not.

Example:
Definition:
Dead Code Elimination is an optimization technique that removes code that does not affect the
Consider the following code:
program's output. This usually involves eliminating unreachable code or instructions that are
never used (e.g., calculations whose results are not used). int a = 10, b = 20, c;
c = a + b;
Example: b = c * 2;
Consider the following code:
In the above code:
a = 5;
b = a + 2;  After the statement c = a + b;, a and b are live because their values will be used in the
c = b + 3;
next computation (b = c * 2;).
 However, the variable a is no longer used after c = a + b;, making it dead in
Now, if c is never used in the program, the code related to c is considered dead code:
subsequent computations. This can be safely eliminated in an optimization step.
a = 5;
b = a + 2; 2) Structure Preserving Transformations (7 Marks)

In this case, c = b + 3; is eliminated because c is not used, and it has no effect on the Structure Preserving Transformations are compiler transformations that change the internal
program's output. representation of the program without altering the program's semantic meaning. These
transformations aim to optimize the program while maintaining its original structure and
Summary: functionality.

Key Points:
  Semantic Integrity: The program's output should remain the same after the
transformation. int main() {
int x = 10, y = 20;
 Efficiency: The transformation aims to improve efficiency, such as reducing the int result = add(x, y);
execution time or memory usage, but the logic of the program should not be affected. return 0;
 Examples of Structure-Preserving Transformations: }
o Loop Unrolling: This transformation reduces the overhead of looping by
replicating the loop body multiple times. In this program:
 Example:
 for (int i = 0; i < 4; i++) {  When add(x, y) is called, memory for the parameters a, b, and the local variable sum is
 a[i] = b[i] + 10; allocated on the stack.
 }
 Once the function add completes, the memory used by these variables is deallocated.
After unrolling: Working of Stack Allocation:
a[0] = b[0] + 10;
a[1] = b[1] + 10; 1. The call to main pushes a new stack frame for main with local variables x, y, and result.
a[2] = b[2] + 10; 2. The call to add(x, y) pushes a new stack frame containing a, b, and sum.
a[3] = b[3] + 10; 3. After add returns, its stack frame is removed, and control returns to main.

o Strength Reduction: Replaces expensive operations with cheaper ones. The stack grows and shrinks as functions are called and return, ensuring automatic memory
 Example: Replacing multiplication by a constant with addition. management for local variables.
 for (int i = 0; i < 10; i++) {
 a[i] = i * 2;
 } (b) Basic Block and Algorithm for Constructing Control Flow Graph:

Transformed to: Basic Block: A Basic Block is a sequence of consecutive statements in a program with a single
entry point and a single exit point. It has no branches (except at the entry and exit points). It is a
for (int i = 0; i < 10; i++) { fundamental unit of control flow in a program.
a[i] = i + i;
} For example, the following code represents a basic block:

(a) Stack Allocation Strategy: int a = 5;

a = a + 1;
printf("%d", a);
Stack Allocation refers to the method of allocating memory in a program during execution. This
strategy uses the stack data structure to allocate memory for local variables and function calls.
The memory for a function’s local variables is automatically allocated when the function is This is a basic block because there are no jumps or branches within this sequence of instructions.
called and deallocated when the function returns.
Control Flow Graph (CFG): A Control Flow Graph (CFG) is a representation of the flow of
In a stack, memory is allocated in a Last In First Out (LIFO) manner, which means that the most control within a program. The nodes represent basic blocks, and the edges represent the flow of
recently called function will have its local variables stored at the top of the stack. control between these blocks.

Example: Algorithm for Constructing Control Flow Graph (CFG):

Consider the following simple program: 1. Identify Basic Blocks:

o Traverse the intermediate code or program, and identify sequences of instructions
int add(int a, int b) { with a single entry and exit point.
int sum = a + b; o Each identified sequence forms a basic block.
return sum; 2. Create Nodes for Basic Blocks:
} o For each basic block, create a node in the CFG.
 3. Connect the Nodes: i) Argue whether the expression a*b is available at statement 6 and statement 8.
o If there is a jump (like goto, if, while, etc.) from one basic block to another,
draw an edge from the current block to the target block. ii) Argue whether the expression b*c is available at statement 5 and statement 9.
o For every function call, an edge should be created from the current block to the
called function block. Intermediate Code:
4. Handle Entry and Exit:
o The entry point of the program has no incoming edges, and the exit point has no 1. x = a*b
outgoing edges. 2. y = b*c
3. if a>20 goto 6
Example: 4. z = a*b
5. w = b*c
Consider the following intermediate code (three-address code): 6. p = a*b
7. a = a+20
1. a = 5
8. q = a*b
2. b = 10
3. if a > b goto L1 9. r = b*c
4. c = a + b
5. goto L2 Answer:
L1: d = a - b
L2: e = c + d
i) Availability of a*b at statement 6 and statement 8:
 Basic blocks can be identified as follows:
o Block 1: a = 5; b = 10  Statement 6 (p = a*b): The expression a*b is available at this point. This is because it is
o Block 2: if a > b goto L1 computed at statement 1 (x = a*b), and no modification to a or b has occurred before
o Block 3: c = a + b statement 6. Therefore, the expression a*b is still available in the previous statements (1
o Block 4: goto L2 and 4), making it available at statement 6.
o Block 5: d = a - b  Statement 8 (q = a*b): The expression a*b is not available here. This is because at
o Block 6: e = c + d statement 7, a is updated with a = a + 20, which modifies the value of a. As a result,
 The control flow graph will be: the expression a*b from earlier (statement 1, 4, or 6) is no longer valid at statement 8
o Block 1 → Block 2 because a has changed.
o Block 2 → Block 3 (if the condition is false)
o Block 2 → Block 5 (if the condition is true) ii) Availability of b*c at statement 5 and statement 9:
o Block 3 → Block 4
o Block 4 → Block 6  Statement 5 (w = b*c): The expression b*c is available at statement 5. This is because it
o Block 5 → Block 6 is computed in statement 2 (y = b*c), and no modification to b or c has occurred before
statement 5. Therefore, the expression b*c from statement 2 is still valid here.
The constructed CFG will look like this:  Statement 9 (r = b*c): The expression b*c is available at statement 9. This is because
no modifications have been made to b or c between statement 5 and statement 9. Thus,
(Entry) → Block 1 → Block 2 → Block 3 → Block 4 → (Exit) the expression b*c from statement 2 and 5 remains valid at statement 9.
→ Block 5 →
In summary:
This graph represents how the program’s control flows, showing the different paths it can take
based on conditions and jumps.
 a*b is available at statement 6 but not at statement 8 due to the update of a in
statement 7.
Question:
 b*c is available at both statement 5 and statement 9 because there were no changes to
b or c between these statements.
Perform available expression analysis on the following intermediate code statements numbered
from 1 to 9.