COL729 Lab 3 : Studying Compiler Passes

Due date - 23:55, 4 October 2026

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

Part A: A transformation pass (10 marks)

Implement a function-pass plugin for LLVM's new pass manager, named strength-reduce. It must replace multiplication by a positive power-of-two integer constant with an equivalent shl. Handle the constant on either side, preserve the integer type and applicable nuw/nsw flags (you may need to read about the meanings of these flags), avoid changing vector multiplications, and return the correct PreservedAnalyses value. Run it with:

opt -load-pass-plugin ./libStrengthReduce.so \
  -passes=strength-reduce -S input.ll -o output.ll
opt -passes=verify -disable-output output.ll

Provide positive tests for at least two integer widths and both operand orders, and negative tests for zero, one, a non-power-of-two, a negative constant, and a vector value. Compare the original and transformed programs' outputs.

You may use an online search or AI conversation bots to learn about how to write an LLVM pass, but please do not try to get an AI to solve the whole assignment for you.

Part B : Examples of Dataflow Analyses for C++ in Clang Analyzer (5 marks)

Read about Clang's analysis at https://clang.llvm.org/docs/DataFlowAnalysisIntro.html. Notice the difference in terminology: they use \bottom for \top and vice-versa; also they use the term join instead of "meet" (as discussed in class). Other than these cosmetic differences, the dataflow analysis fundamentals are identical to those discussed in class. Answer the following questions:

Which analysis among the examples presented on the webpage is your favourite, and why? Explain briefly.
Based on your programming experience, can you propose a new analysis that you think will be worthy to implement in Clang? Your proposal should ideally score high on the metrics used to evaluate a potential optimization: generality, payoff, and ease-of-implementation. Briefly explain why your proposal scores high on these metrics, use concrete examples wherever possible.

Do not use AI for this part

Part C : Understand Clang's CFG (10 marks)

Download and extract the files of LLVM 23.1.0. Clang's CFG format is available in llvm-project/clang/include/clang/Analysis/CFG.h. This consists of:

CFGBlock: a basic block, holding an ordered list of CFGElements plus a terminator Stmt*.
CFGElement: a tagged union over statement/expression nodes and special "pseudo-statement" kinds you won't find directly in the AST — Initializer, ScopeBegin/ScopeEnd, LifetimeEnds, AutomaticObjectDtor, TemporaryDtor, LoopExit, CleanupFunction, etc. (enum at CFG.h:57-84). These extra kinds are exactly what makes the CFG richer than "just the AST with edges" — it makes implicit destructor calls, temporaries, and scope exits explicit nodes.
CFG itself: owns the blocks, exposes getEntry()/getExit(), iteration, and a dump()/print() method.
CFGBuilder: the class that actually lowers a Stmt*/function body AST into the graph — reading its implementation in clang/lib/Analysis/CFG.cpp is the ground truth for why a given AST construct produces the blocks/edges it does (e.g. how &&/||, ?:, loops, try/catch, and switch fallthrough get lowered).

Build the clang executable using the following commands:

Prerequisites (already satisfied on this machine): CMake ≥3.20, Ninja, a C++17-capable compiler. Python3 is needed for the test suite (lit)

Configure

cmake -G Ninja -S llvm -B build \
  -DCMAKE_BUILD_TYPE=Release \
  -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" \
  -DLLVM_TARGETS_TO_BUILD="X86" \
  -DCMAKE_C_COMPILER=clang-12 -DCMAKE_CXX_COMPILER=clang++-12 \
  -DLLVM_USE_LINKER=lld \
  -DLLVM_ENABLE_ASSERTIONS=ON

Key flags:

- -S llvm -B build: source root is the llvm/ subdirectory, not the repo root; build is wherever you want the build tree (out-of-tree only — never build inside the source dir).
- LLVM_ENABLE_PROJECTS: which subprojects to build alongside core LLVM (clang, clang-tools-extra, lld, compiler-rt, polly, mlir, etc., semicolon-separated).
- CMAKE_BUILD_TYPE: Release for speed/size, Debug if you need full debug info to step through code in gdb (much slower build, far more disk — your existing tree uses Debug).
- LLVM_USE_LINKER=lld: dramatically faster links than GNU ld/gold, worth it especially for Debug builds.
- LLVM_ENABLE_ASSERTIONS=ON: catches internal invariant violations; on by default for Debug, off by default for Release — turn on explicitly if developing/debugging.
- Using clang-12/clang++-12 to compile LLVM itself builds noticeably faster than gcc/g++.

Build
```
cmake --build build              # builds everything configured
# or, narrower:
ninja -C build clang
	
```
Add -j N to ninja/cmake --build ... -- to cap parallelism if RAM-constrained (each parallel Debug compile/link job can use 1.5–2GB+).

Once you build the clang repo, you can dump a CFG for real code using clang -Xclang -analyze -Xclang -analyzer-checker=debug.DumpCFG -fsyntax-only foo.c, or to render it as a graph (needs Graphviz) using clang -Xclang -analyze -Xclang -analyzer-checker=debug.ViewCFG -fsyntax-only foo.c. You can also add debug statements in the clang code, e.g., using llvm::dbgs() << "Debug statement: ...", build and run again. Answer the following question:

Feed it small, deliberately tricky snippets of code (&&, ?:, loops with break/continue, a C++ destructor, a try/catch) and compare the dump to the source. Document the code snippets you tried and the resulting CFGs, and your observations/conclusions on the logic that generates the CFGs. Try to identify interesting/non-obvious observations.

Do not use AI for this part

Part D : Study Clang's Single Variable Constant Propagation Dataflow Analysis (5 marks)

Study the code of llvm-project/clang/unittests/Analysis/FlowSensitive/SingleVarConstantPropagationTest.cpp. You may also look at the code that implements the generic fixed-point algorithm for a dataflow analysis in runTypeErasedDataflowAnalysis() in clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp (headers defined in include/clang/Analysis/FlowSensitive/DataflowAnalysis.h, ...). You may need to execute the code on some example programs to be able to answer the following questions.

Draw the lattice of this dataflow analysis? Use the names of the structs, member fields, or variables in the code to annotate your lattice diagram, to clearly show the correspondences between your diagram and the actual code.
Briefly explain (in english, or using a mathematical expression, or pseudocode) the operation of ConstantPropagationAnalysis::transfer() which implements the transfer function of this dataflow analysis.
What are LatticeJoinEffect::{Changed,Unchanged} and why are they needed?

Do not use AI for this part