Class Hierarchy Analysis in LLVM

An out-of-tree LLVM 22 pass plugin implementing CHA-based virtual call devirtualization using the LLVM New Pass Manager.

---

Overview

This pass recovers C++ class hierarchies in LLVM IR without requiring -fwhole-program-vtables or any Clang type metadata.

It computes:

• The class hierarchy from _ZTI typeinfo globals
• The virtual function slots per class from _ZTV vtable globals
• Direct-call rewrites for indirect virtual calls when a slot has one recovered target

Based on:

• Dean, Grove, Chambers Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, ECOOP 1995
• Bacon & Sweeney Rapid Type Analysis for C++, OOPSLA 1996

---

Why metadata-free?

Clang's built-in devirtualization (-fwhole-program-vtables) requires recompiling with that flag set. This pass works on any C++ IR including pre-compiled translation units and lifted binaries by reading the vtable and typeinfo globals.

---

Project Structure

CHA/
├── include/cha/
│   ├── CHA.h             # Analysis class declaration
│   ├── ClassHierarchy.h  # Hierarchy data structure
│   └── VTableInfo.h      # Vtable recovery result
├── lib/
│   ├── CHA.cpp           # Core analysis logic
│   └── CHAPass.cpp       # LLVM pass plumbing
├── test/
│   └── simple.cpp        # Test C++ with virtual dispatch
├── scripts/
│   └── run.sh
└── CMakeLists.txt

---

Build

mkdir build && cd build
cmake .. -DLLVM_DIR=$(llvm-config --cmakedir)
make

Run

# Compile test to IR
clang++ -O0 -emit-llvm -S -fno-discard-value-names test/simple.cpp -o test/simple.ll

# Run pass
opt -load-pass-plugin ./build/CHA.so -passes=cha -disable-output test/simple.ll

Example Output

>>> RUNNING CHA MODULE pass
== Class Hierarchy Analysis ==
Classes found: 3
  class Animal {
    slot[0]: <offset-to-top / rtti / pure>
    slot[1]: <offset-to-top / rtti / pure>
    slot[2]: _ZN6Animal3eatEv
    slot[3]: _ZN6Animal4moveEv
  }
  class Dog {
    slot[0]: <offset-to-top / rtti / pure>
    slot[1]: <offset-to-top / rtti / pure>
    slot[2]: _ZN3Dog3eatEv
    slot[3]: _ZN3Dog4moveEv
  }
  class Cat {
    slot[0]: <offset-to-top / rtti / pure>
    slot[1]: <offset-to-top / rtti / pure>
    slot[2]: _ZN3Cat3eatEv
    slot[3]: _ZN6Animal4moveEv
  }

== Inheritance Edges ==
  Animal -> Dog
  Animal -> Cat

== Devirtualization ==
  slot 0 has multiple targets (3), skip
  slot 1 has multiple targets (2), skip
Indirect calls seen: 2
Indirect calls rewritten: 0