Categories

Yet Another Pointer Analysis for LLVM

Technical Area

Software Correctness

We are pleased to announce that Galois is open-sourcing Yapall (Yet Another Pointer Analysis for LLVM), a static pointer analysis tool for programming languages that compile to LLVM.

Developed as a part of the POLYMORPH project (itself part of the larger DARPA V-SPELLS program), this remarkable tool is instrumental in structural analysis of legacy applications and the generation of structural models of legacy software. 

We are excited to open-source Yapall to the wider software development community. Static pointer analysis is critical for a wide range of applications, such as memory safety assurance, code optimization, code understanding, and legacy code integration.

Yapall is the latest of many pointer analysis approaches for LLVM. In contrast to previous efforts such as cclyzer++ and the original cclyzer, Yapall has a simpler, sound, Andersen-style memory model and is implemented in the open-source, highly parallel and performant Ascent Datalog engine.

Use-cases of Yapall include:

  • Creation of call graphs with precise handling of indirect function calls and virtual method calls
  • Precise interprocedural control- and data-flow analysis
  • Answering may-alias queries

Notable features include:

  • On-the-fly call graph construction
  • Configurable k-callsite context-sensitivity
  • Support for models of external/library functions
  • Online documentation
  • Parallel evaluation due to implementation in Ascent
  • Rust interface
  • Tested on LLVM code up to LLVM 14

Yapall does not include array-, field-, nor flow-sensitive analysis, nor support for heap cloning. 

The analysis is described in section 5.7 of the OOPSLA 2023 paper Bring Your Own Data Structures to Datalog.

Learn more about Yapall in the documentation HERE, or take a closer look at the source at the GitHub repo HERE.