Matching Practice Questions

The loop exit condition i < 100 is evaluated: once before each of the 100 iterations (to decide to continue), plus once after the 100th iteration completes (when i = 100 and i < 100 is false, causing loop exit). Total = 101 evaluations. In a while-loop formulation: the condition is checked at the top each iteration. The 101st check (i=100, false) causes exit. This is important for loop optimization - the condition test itself is an overhead that loop unrolling reduces proportionally.

A basic block is a maximal sequence of consecutive three-address instructions such that: (1) Control enters only at the first instruction (no jumps into the middle), and (2) Control leaves only at the last instruction (no jumps out of the middle except at the end). Leaders (first instructions of basic blocks) are: the first instruction of the program, any target of a conditional/unconditional jump, and any instruction immediately following a jump. Basic blocks are the fundamental unit for local optimizations and code generation.

Instruction scheduling reorders instructions within a basic block (or across blocks) to minimize pipeline hazards and stalls. Modern CPUs have pipelines - a load instruction may have a latency of several cycles before its result is available. If the next instruction immediately uses the loaded value, a pipeline stall occurs. Instruction scheduling inserts independent instructions between dependent ones to hide latency. Constraints: data dependences (RAW - read after write, WAR, WAW) must be respected; the program's observable behavior must be unchanged. List scheduling is a common algorithm. Two types: pre-register-allocation scheduling (more freedom) and post-register-allocation scheduling (more accurate timing).

In SSA form, when a variable x is assigned in two branches (x=1 in then-branch, x=2 in else-branch), at the merge point after both branches, the correct value of x depends on which branch was executed. SSA inserts a φ (phi) function: x3 = φ(x1, x2), where x1 and x2 are the versions assigned in each branch. The phi function conceptually selects the appropriate version at runtime. Phi functions are not real machine instructions - they are replaced during code generation with appropriate move instructions or handled by register allocation. SSA simplifies many optimizations (constant propagation, dead code elimination, value numbering).

Code generation tasks: Instruction selection: mapping IR operations to target machine instructions (may have multiple choices - e.g., using a single multiply-add instruction instead of separate multiply and add). Register allocation: assigning variables/temporaries to the limited number of machine registers; spilling to memory when registers are insufficient. Instruction scheduling: reordering instructions (within correctness constraints) to exploit instruction-level parallelism, fill pipeline delay slots, and reduce stalls. Garbage collection is a runtime system concern, not a compile-time code generation task (though the compiler may generate GC support code).

Control Flow Graph (CFG): A: TRUE - each node is a basic block (maximal straight-line code sequence). B: TRUE - directed edges represent possible control flow: sequential (fall-through), conditional branches (two edges), and unconditional jumps. C: TRUE - all dataflow analyses (reaching definitions, liveness, available expressions) are formulated as equations over the CFG and solved iteratively. D: TRUE - for analysis purposes, a single entry node (program entry/function entry) and a single exit node (artificial merge of all return/exit points) are assumed. If multiple returns exist, they are merged into a single EXIT node for backward analyses.

Compiler considers a variable as live if its value is accessed before its being rewritten with an another value. Therefore at end of B1; except d all are live. Now comparing the options we need to choose between option A and C, therefore need to check at end of B3: Clearly a is not live as it is getting overwritten in next block B1, and we can also observe that b and c are live. In case of block B2 and B3 we can note that variable d is also being over written in B2, but e and f is getting accessed in B2 and B3 respectively, hence variable e and f are also live. In case of block B4, variable g is getting overwritten hence not live. Therefore the set of all live variables at the end of block B3 $= \{b, c, e, f\}$. Hence, Option A is the correct answer. PS: For liveness analysis at then end of Block B2 and B4; as after block B4 the program will exit no variable needs to be live after B4 and in case of B2 as only d and e variable are accessed to overwrite variable g, the set of live variables after B2 will be $\{d,e\}$

Check each potential common subexpression: (2) b = a - d and (4) d = a - d: at instruction (2), a and d have their original values. At instruction (4), a still has the same value (last assigned at (1)), and d still has its original value (d not redefined between (2) and (4) - instruction (2) redefines b, not d). So a-d at (4) computes the same value as at (2). YES - common subexpression. (1) b+c and (3) b+c: at (1), b and c have original values. At (3), b has been redefined by instruction (2): b = a-d. So b+c at (3) uses a different b - NOT a common subexpression. Answer: only (2) and (4) are common subexpressions.

Alias analysis determines whether pointer p and pointer q can point to the same memory location (*p and *q alias). This is critical for optimizations: CSE: if t1 = *p and later t2 = *p, and between them *q is written - if p and q may alias, the write to *q may change *p's value, so t2 cannot be replaced by t1. Code motion: *p = f() cannot be hoisted out of a loop if the loop body writes through a pointer that may alias p. Register allocation: a variable stored in a register may be stale if aliased memory is modified through a pointer. Without alias information, the compiler must assume the worst case (any two pointers may alias), preventing many optimizations. Precise alias analysis (points-to analysis) enables more aggressive optimization.

Analysis of if(x>0){y=1;}else{y=1;}: A: TRUE - both branches assign y=1 regardless of the condition. The entire if-else can be replaced by y=1, eliminating the conditional branch. This is a form of dead code elimination (the branch condition x>0 is never used to differentiate behavior). B: TRUE - after this if-else, y is known to be 1 on all paths (constant propagation), enabling further optimizations wherever y is used. C: FALSE - CSE eliminates recomputation of the SAME expression when the result might differ. Here y=1 is not a 'subexpression' that produces different values at different points - both assignments produce the same value, but CSE is not the right term. The optimization is branch elimination. D: FALSE - no loop present.

For a 2D array stored in row-major order (C/Java convention): a[i][j] is stored at base address + offset. Row i starts at base + i * (R * w) where R = number of columns and w = size of each element. Element j within row i is at additional offset j * w. Total address = base(a) + (i * R + j) * w. This generates code: t1 = i * R; t2 = t1 + j; t3 = t2 * w; addr = base(a) + t3. For column-major order (Fortran): address = base(a) + (j * C + i) * w where C = number of rows.

A variable x is live at point p if there exists a path from p through the control flow graph to some use of x, and x is not redefined along that path before the use. If x is live at p, its current value may be needed in the future - so x's register or memory location cannot be safely freed. If x is not live (dead) at p, its value will never be used again - registers holding x can be reallocated. Liveness analysis is a backward dataflow problem: USE[B] = variables used in B before any redefinition. DEF[B] = variables defined in B before any use. IN[B] = USE[B] ∪ (OUT[B] − DEF[B]); OUT[B] = ∪ IN[S] for successors S.

For a stack machine evaluating a + bc (operator precedence: * before +): bc must be computed first, then add a. Option A: PUSH a → stack:[a]. PUSH b → [a,b]. PUSH c → [a,b,c]. MUL → pops b,c, pushes bc → [a, bc]. ADD → pops a, bc, pushes a+bc → [a+bc]. Correct. Option B: PUSH b → [b]. PUSH c → [b,c]. MUL → [bc]. PUSH a → [bc, a]. ADD → pops bc and a, pushes bc+a = a+bc → [a+b*c]. Correct (addition is commutative). Option C: PUSH a; PUSH b; ADD → computes a+b first (wrong order). So A and B are both correct.

Common intermediate representations: Three-address code (TAC) - each instruction has at most one operator and three addresses; easy to generate target code from. Abstract Syntax Tree (AST) - tree representation of the program structure; used for source-level optimizations. SSA form - each variable assigned exactly once; simplifies dataflow analysis and many optimizations (used in LLVM). Regular expressions are used in lexical analysis (scanner), not as an IR for code generation.

An activation record (stack frame) is the memory block allocated on the call stack for each procedure invocation. Typical contents: Return address - where to return after the call completes. Control link (dynamic link) - pointer to caller's activation record. Access link (static link) - pointer to enclosing scope's activation record (for nested procedures). Saved registers - callee-saved registers that must be preserved. Local variables - variables local to the procedure. Temporaries - compiler-generated temporaries. Parameters - actual arguments passed to the procedure (or pointers to them). Return value - storage for the value returned (sometimes in a register). The exact layout varies by calling convention (cdecl, stdcall, fastcall, System V AMD64 ABI).

Register spilling occurs during register allocation when all available registers are occupied and a new variable needs a register. The code generator must free a register by storing its current value to a memory location (the variable's stack frame slot or a designated spill location). This 'spills' the register's value to memory. The spilled variable is later reloaded from memory when needed again. Spilling adds load and store instructions, increasing code size and runtime. Minimizing spills is a key objective of register allocation algorithms. A good register allocator (e.g., Chaitin's graph coloring) chooses to spill variables with low 'spill cost' (infrequently used, cheap to reload).

Calling convention register categories: Caller-saved (volatile) registers: the caller must save their values before making a function call if those values are needed after the call returns. The callee is free to modify them without saving/restoring. Example: RAX, RCX, RDX in System V AMD64 ABI. Callee-saved (non-volatile) registers: if the callee uses these registers, it must save their original values (push to stack) at function entry and restore them (pop) before returning. The caller can trust these registers are unchanged after a call. Example: RBX, RBP, R12-R15 in System V AMD64 ABI. This division reduces the number of save/restore operations needed overall.

Worklist algorithm for dataflow analysis: (1) Initialize: for forward analysis, initialize IN[entry] to the initial value; all other IN/OUT sets to the most optimistic value (top of lattice) or most conservative. (2) Add all basic blocks to a worklist. (3) Repeat: remove a block B from the worklist; compute IN[B] from OUT of predecessors (or OUT[B] from IN of successors for backward); recompute OUT[B] (or IN[B]) using the transfer function; if changed, add all successors (or predecessors) to the worklist. (4) Terminate when worklist is empty (fixed point). Terminates because: transfer functions are monotone and the lattice has finite height. Works on arbitrary CFGs including loops (back edges). Finds the meet-over-all-paths (MOP) solution - optimal for the chosen lattice.