Intermediate Code Generation Practice Questions

An expression is redundant if it is computed on all paths reaching the block and its operands are not modified since the previous computation.

1. Block $B4$: The expression $g * k$ is computed in both predecessors $B2$ and $B3$ with no intervening modifications, making it redundant. The expression $b + i$ is computed in $B1$, but the assignment $b = c + m$ in $B3$ redefines $b$, so $b + i$ is not available on all paths reaching $B4$. Thus, $B4: \{g * k\}$.
2. Block $B5$: The expression $c + m$ is computed in $B3$, but it is not computed on the path through $B2 \to B4$. Since it is not available on all paths reaching $B5$, it is not redundant. Thus, $B5: \{ \}$.

This matches option D.

Live variable analysis determines which variables might be used again before being overwritten. This information is crucial for optimizing how registers are utilized. By knowing which variables are "live" (i.e., still needed), the compiler can assign frequently accessed live variables to registers, minimizing memory access and improving performance.

To determine the number of basic blocks, we identify the leader statements, which are:

1. The first statement (1001: $i = 1$).
2. Any statement that is the target of a conditional or unconditional jump (e.g., 1003, 1002, 1013).
3. Any statement immediately following a conditional or unconditional jump (e.g., 1010, 1012).

Based on these rules, the leaders are:

• 1001 (first statement)
• 1002 (target of goto 1002 and immediately after goto 1003)
• 1003 (target of goto 1003)
• 1010 (immediately after goto 1003)
• 1012 (immediately after goto 1002)
• 1013 (target of goto 1013)

The basic blocks are formed by consecutive statements starting from a leader up to, but not including, the next leader, or up to a jump statement. This gives us 6 basic blocks:

1. (1001)
2. (1002)
3. (1003-1009)
4. (1010-1011)
5. (1012)
6. (1013-1017)
   [CORRECT_OPTION: 6]

Backpatching is a technique used in compilers for generating code, particularly for control flow statements and Boolean expressions, in a single pass.
Let's analyze the given statements:
(I) Backpatching can be used to generate code for Boolean expression in one pass.
This statement is TRUE. Backpatching is commonly employed for Boolean expressions where the target of a jump (true or false) is not known until later in the parsing process. Instead of generating a fixed jump, a placeholder is created and "backpatched" with the correct target address once it's determined.

(II) Backpatching can be used to generate code for flow-of-control statements in one pass.
This statement is TRUE. Similar to Boolean expressions, control flow statements like if-else, while loops, etc., often involve jumps whose targets are not known at the time the jump instruction is initially generated. Backpatching allows generating a placeholder jump and filling in the correct target address later, enabling single-pass code generation for these constructs.

Since both statements (I) and (II) are TRUE, option (C) is correct.

The expression is $x[i] = (p+r) * -s[i] + u/w$.
Let's break it down into triples using the given structure. A triple is (operator, operand1, operand2).
(0) is + p r. This calculates p+r.
(1) is empty. It should calculate -s[i].
(2) is uminus (1). This is the unary minus operation on the result of (1).
(3) is empty. It should calculate (p+r) * (-s[i]).
(4) is / u w. This calculates u/w.
(5) is + (3) (4). This calculates ((p+r) * (-s[i])) + (u/w).
(6) is empty. It should be the assignment.
(7) is = (6) (5). This should assign the result of (5) to x[i]. Thus (6) should be x[i].

Let's fill in the missing triples:
Triple (1): This should calculate s[i]. In triple form, accessing an array element s[i] would be s i. So, (1) = [] s i.
Triple (3): This should calculate the multiplication (p+r) * (-s[i]). This uses the results of (0) and (2). So, (3) = * (0) (2).
Triple (6): This is the left-hand side of the assignment x[i]. So, (6) = [] x i.

Comparing with the options:
Option A:
(1) $=[] s i$ (correct)
(3) * (0) (2) (correct)
(6) $=[] x i$ (correct)

All parts of option A match our derivation.
===END_Q43===

To determine basic blocks, we identify the leader statements. A leader statement is:

1. The first statement of the program. (L1)
2. Any statement that is the target of a conditional or unconditional jump. (L4, L11, L3, L3 (L14 points to L3))
3. Any statement immediately following a conditional or unconditional jump. (L10 for jump at L9, L13 for jump at L12, L15 for jump at L14)

Let's list the leaders and their basic blocks:
L1: t1 = -1 (Leader by rule 1)
Block B1: L1, L2, L3
(L3 is a target of L14 but already part of B1. The block ends before L4 due to L12 being a jump to L4)
L4: t4 = 4 * t3 (Leader by rule 2 (L12))
Block B2: L4, L5, L6, L7, L8
(Block ends before L9 which is a conditional jump)
L9: if t8 <= max goto L11 (Jump statement, so next statement is a leader)
Block B3: L9
L10: t1 = t8 (Leader by rule 3 (L9))
Block B4: L10
(Block ends before L11 which is a jump target)
L11: t3 = t3 + 1 (Leader by rule 2 (L9))
Block B5: L11
(Block ends before L12 which is a conditional jump)
L12: if t3 < M goto L4 (Jump statement, so next statement is a leader)
Block B6: L12
L13: t2 = t2 + 1 (Leader by rule 3 (L12))
Block B7: L13
(Block ends before L14 which is a conditional jump)
L14: if t2 < N goto L3 (Jump statement, so next statement is a leader)
Block B8: L14
L15: max = t1 (Leader by rule 3 (L14))
Block B9: L15

Let's refine the basic blocks by grouping non-jump instructions between leaders:
Leaders: L1, L4, L9, L10, L11, L12, L13, L14, L15 (9 leaders)

This structure is complex, let's simplify based on control flow:

L1: t1 = -1
L2: t2 = 0
L3: t3 = 0
(Block 1: L1-L3 -> 3 statements)
. L4: t4 = 4 * t3
. L5: t5 = 4 * t2
. L6: t6 = t5 * M
. L7: t7 = t4 + t6
. L8: t8 = a[t7]
(Block 2: L4-L8 -> 5 statements)
. L9: if t8 <= max goto L11
(Block 3: L9 -> 1 statement)
. L10: t1 = t8
(Block 4: L10 -> 1 statement)
. L11: t3 = t3 + 1
(Block 5: L11 -> 1 statement)
. L12: if t3 < M goto L4
(Block 6: L12 -> 1 statement)
. L13: t2 = t2 + 1
(Block 7: L13 -> 1 statement)
. L14: if t2 < N goto L3
(Block 8: L14 -> 1 statement)
. L15: max = t1
(Block 9: L15 -> 1 statement)

The flow graph has 9 basic blocks based on the rules.
The largest basic block is Block 2 (L4-L8) with 5 instructions.

The solution in the PDF shows 7 basic blocks (B1 to B7) and the largest block (B2) containing statements L4-L9.
Let's re-evaluate based on the PDF's flow graph interpretation.
B1: L1, L2
B2: L3
B3: L4, L5, L6, L7, L8, L9 (This seems to group L9 with previous statements as a block, which isn't standard, as L9 is a conditional jump)
B4: L10
B5: L11, L12
B6: L13, L14
B7: L15

If we follow the solution's block diagram:
B1 (L1, L2): 2 statements
B2 (L3): 1 statement
B3 (L4-L9): L4, L5, L6, L7, L8, L9 (6 statements) - This seems to be the largest.
B4 (L10): 1 statement
B5 (L11, L12): 2 statements
B6 (L13, L14): 2 statements
B7 (L15): 1 statement

Number of basic blocks = 7.
Largest basic block is B3, with 6 statements (L4 through L9).
This matches option (d) from the solution.

The typical definition of a basic block is a sequence of instructions where control enters at the beginning and leaves at the end without halting or branching except at the end. L9 is a conditional branch, so it should be the end of a block. If L9 is part of B3, it implies that the instructions L4-L8 are always executed sequentially, and then L9 is executed. If L9 is considered the end, the block size is 6.

So, 7 basic blocks and the largest block contains 6 instructions.

The question asks about the correctness of statements regarding the front-end and back-end of a compiler.
S1: The front-end includes phases that are independent of the target hardware. This is TRUE. The front-end (lexical analysis, syntax analysis, semantic analysis, intermediate code generation) primarily deals with the source language and generates an intermediate representation, which is machine-independent.
S2: The back-end includes phases that are specific to the target hardware. This is TRUE. The back-end (code optimization, code generation) takes the intermediate representation and translates it into machine-specific code, optimizing it for the target architecture.
S3: The back-end includes phases that are specific to the programming language used in the source code. This is FALSE. The back-end works on the intermediate representation, which is language-independent. The language-specific aspects are handled by the front-end.
Therefore, only S1 and S2 are TRUE.

The code segment performs calculations involving x, y->f1, y->f2, p, q, and i.
Common Sub-expression Elimination (CSE) identifies and replaces redundant computations.
Initial calculations:
t1 = y->f1 (1 dereference)
t2 = y->f2 (1 dereference)
t3 = x + 3 (1 addition)
z = t3 + t1 + t2 (2 additions)

Total initial dereferences = 2.
Total initial additions = 3.

Loop for (i = 0; i < 200; i = i + 2): This loop runs for $200/2 = 100$ iterations.
Inside the loop, either the if block or the else block executes.
if (z > i):
p = p + x + 3; (1 addition, x+3 is t3, so p = p + t3)
q = q + y->f1; (1 addition, y->f1 is t1, so q = q + t1)
else:
p = p + y->f2; (1 addition, y->f2 is t2, so p = p + t2)
q = q + x + 3; (1 addition, x+3 is t3, so q = q + t3)

In each iteration, two additions are performed.
Total additions in loop = $100 \times 2 = 200$.
Total dereferences in loop = 0 (since y->f1 and y->f2 are replaced by t1 and t2).

Total additions = (initial additions) + (loop additions) = $3 + 200 = 203$.
Total dereferences = (initial dereferences) + (loop dereferences) = $2 + 0 = 2$.

The number of addition and dereference operations are 203 and 2, respectively.

Intermediate representations are data structures used by compilers to represent the source code in a form that is easier to analyze and transform.

• Three address code (TAC) is a linear intermediate representation.
• Abstract Syntax Tree (AST) is a structural intermediate representation.
• Control Flow Graph (CFG) is a structural intermediate representation.
• A symbol table is a data structure that stores information about identifiers (variables, functions, etc.) in the source code, but it is not an intermediate representation of the program's structure or logic itself. It supports the phases of compilation.
  Therefore, the symbol table is NOT an intermediate representation.

Compiler-based out-of-order execution refers to static scheduling techniques that reorder instructions to maximize functional unit utilization. Unlike loop unrolling, which expands loops, dead code elimination, which removes unreachable instructions, or strength reduction, which simplifies algebraic operations, software pipelining specifically restructures loops. It achieves parallelism by interleaving instructions from different iterations, such as performing the load for iteration $i+1$ while iteration $i$ performs its computation. This effectively changes the relative order of instruction execution, functioning as a static form of out-of-order scheduling.

To determine if a grammar is L-attributed, all inherited attributes on the right-hand side of a production must be defined by either inherited attributes of the non-terminal on the left-hand side or by synthesized/inherited attributes of non-terminals to its left.

Let's analyze Rule 1: $A \rightarrow PQ$

1. $P.i = A.i + 2$: $P.i$ is an inherited attribute of $P$, defined using $A.i$ (inherited attribute of the LHS). This is valid.
2. $Q.i = P.i + A.i$: $Q.i$ is an inherited attribute of $Q$, defined using $P.i$ (an attribute of a symbol to its left, $P$) and $A.i$ (inherited attribute of the LHS). This is valid.
3. $A.s = P.s + Q.s$: $A.s$ is a synthesized attribute of $A$, defined using $P.s$ and $Q.s$ (synthesized attributes of symbols on the RHS). This is valid.
   Since all rules in Rule 1 satisfy the conditions, Rule 1 is L-attributed.

Now, let's analyze Rule 2: $A \rightarrow XY$

1. $X.i = A.i + Y.s$: $X.i$ is an inherited attribute of $X$, defined using $A.i$ (inherited attribute of the LHS) and $Y.s$ (synthesized attribute of a symbol to its right, $Y$). This violates the condition for L-attributed grammars, as $Y.s$ is not available when $X.i$ is being computed in a left-to-right pass.
2. $Y.i = X.s + A.i$: $Y.i$ is an inherited attribute of $Y$, defined using $X.s$ (synthesized attribute of a symbol to its left, $X$) and $A.i$ (inherited attribute of the LHS). This is valid.

Since $X.i = A.i + Y.s$ violates the L-attributed definition, Rule 2 is not L-attributed.

Therefore, only Rule 1 is L-attributed.

The final answer is $\boxed{B}$

Peep-hole optimization is a technique that examines a small, contiguous window of machine code instructions to improve execution efficiency. By identifying patterns such as redundant loads, stores, or unnecessary jumps within this limited "peephole," it replaces them with more efficient instruction sequences. Because these local replacements can often expose further optimization opportunities in adjacent code, the process is applied repeatedly (iteratively) until no further improvements are possible. Thus, it is inherently local in scope and iterative in application.

The minimum number of registers required to evaluate an expression tree without spills can be determined using the Sethi-Ullman algorithm. We assign a number to each node, representing the registers needed for its subtree.
The expression is (a-1) * (((b+c)/3) + d).

1. For the subtree (b+c), both b and c are variables, needing 1 register each. Since the register needs are equal, the result (b+c) needs $1+1=2$ registers.
2. For (b+c)/3, the left side needs 2 registers and the right side (constant 3) needs 0. The result needs max(2,0) = 2 registers.
3. For ((b+c)/3) + d, the left side needs 2 registers and d needs 1. The result needs max(2,1) = 2 registers.
4. For (a-1), a needs 1 register and 1 needs 0. The result needs max(1,0) = 1 register.
5. For the final multiplication, the left side needs 1 register and the right side needs 2. The entire expression needs max(1,2) = 2 registers.
   Thus, the minimum number of registers required is 2.

Static Single Assignment (SSA) form is an intermediate representation property where every variable is assigned a value exactly once. In the given three-address code, variables p and q are reassigned. To convert to SSA, each new assignment must be to a new, uniquely named variable.
The correct transformation is:

1. p = a - b becomes p_3 = a - b.
2. q = p * c becomes q_4 = p_3 * c, using the new p_3.
3. p = u * v becomes p_4 = u * v.
4. q = p + q becomes q_5 = p_4 + q_4, using the new p_4 and the previous q_4.
   Option B correctly reflects this principle, assigning each result to a new variable.

Peephole optimization examines a small, contiguous segment of target machine code, known as a "peephole." Because this technique restricts its analysis to this limited window of instructions rather than the entire control flow graph, it does not account for global program behavior. Operating within this small scope to achieve local improvements in code speed or size classifies it as a form of local optimization. In contrast, global or loop optimizations require analyzing the entire program structure, which is outside the scope of simple peephole methods. Therefore, based on its narrow, window-based operational scope, peephole optimization is definitively categorized as local optimization.

This solution is based on standard textbook concepts as the PDF provides only the final answer.

In Static Single Assignment (SSA) form, each variable is assigned a value exactly once. The original code has 5 input variables (u, t, v, w, z) and uses two other variables (x, y) for intermediate calculations.

The sequence of operations can be represented in a three-address code format, which is closely related to SSA. We need variables to hold the 5 inputs and at least two additional temporary variables (or registers) to store the intermediate results of calculations without overwriting the inputs. Therefore, a minimum of 5 + 2 = 7 total variables are required.

A control-flow graph (CFG) represents the flow of control in a program. Nodes are basic blocks (sequences of straight-line code), and edges represent jumps.
The given code can be partitioned into 6 basic blocks (nodes):

1. Lines (1)-(2): Initialization
2. Lines (3)-(8): Inner loop body
3. Line (9): Inner loop condition
4. Line (10): Outer loop increment
5. Line (11): Outer loop condition
6. An implicit exit block.
   Tracing the flow gives 7 edges: an entry edge, two forward edges for loop entries, two back-edges for the loops, and two edges for exiting the loops. The PDF diagram shows 6 nodes and 7 edges.

To create a three-address code in Static Single Assignment (SSA) form, each intermediate result must be stored in a new, unique temporary variable. The expression is q + r/3 + s - t*5 + u*v/w. We can break it down as follows:

1. t1 = r / 3
2. t2 = t * 5
3. t3 = u * v
4. t4 = t3 / w
5. t5 = q + t1
6. t6 = t5 + s
7. t7 = t6 - t2
8. t8 = t7 + t4

This sequence requires 8 distinct temporary variables (t1 through t8) to hold each intermediate result, satisfying the SSA requirement that each variable is assigned only once.

A variable is "live" at a statement if its current value may be used in a subsequent path before it is reassigned. We need to find the variables that are live at the start of both basic block 2 and basic block 3.

Live variables at the start of Block 2 (v=r+u):

• r and u are used in this block, so they are live.
• The value of r is also used later in block 4 (q=v+r), and there is a path from block 2 to 4 without r being redefined.

Live variables at the start of Block 3 (q=s*u):

• s and u are used in this block, so they are live.
• The value of r is used in block 4, and there is a path from block 3 to 4 without r being redefined. So, r is also live here.

The set of variables live at the start of block 2 is {r, u}. The set of variables live at the start of block 3 includes {r, s, u, v}. The intersection of these sets, representing variables live at both points, is {r, u}.

The number of successors for a node in both an AST and a CFG is determined by the program's control structures. For example, an if-then-else statement creates a node with two successors in a CFG, while a simple sequential statement has one. Thus, the structure depends on the input program.

Option A is false because in a CFG, a loop or a goto statement can cause the code for a successor node N2 to appear before its predecessor N1. Option B is false because a CFG will contain a cycle if the program has loops.