A first example

First consider a small program analysis example, the transitive closure over basic blocks. Typically, basic blocks are sequences of statements started by labels and ended by jumps (straight-line code). Each block is connected to other blocks via the jumps and the labels. A block B1 is predecessor of another block B2 if it ends with a jump to B2. Then B2 is a successor to B1, and this relation makes up the basic block graph.

If we want to know which blocks are reachable from a block, we have to construct the transitive closure operation on the basic block graph. Assume our block looks like (in AST):^1.1

A similar CoSy-fSDL definition would be:

A similar definition in Java syntax could be:

With this data model we may write a specification that computes the transitive closure of the graph BlockGraph into the graph ReachableBlocks. This specification is in the style of Datalog.

This EARS (edge addition rewrite system) specifies with two rules how a relation ReachableBlocks over blocks may be constructed by querying another relation BlockGraph. The first rule means that a block b1 which is a successor to a block b in relation BlockGraph should also be a successor in Relation ReachableBlocks. The second rule describes the transitive closure: if there is a successor block s to b in relation BlockGraph which has another reachable block b1, then b1 should also reachable from b.

We could also specifiy the rules in a way which is based on graph-rewrite rules:

Or we could specify it set-based, with path expressions:

For the EARS a routine in the target language (C or Java) with name ComputeReachableBlocks is generated. This routine walks over all blocks from the parameter set BlockSet and applies the two rules. Because the rules are recursive, the rule applications are embedded in a fixpoint evaluation loop. To see which code generates for this specification, feed the file example-reachable.ox from directory doc to . The generated C code may be found in Appendix 7.3.