Compiler & LLVM Passes

Two LLVM IR analysis passes implemented in C++17 with LLVM 19: a Local Value Numbering pass for redundancy detection inside a basic block, and a Liveness Analysis pass computing UEVar, VarKill, LiveIn, LiveOut over CFGs with back edges.

View on GitHub

Highlights

• Built LocalValueNumbering and Liveness as LLVM plugin shared libraries registered with the new pass manager
• LVN uses value-number and expression tables to flag redundant binary computations within a basic block
• Liveness uses iterative fixed-point updates over CFG successors, handling back edges and self-use patterns (a = a + 1)
• Worked directly with LLVM IR instructions, basic blocks, and CFG traversal via the LLVM 19 C++ API

Local Value Numbering

The LocalValueNumbering pass scans IR instructions within each function and assigns value numbers to operands and expressions to flag redundant computations.

Core data structures:

• ValueNumberTable — maps stringified operands and instructions to value numbers
• ExpressionTable — maps (opcode, VN1, VN2) tuples to value numbers; a repeated tuple signals a redundant expression

Binary, load, and store instructions are handled separately in LVN::generateLVNMap. The pass operates within a single basic block (local analysis only).

Pass output: value numbers assigned per instruction; redundant expressions flagged

Liveness Analysis

The Liveness pass computes per-basic-block liveness information using the standard dataflow equations, iterated until convergence:

• LiveOut(BB) = ∪ LiveIn(Successors)
• LiveIn(BB) = UEVar(BB) ∪ (LiveOut(BB) − VarKill(BB))

CFG traversal uses LLVM’s successor iterators. The iterative loop runs until no LiveIn or LiveOut set changes — correctly handling back edges. A special case handles self-use patterns (a = a + 1) where a variable appears on both sides of an assignment.

Iterative fixed-point loop: LiveOut propagated from successors, LiveIn recomputed each pass

Pass output: UEVar, VarKill, LiveOut per basic block across a CFG with branches

Technical Summary