Matching Practice Questions

Loop unrolling replicates the loop body k times and adjusts the loop counter: Benefits: A: TRUE - loop overhead (branch, counter update) is amortized over k original iterations - for a 4× unroll, loop overhead is reduced by 4×. B: TRUE - multiple iterations of independent computations in the unrolled body can execute in parallel (using multiple execution units or SIMD). C: TRUE - with multiple iterations inline, the compiler sees more code in one basic block, enabling more aggressive CSE, register allocation, and scheduling. D: FALSE - unrolling INCREASES code size by replicating the body. This is a trade-off: speed vs code size. Excessive unrolling can harm instruction cache performance.

An expression e (e.g., a+b) is available at point p if: (1) On every path from the program entry to p, e has been computed at least once, AND (2) On every such path, after the last computation of e, none of the variables in e (a or b) have been redefined (which would change e's value). Available expressions analysis is used for CSE: if e is available at a point where e is being computed, the computation can be replaced by a reference to the previously computed value. It is a forward, must analysis (conservative - requires the expression on ALL paths, not just some). GEN[B] = expressions computed in B with operands not subsequently redefined. KILL[B] = expressions with an operand defined in B.

r, u. p, and s are assigned to in $1$ and there is no intermediate use of them before that. Hence p, and s are not live in both $2$ and $3$. q is assigned to in 4 and hence is not live in both $2$ and $3$. v is live at $3$ but not at $2$. u is live at $3$ and also at $2$ if we consider a path of length $0$ from $2 - 2$. So, r, u is the answer.

With 2 registers and 4 instructions, trace through code generation: (1) t1 = ab: Load a→R0, load b→R1 (or use memory), compute R0=ab. t1 in R0. (2) t2 = t1+c: t1 in R0, need c (load into R1), R1=R0+R1=t1+c. t2 in R1. t1 still needed (used in instruction 3). Registers: R0=t1, R1=t2. (3) t3 = t1d: Need t1 (in R0) and d. But t2 (in R1) is needed in instruction 4. Load d - need a register. Both R0 (t1, needed) and R1 (t2, needed) are occupied. Must spill one. Spill t2 to memory (1 STORE), use R1=t1d=t3. (4) e = t2+t3: Reload t2 from memory (1 LOAD), compute R0=t2+t3=e. Minimum spills = 1 STORE instruction.

Eventhough this is answered well, I post this to emphasize the initialization of Basic Block B2 which I have shown below.

Note that initialization of $\text{DEF}[B_2]=\phi$ and not $\cancel{\text{DEF}[B_2]=\left \{i, j\right\}}$ See $\text{Example 9.13 : B2 does not define i or j, since they are used before definition}$. More importantly this is corrected statement in errata of the Compilers by Aho, 2nd edition Pass 4 is same as Pass 3 and so the answer is OPTION (D)

Code optimizations are classified along two dimensions: (1) Machine independence - Machine-independent optimizations (CSE, constant folding, dead code elimination) work on IR without knowledge of target hardware. Machine-dependent optimizations (register allocation, instruction scheduling, peephole) exploit target-specific features. (2) Scope - Local optimizations work within a single basic block (simple, fast). Global optimizations work across basic blocks within a function using dataflow analysis. Interprocedural optimizations work across function boundaries (most powerful, most expensive).

Reaching definitions: a definition d (an assignment to variable x at some program point) reaches program point p if there exists a path through the control flow graph from d to p along which x is not redefined (killed). In other words, the value assigned by d could potentially reach p. Reaching definitions is a forward dataflow problem: information flows in the direction of program execution. Used for: constant propagation (is the reaching definition a constant?), use-def chains, copy propagation. GEN[B] = definitions in block B. KILL[B] = definitions killed by B (same variable redefined in B). Equation: OUT[B] = GEN[B] ∪ (IN[B] − KILL[B]); IN[B] = ∪ OUT[P] for predecessors P.

May vs Must analysis: May analysis (optimistic for existence): a property is conservatively reported if it holds on at least one path. Uses UNION at join points (if any predecessor has the property, the join point may have it). Example: reaching definitions (a definition may reach a point if it reaches on some path). Must analysis (conservative for certainty): a property is reported only if it holds on ALL paths. Uses INTERSECTION at join points (all predecessors must have the property). Example: available expressions (an expression is available only if computed on every path - must analysis). B is reversed - may uses union, must uses intersection. Liveness: may analysis (backward) - variable is live if there is some path to a use.

Copy propagation: after a copy assignment x = y, substitute y for subsequent uses of x (as long as neither x nor y is redefined between the copy and the use). Example: t1 = a + b; x = t1; z = x * c → after copy propagation: z = t1 * c (x replaced by t1). This eliminates the copy x = t1 if x has no other uses, enabling dead code elimination of the copy. Copy propagation is often combined with constant propagation and dead code elimination in an iterative pass over the IR. It reduces the number of variables, potentially reducing register pressure.

In the simple code generator for basic blocks: Register descriptor: for each register R, maintains the set of variable names whose current value is in R. Initially all registers are empty. Updated after each instruction. Address descriptor: for each variable x, maintains the set of locations (registers and/or memory locations) where the current value of x can be found. A variable's value may be in a register only, memory only, or both (if it has been stored). These two descriptors together allow the code generator to decide: which register to use for a new computation, when a register is safe to reuse, and whether a store instruction is needed before reusing a register.

For CSE, an expression E at point p is a common subexpression if: (1) E was previously computed at some earlier point q in the program, (2) The values of all variables in E are the same at both p and q (i.e., none have been redefined between q and p). If both conditions hold, the computation at p is redundant - it produces the same value as the computation at q, which can be saved in a temporary. B is wrong - it can appear more than twice. C is wrong - CSE applies globally, not just in loops. D is partially relevant but not strictly required - it applies to expressions with defined values regardless of side effects (pure expressions like array indexing without bounds check side effects).

Dataflow analysis direction: Forward analyses (entry → exit): Reaching definitions - where a definition can reach (flows forward). Available expressions - whether an expression has been computed and not invalidated (flows forward). Backward analyses (exit → entry): Liveness analysis - whether a variable's value will be used (flows backward from uses). Very busy expressions - an expression is very busy at a point if it will be computed on every path from that point (flows backward from computations). The direction matches the direction of information flow - backward analyses reason about 'what will happen in the future' (which requires looking backward from exits).

Function inlining replaces a function call with the body of the callee: Benefits - A: TRUE - eliminates call overhead: no need to save/restore registers, set up activation record, execute call/return instructions. For small frequently-called functions, this overhead can dominate. B: TRUE - after inlining, the caller and callee code are in the same basic block scope, enabling optimizations that cross call boundaries: CSE, constant propagation of arguments, dead code elimination of unused return values. Costs - D: TRUE - inlining increases code size (the callee body is duplicated at each call site). This can hurt instruction cache performance. Also increases register pressure - the combined code needs registers for both caller and callee variables. C: FALSE - inlining increases code size for functions called multiple times; only decreases if the call overhead code itself is larger than the function body.

Optimization and code generation relationship: A: TRUE - optimization occurs at multiple levels: IR-level (machine-independent: CSE, constant folding, dead code elimination, loop optimizations) before code generation, and peephole optimization on the target code after generation. B: FALSE - naive code generation produces correct but often suboptimal code; optimizations are crucial for performance. C: TRUE - machine-independent optimizations on IR don't depend on target architecture specifics (register count, instruction set) and are applied before code generation. D: TRUE - machine-dependent optimizations like instruction selection (choosing target instructions), register allocation (target-register-count-specific), and instruction scheduling (target-pipeline-specific) are inherently part of or after the code generation phase.

Loop-invariant code motion (LICM) identifies expressions inside a loop whose values do not depend on any variable that changes during the loop (loop-invariant expressions) and moves them to the loop preheader (a block executed once before the loop). Example: for(i=0;i<n;i++) { a[i] = xy + z; } - if x, y, z are not modified in the loop, t=xy+z is loop-invariant and can be moved before the loop, computing it once instead of n times. Conditions for safe hoisting: the expression must dominate all loop exits (or the loop always executes at least once), and the variables it reads must not be defined within the loop.

Value numbering: Local value numbering (LVN): assigns value numbers within a single basic block. Two expressions get the same value number if they provably compute the same value within the block. Detects local CSE opportunities. Global value numbering (GVN): extends value numbering across the entire function's CFG using SSA form. Two expressions get the same value number if they compute the same value on all paths - this detects non-local common subexpressions. GVN with SSA naturally handles phi functions - different phi functions get different value numbers unless they always select the same value. C is FALSE - GVN is more powerful (works across blocks). D is FALSE - GVN specifically uses SSA and handles phi functions.

Partial Redundancy Elimination (PRE) subsumes both CSE and LICM: A fully redundant expression: computed on ALL paths reaching a point - CSE eliminates it. A partially redundant expression: computed on SOME but not all paths - PRE inserts the computation on the paths where it was not computed (making it fully redundant), then eliminates the redundancy. This is equivalent to LICM for loops: a loop-invariant expression is partially redundant (computed on the back edge path but not the loop entry path). PRE inserts it in the preheader (making it fully redundant), then eliminates the loop-body computation. Lazy code motion is a classic PRE algorithm. PRE is strictly more powerful than CSE alone.