# Irreducible loops

DevFeed: [Irreducible loops](<https://devfeed.tech/articles/irreducible-loops-31129.md>)

Original publisher: [Read original article](<https://maskray.me/blog/irreducible-loops>)

Published: 2026-07-12T07:00:00Z

Content type: tutorial

Language: en

Sources: [MaskRay](<https://devfeed.tech/sources/maskray.md>)

Topics: [Graphs](<https://devfeed.tech/topics/graphs.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [Code](<https://devfeed.tech/topics/code.md>), [LLVM](<https://devfeed.tech/topics/llvm.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [code](<https://devfeed.tech/tags/code.md>), [entries](<https://devfeed.tech/tags/entries.md>), [flow](<https://devfeed.tech/tags/flow.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [llvm](<https://devfeed.tech/tags/llvm.md>), [loops](<https://devfeed.tech/tags/loops.md>), [static](<https://devfeed.tech/tags/static.md>), [structure](<https://devfeed.tech/tags/structure.md>)

## AI overview

This technical post explains why dominator-based natural-loop detection fails for irreducible control-flow graphs, which can have multiple entries. It describes reducibility, the irreducible three-node pattern, and a DFS-based loop-nesting forest using Havlak's convention.

## Source excerpt

The dominator tree lets us identify natural loops: a back edge T->H whose head H dominates its tail T defines a loop with the single entry H. This works only for reducible control flow graphs. Optimized machine code and decompiler output routinely contain irreducible loops, which have more than one entry and thus no dominating header, so the dominator-based method cannot see them. This post builds a loop-nesting forest for an arbitrary CFG with the single-pass depth-first search of 韦韬、毛剑、邹维、陈宇(Tao Wei, Jian Mao, Wei Zou & Yu Chen) A New Algorithm for Identifying Loops in Decompilation, SAS 2007 (The 14th International Static Analysis Symposium).