COL729 Lab 2 : IR and Compiler Passes

Due date - 23:55, 9 September 2026

Weightage: 20 Marks (Actual weightage will be decided later)

In this assignment, we will become familiar with the LLVM IR and the optimization passes implemented by the Clang/LLVM compiler infrastructure at various optimization levels. We will also implement a simple transformation pass within the Clang/LLVM infrastructure.

Instructions

Work in groups of two.
Do not submit compiler-generated files. Submit the source programs, the source and build instructions for your pass, and a PDF report containing the requested IR excerpts and discussion.

Part A: Reading unoptimised LLVM IR (5 marks)

Write one C file, opcodes.c, containing the following functions. Keep the functions separate and mark them noinline so that their IR remains easy to locate.

A function that updates a field of an element of an array of structures. The structure must contain a scalar, a two-dimensional array, and a pointer. Use both a run-time array index and constant field indices.
A loop containing an integer arithmetic expression, a floating-point expression, both integer and floating-point comparisons, an if/else, and a loop-carried value.
A switch with at least four cases, a call to another function, a ternary expression, and conversions between two integer widths and between an integer and a floating-point type.

Generate textual IR without optimization:

clang -O0 -Xclang -disable-O0-optnone -S -emit-llvm opcodes.c -o opcodes.O0.ll
opt -S -passes=mem2reg opcodes.O0.ll -o opcodes.mem2reg.ll
opt -S -passes='mem2reg,simplifycfg' opcodes.O0.ll -o opcodes.canonical.ll

For every opcode below, locate one occurrence in these files, copy the smallest useful IR excerpt into the report, and explain its operands, result type, and connection to the C source:

memory and addressing: alloca, load, store, and getelementptr;
arithmetic and comparison: one integer operation, one floating-point operation, icmp, and fcmp;
control flow and SSA: br, switch, phi, select, call, and ret;
casts: trunc or zext/sext, and sitofp/uitofp or fptosi/fptoui.

Draw the control-flow graph of the loop function and annotate the incoming edge associated with each phi operand. For the structure access, compute the address represented by each index of its getelementptr. In particular, explain why getelementptr computes an address but does not read memory.

Part B: What optimization does to the IR (5 marks)

Compile the same file at four optimization levels and retain the IR:

clang -O1 -S -emit-llvm opcodes.c -o opcodes.O1.ll
clang -O2 -S -emit-llvm opcodes.c -o opcodes.O2.ll
clang -O3 -S -emit-llvm opcodes.c -o opcodes.O3.ll

Create a table, one row per function and optimization level, reporting the number of basic blocks and of each LLVM instruction opcode. A short script may be used, but it must parse instructions rather than count words in comments or metadata. Discuss at least three substantial changes, such as promotion from memory to SSA, constant folding, dead-code elimination, branch simplification, inlining, loop unrolling, or changes to getelementptr. For each change, give before/after excerpts and identify the LLVM pass most likely responsible. Confirm your claim by running a small, named pipeline with opt -S -passes='...'; do not infer solely from the final -O3 output.

Part C: Optimization passes used at each optimization level (5 marks)

Use opt to inspect the default optimization pipeline at each level. Use the same LLVM installation for clang and opt, since pipelines change between LLVM releases. Record the version reported by opt --version, then run:

for level in O0 O1 O2 O3; do
  opt -passes="default<${level}>" -print-pipeline-passes \
    -disable-output opcodes.O0.ll > passes.${level}.txt
done
opt --print-passes > available-passes.txt

The printed pipeline contains pass-manager adaptors and utility passes as well as transformations. From each pipeline, extract the transformation passes that can be named in an opt -passes='...' pipeline. Do not count analyses, analysis invalidation, instrumentation, or adaptors such as module(...), function(...), and loop(...) as transformations. Use opt --print-passes to check pass names; retain repeated occurrences in the ordered list because the same transformation can run at several points in a pipeline.

In the report, give one table with a column for each of O0, O1, O2, and O3. For each level, report the ordered transformation-pass list (share a short description for each pass), the number of pass invocations, and the number of distinct transformations. Then identify:

transformations common to all four levels;
transformations first introduced at O1, O2, or O3; and
transformations whose number or position of invocations changes between levels.

Part D: Vector IR produced by optimization (5 marks)

Create vector.c with three counted loops over arrays:

c[i] = a[i] * alpha + b[i] for float arrays;
an integer reduction (for example, sum or dot product); and
a loop which conditionally chooses an element from two arrays and writes the result to a third array.

Pass the length as a parameter, use at least 1024 elements in the test driver, and use C's restrict qualifier where it is valid. First compile with vectorization disabled, then enabled:

clang -O3 -fno-vectorize -fno-slp-vectorize -S -emit-llvm vector.c -o vector.scalar.ll
clang -O3 -march=native -Rpass=loop-vectorize -Rpass-missed=loop-vectorize \
  -S -emit-llvm vector.c -o vector.vector.ll 2> vector.remarks.txt

Find the vector types (for example, <4 x float>) in the optimised file. Explain the vector width and trace one vectorised loop through its vector load, arithmetic or comparison, select, and store instructions. Also locate and explain every vector-specific opcode emitted, including extractelement, insertelement, and shufflevector when present. Relate reduction code to llvm.vector.reduce.* intrinsics if your LLVM version emits them.

Vectorization and the exact opcodes depend on the target. If a loop is not vectorised, use the missed-optimization remark to explain why, modify only that loop to remove the obstacle, and show both versions. If one of the three vector-specific opcodes above is absent, state which lowering replaced it and add a small fourth loop (such as interleaving or de-interleaving two arrays) that gives the vectoriser an opportunity to generate it. Do not insert vector instructions into the generated IR by hand. Finally, check that the scalar and vector executables produce identical results on at least five input sizes, including a size not divisible by the vector width.

Turn in

Submit a single archive containing opcodes.c, vector.c, your opcode-counting script, the pass source and CMakeLists.txt, the pass tests, a README with exact build/run commands, and the PDF report. The report must be succinct and must include the requested tables, IR excerpts, vectorization remarks, correctness results, and explanations. Generated .ll, object, and shared library files should not be included.

The report should not contain any AI generated text.