Steensgaard Pointer Analysis in LLVM

An out-of-tree LLVM (v16+) pass plugin implementing Steensgaard’s unification-based pointer analysis using the LLVM New Pass Manager.

This project focuses on building real compiler infrastructure rather than toy analyses, working directly at the LLVM IR level.

---

Overview

This repository contains a flow-insensitive pointer analysis based on Steensgaard’s algorithm, implemented from scratch as a modern LLVM pass.

The analysis computes points-to relationships for:

• stack allocations
• globals
• heap objects allocated via malloc

The primary goal is to explore the trade-off between speed and precision in pointer analysis while gaining hands-on experience with LLVM internals.

---

Features

• LLVM New Pass Manager compatible plugin
• Steensgaard (unification-based) pointer analysis
• Allocation-site heap abstraction
• Flow-insensitive, intraprocedural analysis
• Clean separation between:
  • analysis logic
  • points-to representation
  • LLVM pass plumbing
• Human-readable analysis output via opt

---

Why Steensgaard?

Steensgaard’s analysis is:

• extremely fast (almost linear time)
• coarse but scalable
• widely used as a baseline in compilers

It is ideal for:

• understanding pointer abstraction
• experimenting with IR-level modeling
• serving as a foundation for more precise analyses later

This project intentionally starts with Steensgaard before moving to more precise approaches such as Andersen-style inclusion-based analysis in a separate effort.

---

Project Structure

LLVMPA/
├── include/pa/          # Public analysis interfaces
│   ├── Steensgaard.h
│   └── PointsToSet.h
├── lib/                 # Implementations
│   ├── Steensgaard.cpp
│   ├── PointsToSet.cpp
│   └── PointerAnalysisPass.cpp
├── test/                # Small C test programs
│   ├── simple.c
│   ├── alias.c
│   ├── heap.c
│   └── structs.c
├── scripts/
│   └── run.sh           # Helper script to run the analysis
├── CMakeLists.txt
└── README.md