---
id: gcc-0001
repo: gcc
severity: MEDIUM
status: PATCHED
created: 2026-03-23
patched: 2026-03-23
patch: defects/gcc/patch/gcc-0001-gcov-blocked-map.patch
---

## Defect

**File:** `gcc/gcov.cc:980`
**Pattern:** `std::find(vector.begin,end,w)` in Johnson's algorithm for coverage analysis
**Complexity:** `O(V²)`
**Language:** C++

## Description

GCC's coverage analysis (`gcov`) uses Johnson's algorithm to find all simple cycles in the control flow graph. At line 980, the algorithm checks whether a vertex is blocked using `std::find` over a `std::vector`. This linear membership check is performed for every vertex examined during the cycle-finding DFS, causing the blocked-set lookup to dominate runtime and degrading the algorithm from near-linear to O(V²) for dense CFGs.

## Fix

**Replace:** `std::find(blocked.begin(), blocked.end(), w) != blocked.end()`
**With:** `blockedSet.count(w) > 0`
**Data structure change:** `std::vector<vertex_t> blocked → std::unordered_set<vertex_t> blockedSet`

## Work required

- [ ] Patch in `defects/gcc/patch/`
- [ ] Unit test — asserts exact operation counts before/after (in `defects/gcc/unit/`)
- [ ] Integration test (in `defects/gcc/integration/`)
- [ ] Benchmark — before/after on V=100,200,400,800 (in `defects/gcc/bench/`)
- [ ] White paper section