Theory makes beautiful programs
summary
An algorithm extracts MC/DC conditions from compiler control‑flow graphs rather than ASTs, using BFS/DFS and a topological sort to locate Boolean subexpressions and detect masking via graph algorithms; it’s implemented in GCC as a patch of about 3000 lines with roughly half tests. Instrumentation records per-decision bit accumulators and uses a few fast bitwise ops; runs with profile-enabled builds and g-cover to report which basic conditions independently affect decisions. It handles C, C++ and D, flags implicit checks, and currently fails on Go due to its CFG construction.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:54Coverage and MC/DC basics
- 3:16Branch coverage limits
- 6:46MC/DC in GCC
- 9:11Theory-driven programming
- 11:18Control flow and Boolean expressions
- 18:45Inferring decisions in CFG
- 29:26Masking in Boolean expressions
- 38:20Detecting masking edges
- 47:24Sub-expression isolation algorithm
- 50:15Theory-based benefits
- 52:21MC/DC instrumentation in GCC
- 58:02Q&A
related talks
01h 23mModified Condition and Decision Coverage in Gcc: Intro, Motivation & Tooling
44mWhat is your Algorithmic Core?
01h 25mPeeking Into Your Compiler
16mWhat Every C++ Programmer Should Know About Modern Compilers
01h 01mPath coverage in gcc
52mNon-conforming C++: the Secrets the Committee Is Hiding From You
01h 27mDangerous Optimizations! in C++ - Part Deux
40mLessons from two decades of writing bad code