Topological Sorting of Basic Blocks in LLVM

Question

I would like to be able to get the basic blocks in a function in topological order. There is an iterator available which iterates over the basic blocks in a function, however I am not sure if it does it in topological order. I wasn't able to get the next basic block for a particular basic block and wasn't able to do topological sorting myself.

You can assume there are no loops in the CFG.

Answer 1

In the general case, this is impossible because BBs don't form a DAG. A topological order is only defined for a DAG - a graph without cycles; BBs within a function may form cycles (loops, etc).

Your best approximation IMHO is to decompose the BB graph into SCCs (Strongly Connected Components). LLVM already has tools to do that: see include/llvm/ADT/SCCIterator.h, and also tools/opt/PrintSCC.cpp.

The latter, in fact, will already print the SCCs of a function in reverse topological order, invoked like this:

$ opt -print-cfg-sccs <bitcode file>

Update (16-Sep-2013): See also this blog post.