Matching Practice Questions

This question matches inputs to their corresponding phases in a compiler's front end.
(Q) Character stream: The raw source code is first read as a stream of characters. This is the input to the Lexical Analyzer. This matches (iv).
(S) Token stream: The Lexical Analyzer processes the character stream and groups characters into a sequence of tokens. This token stream is the input to the Syntax Analyzer (Parser). This matches (ii).
(P) Syntax tree: The Syntax Analyzer parses the token stream to create a hierarchical structure like a syntax tree. This tree is then processed by the Semantic Analyzer. This matches (iii).
(R) Intermediate representation: After semantic analysis, the compiler generates an intermediate representation (IR) of the program. This IR is the input to the Code Generator. This matches (i).

The correct pairings between the algorithms and design paradigms are:

• P. Lexical analysis (P) uses Deterministic Finite Automata (DFA), so its optimization involves DFA minimization (II).
• Q. Parsing (Q) generates a production tree (IV) (or parse tree) to represent the syntactic structure of the code.
• R. Register allocation (R) is a classic problem that can be modeled and solved using graph coloring (I).
• S. Expression evaluation (S), especially for expressions in postfix or prefix form, is efficiently done using a post-order traversal (III) of the expression tree.

Here's the step-by-step matching:

• P. Regular expressions are fundamental for defining patterns of tokens during the lexical analysis phase of a compiler. Thus, P matches with 3 (Lexical analysis).
• Q. Pushdown automata are theoretical models used to recognize context-free languages, which describe the syntax of most programming languages, making them relevant to syntax analysis (parsing). Thus, Q matches with 1 (Syntax analysis).
• R. Dataflow analysis is a technique employed by compilers to gather information about the possible set of values computed by a program, which is crucial for performing various code optimizations. Thus, R matches with 4 (Code optimization).
• S. Register allocation is the process of assigning variables to CPU registers to minimize memory access, a key task performed during the code generation phase to produce efficient machine code. Thus, S matches with 2 (Code generation).

Combining these matches: P-3, Q-1, R-4, S-2. This corresponds to option B.

(A) An Activation record (stack frame) is created during a subroutine call to store local variables, return addresses, and parameters, matching (3).
(B) A Location counter is used by an Assembler to track the memory address of the instruction being assembled, matching (4).
(C) Reference counts are a memory management technique employed in Garbage collection to track active references to objects, matching (2).
(D) Address relocation is performed by a Linking loader to modify machine code addresses to reflect the program's actual memory location, matching (1).
Combining these mappings, the correct sequence is A-3, B-4, C-2, D-1.

Applicable optimizations: LICM: x = y + z does not depend on i or any variable modified in the loop - it is loop-invariant. Move it before the loop. xx is also loop-invariant after moving x - it can also be moved before the loop (let xx = xx). Strength reduction: 6i is a linear function of induction variable i. Replace with induction variable t = 6i, initialized to 6 before loop, incremented by 6 each iteration. Result: x=y+z; xx=x*x; t=6; for(i=1;i<=10;i++){a[i]=t+xx; t=t+6;}. Now i is only used to control the loop count; further induction variable elimination could replace the i-based exit condition with t>60 and eliminate i entirely.

Next-use information (liveness information within a basic block): variable x has a next use at instruction p if there exists a subsequent instruction q (q > p) in the same basic block that uses x as an operand, with no definition of x between p and q. Next-use information is computed by scanning the basic block backward. It is used during code generation to decide register allocation - if a variable has no next use, its register can be freed immediately after the current instruction. A variable with no next use at the end of a basic block is dead and its register can be reused.

getReg strategies for selecting a register for result x in instruction x = y op z: Use y's register if y dies here (no next use) - avoids an unnecessary copy. Use an empty register - straightforward, no spill needed. Spill: if no register is free, choose a register R to spill - store R's value to memory (if not already there), update address descriptor, and use R for x. The choice of which register to spill uses heuristics: prefer registers whose next use is furthest away (Belady's optimal), or registers whose values are already in memory (no store needed). D is wrong - always using R0 would cause incorrect results when R0 is needed for another operand.

Strength reduction replaces expensive operations with cheaper equivalents: A: Introduces induction variable t starting at 0, incremented by 4 each iteration - replaces multiplication i*4 with addition t+4 (additions are cheaper than multiplications). This is the classic strength reduction. B: Replaces multiplication by 4 (power of 2) with a left shift by 2 bits (i<<2) - on most architectures, shifts are cheaper than multiplications. Both are valid: A eliminates multiplication entirely (using addition), B replaces multiplication with shift (machine-dependent). In practice, modern compilers may use both: A for induction variable optimization, B as a machine-level optimization.

https://www.youtube.com/watch?v=IUAIytbb2mw&t=16236s https://www.youtube.com/watch?v=oBAqib3LDi4&t=6756s

A DAG (Directed Acyclic Graph) for a basic block represents computations, sharing nodes for common subexpressions. b+c appears twice (Node 1: a=b+c and Node 3: f=b+c). In the DAG, both a and f point to the same node representing b+c - only one addition is computed. Similarly, a-e and f-e: since a and f have the same value (both = b+c), they also share a node in the DAG. So: 1 addition (b+c, shared by a and f), 1 subtraction (b+c-e, shared by d and g). Total additions = 1.

Strength reduction replaces expensive operations (multiplication) with cheaper ones (addition) for induction variables in loops. Here i is an induction variable (incremented by 1 each iteration), so t1 = i * 4 is a linear function of i. Strength reduction introduces a new induction variable t1 initialized to i4 before the loop and incremented by 4 (= 14) each iteration: t1 = t1 + 4. This replaces the multiplication in every iteration with a single addition, which is faster. After strength reduction, i itself may become dead (if only used to compute t1) and can be eliminated by dead code elimination.

Common Subexpression Elimination (CSE) identifies expressions that are computed multiple times with the same values and replaces subsequent computations with the previously computed result. Here, t1 = a + b and t2 = a + b are identical expressions (a and b unchanged between them). CSE replaces t2 = a + b with t2 = t1 (or equivalently uses t1 in place of t2). Since t2 = t1, t3 = t1 * t2 becomes t3 = t1 * t1. Optimized: t1 = a + b; t3 = t1 * t1 - saves one addition.

Constant propagation replaces uses of variables with their known constant values. Constant folding then evaluates the resulting constant expressions: x = 5 (x is a constant 5). y = x + 3: propagate x=5 → y = 5 + 3; fold → y = 8. z = y * 2: propagate y=8 → z = 8 * 2; fold → z = 16. Result: x=5, y=8, z=16. Option B (z=16 only) would be correct only after further dead code elimination if x and y are not used elsewhere. Without knowing whether x and y are used after, the conservative answer is A.

Three-address code restricts each instruction to at most one operator and three addresses (two operands and one result). The expression a = b * c + b * d is broken into: t1 = b * c (multiply), t2 = b * d (multiply), a = t1 + t2 (add). Each instruction has exactly one operator and at most three addresses. Option B has two operators in one instruction. Option C computes the whole expression in one instruction. Option D is an equivalent but different expression (uses distributive law).

Dead code examples: A: TRUE - if a variable x is assigned but never read afterward (dead assignment), the assignment is useless and can be removed. Detected using liveness analysis (variable is not live after the assignment). B: TRUE - code after an unconditional jump (goto, return, break) can never be executed - it is unreachable and can be eliminated. D: TRUE - a function never called anywhere contributes no useful computation and its code can be removed (requires interprocedural analysis). C: FALSE - a conditional branch whose condition is always true is not dead code itself; the branch becomes an unconditional jump (the false branch becomes dead code). The branch instruction itself is 'live' - it controls program flow.

Peephole optimization examines a small sliding window of generated instructions and replaces them with shorter or faster equivalents: Redundant load/store elimination: if R is stored to x and immediately loaded back from x, the load is unnecessary. Algebraic simplification: x+0=x, x1=x, x0=0 - the instruction can be deleted or simplified. Strength reduction: multiplication by power of 2 → left shift (faster); division by power of 2 → right shift. Unreachable code: instructions after unconditional jumps can never execute - they are dead code and can be deleted. Peephole optimization is applied to a small window (typically 2-5 instructions) of target code.

An induction variable (IV) in a loop is a variable whose value changes by a constant amount (possibly zero) each loop iteration. The basic induction variable is the loop counter (e.g., i in for(i=0;i<n;i++)). A derived induction variable is a linear function of a basic IV: if i is a basic IV with increment 1, then j = 4*i + 5 is a derived IV (changes by 4 each iteration). After strength reduction creates derived IVs, induction variable elimination removes the original basic IV if it is used only to compute derived IVs and for the loop termination test. The termination test can be rewritten in terms of the derived IV.

Given is Load Store Architecture, that means we can access memory using Load and Store Instructions. Key Idea:- Pick new register only when it is required. We want to add c and d , and initially both are in memory, therefore copy these into registers. load $R1, c$ $(R1 \leftarrow c)$ load $R2, d$ $(R2 \leftarrow d)$ (here no compensation can be done, we need two registers) add $R1, R1, R2 \ ( R1 \leftarrow R1 + R2)$ (at this point $R1$ is holding $\mathbf{c+d}$ and $R2$ is holding $\mathbf{d}$, i.e. $R1 \leftarrow \mathbf{c+d}$ and $R2 \leftarrow \mathbf{d})$ Now, $\mathbf{e}$ comes into picture and my question is, Can i make use of $R1$ or $R2$ to store $\mathbf{e}$? I can not use R1 to store e as its value will be needed later but I can use R2. load $R2, e$ (currently $R1 \leftarrow \mathbf{c+d}$ and $R2 \leftarrow \mathbf{e})$ Sub $R1, R2, R1$ $(R1 \leftarrow R2 - R1)$ Doing this all gives, final value of right sub-tree is stored in $R1$, and $R2$ stores $\mathbf{e}$. Now, coming to left subtree, to perform "$a-b$" we need to copy both variables in registers. We can copy one of the variable in $R2$, but we can not obviously copy in $R1$ as value of $R1$ will be required later. Load $R2, a$ Load $R3, b$ ( here comes extra register, and we can not avoid using it .) Current mapping is $R2 \leftarrow a$, $R3 \leftarrow b$ and $R1$ contains final value of Right subtree. SUB $R2, R2, R3 (R2 \leftarrow R2 - R3)$ ADD $R1, R1 , R2$ Hence answer is $3$ i.e. D

Register allocation is equivalent to graph coloring: an interference graph is constructed where each node represents a variable (or live range) and an edge connects two variables that are simultaneously live (interfere - cannot share a register). Register allocation then assigns registers to variables such that no two interfering variables get the same register - this is exactly k-coloring (where k = number of available registers). If the graph cannot be k-colored, some variables must be spilled to memory. Graph coloring is NP-complete in general, so heuristics (Chaitin's algorithm) are used.