Hash Consed Points-To Sets
summary
Implements hash-consed, interned points-to sets and operation tables inside the LLVM/SVF framework, changing only the data structure not the algorithm. Memoised unions and property operations reduce concrete set unions to cheap integer lookups. Evaluated on 16 C/C++ programs (≈9.5M LLVM lines): Andersen’s flow-insensitive runs ~1.86× faster (up to 3.21×), staged flow-sensitive ~1.69× faster (up to 2.23×), and SFS memory drops ≥4.93× (up to ≥15.52×). Flow-sensitive baselines often run out of 100GB without this fix.
AI-written summary · about
chapters (11)
- 0:00Intro
- 1:09Flow-Sensitive Points-to Analysis
- 1:59Motivation
- 2:40Motivating Example
- 3:35Hash Consing
- 4:13Hash Consed Points-To Sets: Interning
- 4:50Hash Consed Points-To Sets: Memoisation
- 5:38Revisiting Our Example
- 6:20Exploiting Set Properties: Commutative Operations
- 10:20Evaluation: Implementation
- 12:40Evaluation: Flow-Sensitive Unions
related talks
16mA Compiler for Fused Relational Operations on Multisets
22mReconciling High-level Optimizations and Low-level Code in LLVM
21mFlow-Analysis-Based Closure Optimization
34mHash Maps: more room at the bottom
15mSealing Pointer-Based Optimizations Behind Pure Functions
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
18mFast and Efficient Boolean Unification for Hindley-Milner-Style Type and Effect...
01h 11mProgramming language memory models: Problems, solutions, and directions