I'm trying to build a complexity analysis tool and I need an algorithm for constructing the control flow graph (to get cyclomatic and eventually essential complexity). I couldn't find any pseudocode online so I just got down to writing it. Using recursion seems to have been a bad way to go; my code handles most simple cases but with deeper nesting of control structures errors arise.
Is there somewhere I can find pseudocode for constructing the CFG?
(For the curious I'm doing this for VHDL.)
To create a CFG you begin with an Abstract Syntax Tree (AST). So I assume you have an AST available. The first step is to collect the nodes in the tree into basic blocks. This step is optional but reduces the number of nodes in the CFG which improves performance. So if you have the source code:
if a:
x = x + 1
print(b)
else:
while c:
print(d)
y = y + 1
you get a tree structure of basic blocks (here denoted BB):
[(BB(if a:), [
[(BB(x = x + 1, print(b)), [])]
[(BB(while c:), [
(BB(print(d)), [])
]), (BB(y = y + 1), [])]
])]
Note that the if-statement has two children lists and the while-statement has one. Note also that every successor of a block is either the first element in a children list or "follows" the block. Thus,
succ(BB(while c:)) = [BB(print(d)), BB(y = y + 1)]
cause the first block is the body of the loop and the second block the block reached after exiting the loop.
Given the tree above, we can create a recursive algorithm that computes the successors of every block:
def connect(tree, parent):
tails = [parent] if parent else []
for bb, children in tree:
for t in tails:
succ[t].append(bb)
if type(bb) == if-block:
if_tails = connect(children[0], bb)
else_tails = connect(children[1], bb)
tails = if_tails + else_tails
elif type(bb) == while-block:
tails = connect(children[0], bb)
for t in tails:
succ[t].append(bb)
tails = [bb]
else:
tails = [bb]
return tails
The "tails" are the predecessors of the next block to operate on. The algorithm becomes a bit hairier when you involve other kinds of control flow like continue, break, and exceptions.
