1. Basic Concept, 2. Important Multiple choice QA, 3.Important 3 marks QA, 4. Important 12 marks QA, 5. Model Question paper.

Important Questions and Answers
CP25C04-Advanced Compiler Design
Syllabus
1. Intermediate Representations and Control Flow Analysis: Static single assignment (SSA)
form- Context-Free Grammer (CFG) construction-dominance relations-Intermediate
Representation (IR) design for functional and imperative languages-Static single assignment
and def-use chains.
Activities:
1. Convert source code to SSA form using LLVM IR.
2. Visualize control flow graphs from SSA using LLVM tools.

2. Program Analysis and Transformations: Data flow analysis- live variable analysis-
reaching definitions-Alias analysis and dependence analysis-Loop optimizations and
transformations.
Activities:
1. Perform loop unrolling and strength reduction.
2. Conduct live variable analysis and visualize data flow graphs.

3. Advanced Optimizations and Polyhedral Compilation: Polyhedral model for loop nests-
Tiling, skewing, fusion, and vectorization-Profile-guided and feedback-directed
optimizations.
Activities:
1. Implement loop tiling and loop skewing on a matrix multiplication program.
2. Analyze the effect on loop-intensive code with LLVM optimization flags.
V.
U
m




4. Just-in-Time (JIT) and Runtime Compilation: JIT compilation models: tracing, method-
ap




based-GraalVM architecture, Java HotSpot internals-LLVM JIT and dynamic language
at




support.
hy




Activities:
,Pr




1. Develop a basic JIT-enabled interpreter with LLVM or GraalVM.
of




2. Implement dynamic dispatch using LLVM JIT API.
./
EC
N
ot
es

, 5. Machine Learning in Compiler Design: ML for phase ordering, auto-tuning, and IR
prediction-Reinforcement learning for optimization passes-Dataset creation and
benchmarking for compiler ML.
Activities:
1. Train an ML model to predict optimization passes.
2. Use reinforcement learning for pass selection in toy compiler.

6. Domain-Specific Languages (DSLs) and Compiler Extensions: Designing DSLs for
AI/ML, DSP, graphics-Code generation for custom accelerators-Integration with TensorFlow
XLA and Halide
Activities:
1. Design and test a simple DSL grammar using ANTLR.
2. Integrate a DSL with TensorFlow XLA or Halide.

7. Security, Verification, and Future Trends: Secure compilation and type-safe intermediate
representations-Compiler fuzzing and formal verification (e.g., CompCert)-Quantum
compilers, multi-target compilers, and neuromorphic systems.
Activities:
1. Use CompCert to verify compilation of simple programs.
2. Apply compiler fuzzing using tools like libFuzzer.

S.No. Description
Unit-I
Intermediate Representations and Control Flow Analysis
Basic Concepts
S.
Basic Concept Important Points / Equations
No.
IR is a machine-independent form of source code used by a compiler for
Intermediate
1 optimization and code generation. Examples: Three-Address Code (TAC),
Representation (IR)
syntax trees, and bytecode.
Static Single Each variable is assigned a value exactly once. Different assignments use
2
Assignment (SSA) unique versions of a variable. Example: x1 = a + b and x2 = x1 * 2.
V.
U




Combines values arriving from different control-flow paths. Example: x3 =
m




3 Phi (φ) Function
φ(x1, x2).
ap




A directed graph representing program execution. Nodes represent basic
at




Control Flow Graph
hy




4 blocks, and edges represent possible control transfers. CFG = (V, E), where
(CFG)
,




V = blocks and E = control-flow edges.
Pr
of




5 Basic Block A sequence of consecutive statements with one entry and one exit, with no
./
EC
N
ot
es

, branching except at the end.
Node A dominates node B if every path from the entry node to B passes
6 Dominance Relation
through A. Notation: A dom B.
Immediate
7 The closest strict dominator of a node. Notation: idom(B) = A.
Dominator
Connect each variable definition to the statements where that value is used.
8 Def-Use Chains
Example: x = a + b; y = x * 2; — definition of x reaches its use in y.
Imperative Language Represents assignments, loops, conditions, and jumps. Example: t1 = a + b;
9
IR if t1 > 10 goto L1.
Represents function applications, expressions, and immutable values.
Functional Language
10 Example: y = f(x); evaluation often uses expression trees or graph-based
IR
representations.
Identify leaders: the first statement, jump targets, and statements following
11 CFG Construction jumps. Group statements into basic blocks and connect them using control-
flow edges.
IR supports constant folding, dead-code elimination, common
12 IR Optimization subexpression elimination, and copy propagation. Example: x = 3 * 4
becomes x = 12.
Important equations (copy directly to Word)

CFG = (V, E)



SSA: Each variable version is assigned only once.



Dominance: A dom B if every path from Entry to B passes through A.



Immediate Dominator: idom(B) = A
V.
U
m
ap




Def-Use Chain: Definition(x) -> Use(x)
at
hy
,Pr
of
./
EC
N
ot
es

, Constant Folding: x = 3 * 4 => x = 12



Phi Function: x3 = φ(x1, x2)

Exam tip: Focus on SSA form, φ-functions, CFG construction, dominance relations, and def-use
chains. These concepts are frequently useful for compiler design short-answer and descriptive
questions.

Multiple Choice QA
1. What is the main purpose of Static Single Assignment (SSA) form?

A) To execute a program faster by increasing variables

B) To assign a value to each variable only once

C) To remove all control-flow statements

D) To convert source code directly into machine code

Answer: B) To assign a value to each variable only once

Reason: In SSA form, each variable is assigned exactly once. Different assignments use different
versions of the variable, making data-flow analysis and compiler optimization easier.

Equation in plain text:

x1 = 10
x2 = x1 + 5

2. What does a Control Flow Graph (CFG) represent in a compiler?

A) The memory size of a program
V.
U




B) The sequence of variable declarations only
m
ap




C) The possible flow of control between basic blocks
at
hy




D) The program's input and output data only
, Pr
of
./
EC
N
ot
es