Datalog for CFG analysis: How and Why

Avishek Sen Gupta on 22 June 2025

---

Abstract

This post is about experiments in building graph analysis techniques for Control Flow Graphs, and other graphs used in program analysis, in Datalog. One of the examples we will see is how to write a basic block construction algorithm in about 14 lines of Datalog code. We will be specifically using Souffle as the Datalog implementation.

This post has not been written or edited by AI.

We will demonstrate a couple of examples to demonstrate the effectiveness of Datalog.

• Basic Block calculation ~32 LoC in Java, ~5 LoC in Datalog
• Dominator calculation ~27 LoC in Java, 2 LoC in Datalog

Datalog as a subset of Prolog

Souffle: A scalable, typed implementation of Datalog

Datalog as a better SQL

Basic Block Analysis

Dominator Identification

References

• Basic Block construction
• Dominators in Datalog

---