Group C — Long / Numerical Questions (15 Marks Each)

Canonical LR(1) Parsing Table and Trace

Part (a): Constructing CLR(1) Parsing Table

Given Grammar:

1. S' → S
2. S → AA
3. A → aA
4. A → b

Step 1: Canonical LR(1) Item Sets

• I0:
  S' → • S, [$]
  S → • AA, [$]
  A → • aA, [a/b] (Since FIRST(A$) = {a, b})
  A → • b, [a/b]
• I1 (Goto I0, S): S' → S •, [$]
• I2 (Goto I0, A):
  S → A • A, [$]
  A → • aA, [$]
  A → • b, [$]
• I3 (Goto I0, a):
  A → a • A, [a/b]
  A → • aA, [a/b]
  A → • b, [a/b]
• I4 (Goto I0, b): A → b •, [a/b]
• I5 (Goto I2, A): S → AA •, [$]
• I6 (Goto I2, a):
  A → a • A, [$]
  A → • aA, [$]
  A → • b, [$]
• I7 (Goto I2, b): A → b •, [$]
• I8 (Goto I3, A): A → aA •, [a/b]
• I9 (Goto I6, A): A → aA •, [$]

Note: Goto(I3, a) loops to I3. Goto(I3, b) loops to I4. Goto(I6, a) loops to I6. Goto(I6, b) loops to I7.

Step 2: CLR(1) Parsing Table

Part (b): Parse Trace for 'aabb$'

Three-Address Code & Control Flow Graphs

Part (a): Generating 3AC

Statement: while (a < b) do if (c < d) then x = y + z; else x = y - z;

Quadruples Representation:

Part (b): Basic Blocks and CFG

• B1: (0) to (1). Evaluates while condition. Exits to B2 or END.
• B2: (2) to (3). Evaluates if condition. Exits to B3 or B4.
• B3: (4) to (5). Executes then branch. Jumps back to B1.
• B4: (6) to (8). Executes else branch. Jumps back to B1.

FIRST/FOLLOW Sets & LL(1) Table

Part (a): Compute FIRST and FOLLOW

Grammar:

1. E → T E'
2. E' → + T E' | ε
3. T → F T'
4. T' → * F T' | ε
5. F → ( E ) | id

FIRST Sets:

• FIRST(F) = { (, id }
• FIRST(T') = { *, ε }
• FIRST(T) = FIRST(F) = { (, id }
• FIRST(E') = { +, ε }
• FIRST(E) = FIRST(T) = { (, id }

FOLLOW Sets:

• FOLLOW(E) = { $, ) } (Start symbol gets $, and ')' follows E in F → (E) ).
• FOLLOW(E') = FOLLOW(E) = { $, ) }
• FOLLOW(T) = FIRST(E') - {ε} ∪ FOLLOW(E') = { +, $, ) }
• FOLLOW(T') = FOLLOW(T) = { +, $, ) }
• FOLLOW(F) = FIRST(T') - {ε} ∪ FOLLOW(T') = { *, +, $, ) }

Part (b): Construct LL(1) Parsing Table

Trace for id + id * id$:

DAG for Basic Blocks & Optimization

Part (a): Constructing the DAG

Original Code:

DAG Construction:

Part (b): Derive Optimized 3AC

By reading the DAG, we eliminate the redundant calculation of 4 * i (Common Subexpression Elimination) and remove redundant variable assignments (Copy Propagation / Dead Code Elimination).

Optimized 3AC:

Chaitin's Graph Coloring for Register Allocation

Part (a): Explanation of the Algorithm

Chaitin's algorithm formulates register allocation as a graph coloring problem. If the CPU has \(K\) physical registers, we attempt to color an Interference Graph using \(K\) colors.

• Node: Represents a variable in the program.
• Edge: An edge connects two nodes if their live ranges overlap (they cannot share the same register).
• Simplification Phase: Repeatedly find a node with degree \(< K\) (fewer than \(K\) edges). Remove it from the graph and push it onto a stack. If all nodes have degree \(\ge K\), a node must be spilled (saved to memory).
• Coloring Phase: Pop nodes from the stack one by one, adding them back to the graph and assigning them a color (register) that is not used by any of their currently active neighbors.

Part (b): Construct Interference Graph

Suppose variables a, b, c, d have lifetimes such that: a interferes with b, c, d. b interferes with a, c. c interferes with a, b, d. d interferes with a, c.

• K = 3 Registers (R1, R2, R3).
• Assign a = R1.
• b neighbors a. Assign b = R2.
• c neighbors a, b. Assign c = R3.
• d neighbors a, c. Can we reuse R2? Yes, because d does not interfere with b. Assign d = R2.
• Coloring successful! No spills needed.

Part (c): Register Spilling Mechanism

If the graph cannot be colored with \(K\) colors, the compiler selects a variable to "spill" to main memory. It generates a STORE instruction after every definition of the variable, and a LOAD instruction before every use. This splits the variable's long live range into several tiny, independent live ranges, significantly reducing the degree of the node in the interference graph, making it easier to color on the next iteration.

SDT for Type Checking & Conversions

Part (a): Type Checking Principles

During Semantic Analysis, the compiler traverses the AST to ensure operators receive operands of compatible types. If types mismatch but are compatible (e.g., int + float), the compiler applies Implicit Type Conversion (Coercion). It inserts a new AST node (like intToFloat) to convert the int operand into a float before the addition occurs.

Part (b): SDD Rules for Arithmetic Type Conversion

Assume we have an expression grammar E → E1 + E2, and our basic types are int and float.

if (E1.type == int and E2.type == int) {
    E.type = int;
    E.node = new Node('+', E1.node, E2.node);
} 
else if (E1.type == float and E2.type == float) {
    E.type = float;
    E.node = new Node('+', E1.node, E2.node);
} 
else if (E1.type == int and E2.type == float) {
    E.type = float;
    // Coerce E1 to float
    Node* t1 = new Node('intToFloat', E1.node);
    E.node = new Node('+', t1, E2.node);
} 
else if (E1.type == float and E2.type == int) {
    E.type = float;
    // Coerce E2 to float
    Node* t2 = new Node('intToFloat', E2.node);
    E.node = new Node('+', E1.node, t2);
} 
else {
    error("Type mismatch");
}

E.type = lookup(id.entry, type);
E.node = new Leaf(id.entry);

Lex/Flex Tool and Program

Part (a): Lex File Structure

A Lex specification file (.l extension) generates a C program (lex.yy.c) that acts as a lexical analyzer. It has three sections:

1. Declarations: %{ ... %} C includes, global variables. Macro definitions for regex patterns.
2. Rules (%%): Pairs of [Regular Expression] { C Code Action }. When the lexer matches the regex against the input stream, it executes the corresponding C code block.
3. User Subroutines (%%): C functions like main() to drive the lexer and yywrap() to handle EOF.

Part (b): Complete Lex Program

A Lex program to count keywords, identifiers, integers, floats, and lines.

Yacc/Bison and Calculator Program

Part (a): Yacc Structure and Precedence

Yacc reads a .y file containing a Context-Free Grammar and generates an LALR(1) parser in C (y.tab.c). To resolve shift-reduce conflicts naturally found in expression grammars, Yacc uses precedence declarations:

• %left '+' '-': Left associative, lower precedence.
• %left '*' '/': Left associative, higher precedence. (Listed lower in the file means higher precedence).

Part (b): Complete Yacc Specification for a Calculator

Lex File (calc.l) - Feeds tokens to Yacc

Yacc File (calc.y)

ICG for 2D Array References

Part (a): Memory Layout Orders

Physical memory is a 1-dimensional array of bytes. A 2D array A[M][N] (where M = rows, N = columns) must be linearized.

• Row-Major Order: Used by C/C++. Elements of the first row are stored contiguously in memory, followed by the second row, etc.
• Column-Major Order: Used by Fortran/MATLAB. Elements of the first column are stored contiguously, followed by the second column, etc.

Part (b): Address Calculation & 3AC

Given: Array A[M][N]. Let w be the size of one element in bytes (e.g., 4 bytes for an int). Let Base be the starting memory address of A[0][0].

Address Formula (Row-Major):
\(\text{Address}(A[i][j]) = \text{Base} + ((i \times N) + j) \times w\)

Generating 3AC for x = A[i][j]:

Assume the array has N = 10 columns and element size w = 4 bytes. We must generate low-level intermediate code that explicitly computes the memory offset.

Next-Use Information & Register Descriptors

Part (a): Next-Use Calculation

Next-use information tells the code generator exactly when the value of a variable will be used next in the basic block. This is critical for Register Allocation. If a variable in a register has no "next use" (it is dead), the register can be immediately reused for another variable without saving it to memory.

Register Descriptor: Tracks which variables are currently held in each physical register.

Address Descriptor: Tracks the current memory locations where the valid value of a variable resides (could be in a register, in RAM, or both).

Part (b): Trace Register Descriptors

Code Segment: x = (a - b) + (a - c) + (a - b)

Convert to 3AC first:

Trace Table (Assume 2 Registers R0, R1):

Global Data Flow Analysis: Reaching Definitions

Part (a): Global Data Flow Analysis

Global Data Flow Analysis determines how values and properties of variables propagate across the Control Flow Graph (CFG), beyond the boundaries of a single basic block. It uses an iterative algorithm to solve a system of data-flow equations until a fixed point (convergence) is reached.

Part (b): Reaching Definitions Equations

A definition \(d\) of a variable \(x\) reaches a point \(p\) if there is a path from \(d\) to \(p\) such that \(x\) is not killed (overwritten) along the path.

• GEN[B]: The set of definitions generated within block B that reach the end of B without being killed locally.
• KILL[B]: The set of all definitions in the entire program that define the same variables defined in B.

Iterative Equations (Forward Flow):

1. \(\text{IN}[B] = \bigcup_{P \in \text{predecessors}(B)} \text{OUT}[P]\)
(A definition reaches the start of B if it reaches the end of any of B's predecessors).

2. \(\text{OUT}[B] = \text{GEN}[B] \cup (\text{IN}[B] - \text{KILL}[B])\)
(A definition reaches the end of B if it was generated in B, OR if it entered B and was not killed in B).

Solving Iteratively:

1. Initialize \(\text{OUT}[B] = \emptyset\) for all blocks.
2. Loop through all blocks, calculating \(\text{IN}\) then \(\text{OUT}\).
3. Repeat the loop until no \(\text{OUT}\) set changes for any block (Convergence).

Live Variables & Available Expressions

Part (a): Concepts

• Available Expressions: An expression x + y is available at point \(p\) if every path from the start node to \(p\) evaluates x + y, and neither x nor y is modified between the last evaluation and \(p\). Used for Global Common Subexpression Elimination.
• Live Variable Analysis: A variable \(x\) is live at point \(p\) if its value at \(p\) could be read along some path before \(x\) is redefined. Used for Dead Code Elimination and Register Allocation.

Part (b): Backward Data Flow Equations for Live Variables

Because liveness depends on future uses of a variable, information flows backward through the CFG.

• USE[B]: Variables whose values are read in B prior to being overwritten in B.
• DEF[B]: Variables that are definitely overwritten in B.

Iterative Equations (Backward Flow):

1. \(\text{OUT}[B] = \bigcup_{S \in \text{successors}(B)} \text{IN}[S]\)
(A variable is live at the end of B if it is live at the start of any of B's successors).

2. \(\text{IN}[B] = \text{USE}[B] \cup (\text{OUT}[B] - \text{DEF}[B])\)
(A variable is live at the start of B if it is used in B, OR if it is live at the end of B and not redefined in B).

Symbol Tables for Object-Oriented Scopes

Part (a): Organization

Object-Oriented Languages (like Java/C++) introduce complex nested scopes: Global → Namespace → Class → Method → Local Block. The symbol table must support inheritance (resolving variables in a parent class) and shadowing (local variables hiding class fields).

The compiler creates a hierarchical tree of symbol tables. Each table represents a scope and contains a pointer to its enclosing (parent) scope's table.

Part (b): Scope Tree Structure and Lookup

Symbol Lookup Mechanism:

If x is referenced inside the if-block:

1. Search the if-block table. Not found.
2. Follow pointer to method1() table. Not found.
3. Follow pointer to Class A table. Found int x. Return type and address.
4. If not found in Class A, and Class A extends BaseClass, the pointer traces up to BaseClass before checking Global.

Runtime Storage Allocation

Part (a): Storage Regions

For procedural languages, OS memory given to a program is divided into:

• Code/Text Segment: Read-only, executable machine instructions.
• Static/Global Data: Global variables and static variables allocated exactly once at compile-time.
• Heap: Dynamically allocated memory (e.g., malloc()). Grows upwards.
• Stack: Memory for function calls and local variables. Grows downwards.

Part (b): Activation Record Creation Trace

When caller() invokes callee(int x):

1. Caller pushes the actual parameter x onto the stack.
2. Caller saves its own machine status (specifically the Return Address PC) onto the stack.
3. Caller executes the jump instruction to callee's code.
4. Callee pushes the old Frame Pointer (Control Link) onto the stack to save the caller's stack frame base.
5. Callee updates the Frame Pointer to the current Stack Pointer (establishing its own Activation Record base).
6. Callee decrements the Stack Pointer to allocate space for its own local variables and temporaries.
7. When returning, the process reverses: the stack pointer is restored to the control link, and execution jumps back to the saved return address.

Garbage Collection (Generational)

Part (a): Standard Algorithms Overview

• Mark-and-Sweep: Marks live objects, sweeps dead ones. Causes fragmentation.
• Copying Collector: Copies live objects to a new memory space. No fragmentation, but wastes 50% RAM.
• Reference Counting: Each object tracks how many pointers point to it. If count reaches 0, it is immediately freed. Cannot detect cyclical references (A points to B, B points to A).

Part (b): Generational Garbage Collection

The Generational Hypothesis: "Most objects die young." (e.g., local variables in functions). Objects that survive a long time (e.g., global caches) will likely continue to survive.

Mechanism:

1. The heap is divided into generations: Young Generation (Nursery) and Old Generation (Tenured).
2. All new objects are allocated in the Young Gen.
3. Because most objects die young, the GC runs a Minor GC frequently on the Young Gen using a fast Copying Collector. It reclaims massive amounts of memory quickly.
4. Objects that survive multiple Minor GCs are "promoted" to the Old Gen.
5. The Old Gen fills up very slowly. A Major GC (usually Mark-and-Sweep) runs infrequently on the Old Gen.

Advantage: Drastically reduces GC pause times because the collector doesn't have to scan the entire heap every time memory runs low.

Error Detection and Recovery

Part (a): Errors Across Phases

• Lexical Errors: Unrecognized characters (@), unterminated strings.
• Syntax Errors: Missing semicolons, unbalanced parentheses, invalid statements.
• Semantic Errors: Type mismatches, undeclared variables, parameter count mismatches.
• Logical Errors: Not caught by the compiler (e.g., infinite loops).

Part (b): Panic Mode vs Phrase-Level in Parsers

Panic Mode in LL(1) / LR(1):

• When an unexpected token arrives, the parser is stuck.
• It enters panic mode, popping states off the stack and discarding input tokens until it finds a "synchronization token" (e.g., } or ;).
• Once synchronized, parsing resumes from a known safe state.

Phrase-Level Recovery:

• The parser detects the error and attempts a local patch.
• If the input is x = y * ;, the parser might artificially insert an identifier token (making it x = y * id;) or delete the *, issue an error message, and continue.
• This prevents massive chunks of code from being skipped, but requires carefully designed error productions in the grammar (e.g., adding a grammar rule Stmt → error ; to catch malformed statements).

Peephole Optimization (x86 Assembly)

Part (a): Pattern Matching

The compiler scans the generated target assembly code using a small sliding window (2-4 instructions). If the window matches a known inefficient pattern, it is replaced with an optimized sequence.

Part (b): Applying Transformations to 8086 Code

Unoptimized Snippet:

Peephole Applied:

Loop Optimizations

Part (a): Concepts

• Loop Unrolling: Duplicating the loop body to reduce the number of iterations and the overhead of evaluating the loop condition/jump.
• Loop Jamming (Fusion): Merging two adjacent loops that iterate over the same range into a single loop to reduce loop overhead.
• Software Pipelining: Reorganizing loops such that different iterations of the loop are overlapped. E.g., loading data for iteration i+1 while computing data for iteration i.

Part (b): Matrix Multiplication Unrolling

Original Loop:

Unrolled Loop (Factor of 4):

Advantages: Eliminates branch instructions entirely. Modern Superscalar CPUs can execute all 4 multiplication instructions simultaneously (Instruction-Level Parallelism) because there are no data dependencies between them.

LLVM Compiler Architecture

Part (a): LLVM Architecture

LLVM is a modern, modular compiler framework used by Clang (C/C++), Rust, and Swift.

• Front-End: Parses the source language and generates LLVM Intermediate Representation (LLVM IR). Clang is the front-end for C/C++.
• LLVM IR: The core of the system. It is a strictly typed, RISC-like, Static Single Assignment (SSA) language. It acts as the universal language for the optimizer.
• Optimizer (Middle-End): A collection of modular Passes that read LLVM IR, optimize it, and emit optimized LLVM IR.
• Back-End: Reads the optimized LLVM IR and translates it into specific machine code (x86, ARM) via Instruction Selection and Register Allocation.

Part (b): LLVM Pass Manager

The Pass Manager controls the execution of optimization passes.

• Analysis Passes: Compute information about the IR without modifying it (e.g., Call Graph analysis, Dominator Tree analysis).
• Transform Passes: Mutate the IR to optimize it (e.g., mem2reg promotes memory allocations to SSA registers, loop-unroll unrolls loops).
• The Pass Manager schedules these passes, ensuring that if a Transform pass invalidates the Dominator Tree, the Analysis pass is automatically re-run before the next pass that requires it.

Complete Trace Through All 6 Compiler Phases

Part (a) & (b): Tracing a = b + c * 60

1. Lexical Analysis: Converts character stream to tokens.

2. Syntax Analysis: Generates Parse Tree (or AST) enforcing precedence.

3. Semantic Analysis: Type checking. Assuming a, b, c are floats.

4. Intermediate Code Generation: Generates 3AC.

5. Code Optimization: Applies Constant Folding at compile time.

6. Target Code Generation: Generates assembly (assuming x86-like FPU).

SLR(1) Parsing Table Construction

Part (a): Construct SLR(1) Table

Grammar:

1. S' → S
2. S → L = R
3. S → R
4. L → * R
5. L → id
6. R → L

FOLLOW Sets:

• FOLLOW(S) = { $ }
• FOLLOW(L) = { =, $ }
• FOLLOW(R) = { =, $ }

LR(0) Item Sets (DFA):

• I0: S' → •S, S → •L=R, S → •R, L → •*R, L → •id, R → •L
• I1 (Goto I0, S): S' → S•
• I2 (Goto I0, L): S → L•=R, R → L•
• I3 (Goto I0, R): S → R•
• I4 (Goto I0, *): L → *•R, R → •L, L → •*R, L → •id
• I5 (Goto I0, id): L → id•
• I6 (Goto I2, =): S → L=•R, R → •L, L → •*R, L → •id
• I7 (Goto I4, R): L → *R•
• I8 (Goto I4, L): R → L•
• I9 (Goto I6, R): S → L=R•

(Goto(I4, *) = I4, Goto(I4, id) = I5, Goto(I6, *) = I4, Goto(I6, id) = I5, Goto(I6, L) = I8)

Part (b): Checking for Conflicts

An SLR(1) table uses FOLLOW sets to place Reduce actions. Look at State I2:

• S → L•=R dictates a Shift action on the symbol = (Goto I6).
• R → L• dictates a Reduce action by rule 6. According to SLR(1) rules, this reduction is placed in the columns for FOLLOW(R).
• Since FOLLOW(R) contains = and $, we must place Reduce 6 in the column for =.

Conflict: In State I2, under column =, we have both a Shift action and a Reduce action. Therefore, the SLR(1) table has a Shift-Reduce (S-R) conflict, and this grammar is NOT SLR(1).

LR Item Sets: SLR vs LALR vs CLR

Part (a): Generation Methods

• SLR(1): Builds the DFA using basic LR(0) items (no lookahead). It blindly places Reduce actions using global FOLLOW() sets. It is small but prone to conflicts.
• CLR(1): Builds the DFA using LR(1) items (Item + Lookahead). Lookaheads are precisely tracked through transitions. It places Reduce actions only in the columns specified by the item's lookahead. It is powerful but produces massive state machines because it creates distinct states for identical items that have different lookaheads.
• LALR(1): Starts by generating the massive CLR(1) DFA. It then scans the states and merges states that have the exact same "Core" (the LR(0) part of the item) but different lookaheads. The resulting DFA has the exact same number of states as SLR(1), but retains precise lookahead information.

Part (b): Merging CLR to LALR

Suppose CLR generates two states:

State 10: A → X • Y, [a]
State 15: A → X • Y, [b]

Because the core A → X • Y is identical, LALR merges them into a single state:

Merged State 10_15: A → X • Y, [a/b]

Conflict Resolution: Merging LR(1) states to form LALR(1) states can never introduce a new Shift-Reduce conflict. If a shift-reduce conflict appears in the merged state, it must have already existed in the original CLR(1) states. However, merging can occasionally introduce new Reduce-Reduce conflicts.

Backpatching in Control Flow

Part (a): Explanation

Backpatching is used in one-pass compilers. When parsing a boolean expression with short-circuit evaluation, the compiler generates jump instructions but doesn't know the destination addresses yet. It leaves them blank and adds their instruction indexes to a truelist or falselist. When the destination code is finally generated, a backpatch() function fills in the blanks.

Part (b): Backpatched 3AC for if (a < b or c < d) and e < f then x = 1;

Assuming instructions start at index 100.

Memory Management for OOP (C++/Java)

Part (a): General Memory Management

In OOP, objects are typically allocated dynamically on the Heap using new. Memory is reclaimed either manually (delete in C++) or automatically via Garbage Collection (Java). Local object references are stored on the Stack within activation records.

Part (b): Object Layout and Virtual Method Tables (VTable)

Object Layout in Memory: An object in memory consists of:

1. A hidden pointer to the class's Virtual Method Table (vptr).
2. The object's instance variables (fields). Fields inherited from parent classes are placed first in the layout to ensure binary compatibility.

Dynamic Dispatch via VTable:

To support Polymorphism (Method Overriding), the compiler creates one VTable per class (not per object). The VTable is an array of function pointers pointing to the most derived implementation of virtual methods.

When a virtual method is called (e.g., obj->draw()):

1. The CPU follows obj's hidden vptr to find the class's VTable.
2. It looks up the index for draw() (e.g., index 2) in the VTable.
3. It jumps to the function address stored at that index.

Code Generation for Target Architectures

Part (a): RISC vs CISC

Part (b): Instruction Selection via Tree-Rewriting

The compiler represents the Intermediate Code as a forest of trees. The Target Architecture's instruction set is represented as a set of tree templates (patterns).

Instruction selection is treated as a Tree Pattern Matching problem. The compiler "tiles" the IR tree with target instruction templates. If a template matches a subtree, the compiler replaces the subtree with the corresponding assembly instruction. Dynamic programming (like the Sethi-Ullman algorithm) is used to find the optimal tiling that minimizes execution cost.

Dominator Trees and Natural Loops

Part (a): Concepts

• Dominator: Node A dominates Node B if every path from the CFG entry node to B must pass through A.
• Dominator Tree: A tree representing dominance. The parent of a node is its immediate dominator (the closest dominator).
• Natural Loop: A loop in the CFG that has a single entry point (the header) and at least one back-edge that returns to the header.

Part (b): Algorithm to Identify Natural Loops

1. Compute Dominators: For all nodes in the CFG.
2. Find Back-Edges: A CFG edge from node T (Tail) to node H (Header) is a back-edge IF AND ONLY IF H dominates T.
3. Construct Loop Body: For every back-edge T → H, the natural loop consists of H, T, and all nodes that can reach T without passing through H.
4. Insert Pre-Header: The compiler injects a new block (the pre-header) immediately before the loop header. This provides a safe place to move invariant code (Loop Hoisting) out of the loop.

Value Numbering

Part (a): LVN vs GVN

Value Numbering tracks the mathematical values computed by a program rather than the variable names themselves.

• Local Value Numbering (LVN): Operates within a single Basic Block. Assigns unique integer IDs to distinct values. Used for localized Common Subexpression Elimination and Constant Folding.
• Global Value Numbering (GVN): Extends this logic across the entire CFG using SSA form. Much more powerful, allowing the compiler to prove that variables in entirely different blocks hold the same underlying value.

Part (b): Applying LVN

Code:

LVN Trace:

1. a = x + y: Give x value 1, y value 2. Expression + (1,2) gets value 3. a maps to 3.
2. b = x + y: Expression + (1,2) already exists and has value 3! Map b to 3. (Optimize: b = a).
3. a = 17: Give 17 value 4. Update a to map to 4.
4. c = x + y: Expression + (1,2) still exists as value 3. Map c to 3. (Optimize: c = b because a was overwritten!).

Interprocedural Optimization and Inlining

Part (a): Interprocedural Optimization (IPO)

Standard optimizations operate within a single function boundary. IPO analyzes the entire program (or multiple files via Link-Time Optimization) to optimize across function calls. Techniques include Dead Function Elimination and Constant Propagation across arguments.

Inline Expansion: The most aggressive IPO technique. The compiler replaces a function call with the actual body of the called function.

Part (b): Tradeoffs of Function Inlining

Target Machine Architecture & Code Generation

Part (a): Target Machine Model

A standard target machine model assumes a byte-addressable memory, \(n\) general-purpose registers (\(R_0\) to \(R_{n-1}\)), and standard instructions (LOAD, STORE, ADD, SUB, MULT, BRANCH). Instruction costs usually correlate with memory access (Register-to-Register = 1 cost, Memory-to-Register = 2 cost).

Part (b): Generating Assembly using 2 Registers

Statement: x = a + b * c

Assuming we have registers R0 and R1. To minimize memory accesses, we should evaluate the most deeply nested subtree first (the multiplication).

Static Program Analysis

Part (a): Tools and Linters

Static analysis examines source code without executing it. Modern compilers (like Clang) use static analysis infrastructure to issue warnings (e.g., "variable used uninitialized", "memory leak"). Linters (like ESLint or SonarQube) are standalone static analysis tools enforcing style and catching common bugs.

Part (b): Abstract Interpretation and Model Checking

• Abstract Interpretation: Mathematically models the execution of a program across all possible inputs. Instead of tracking exact values (e.g., x = 5), it tracks abstract properties (e.g., "x is a positive integer"). It guarantees the absence of certain bugs (e.g., proving no array out-of-bounds errors can ever occur).
• Model Checking: Explores the state space of a program to verify properties, typically for concurrent systems. It creates a state-machine of the program and checks if "bad states" (like deadlocks or race conditions) are reachable. If a bad state is found, it provides a counter-example trace to reproduce the bug.