CoSy-fSDL-mode examples

Here we will present some short examples for CoSy-fSDL mode. We assume a basic block graph is defined in a procedure as follows. In CoSy this can be done in a view specification of an engine. We that the basic block graph has already been constructed and entered into relation BlockGraph.

  
domain mirProcBody <  
      BlockGraph:      SGRAPH(mirBasicBlock),
      ReverseBlocks:   SGRAPH(mirBasicBlock),
      ReachableBlocks: SGRAPH(mirBasicBlock),
      Dominators:      SGRAPH(mirBasicBlock),
      SelfDom:         SGRAPH(mirBasicBlock),
      USED:            BIPUNI(mirBasicBlock,mirLocal),
      Livein:          BITUNI(mirBasicBlock,mirLocal,Livein),
      Liveout:         BITUNI(mirBasicBlock,mirLocal,Liveout)
   >;

Then we may write the following specifications.

  
/* Compute the inverse of the basic block */
EARS ComputeReverse()
{
   RANGE b <= BlockGraph;        // implicit parameter graph BlockGraph
   RULES
      ReverseBlocks(b,b1) :- BlockGraph(b1,b);
}

This EARS of order 1 just builds up the reverse basic block graph, a relation .ReverseBlocks.. The automatic-parameter-range declaration tells that the order loop variable is to be initialized from the node domain of graph BlockGraph. The following shows how the generated routine may be called from C code (CoSy):

  
   BlockGraph = mirProcBody_get_BlockGraph(procbody);
   // or:
   // BlockGraph = SGRAPH_mirBasicBlock_create();
   //     add also some nodes with addnode functions..
   mirProcBody_set_ReverseBlocks(SGRAPH_mirBasicBlock_create());
   ReverseBlocks = mirProcBody_get_ReverseBlocks(procbody);
   CopyNodes (BlockGraph, ReverseBlocks);  // should copy the nodes of the SGRAPH
   ComputeReverse (BlockGraph,  ReverseBlocks);

The order of the parameter graphs to .ComputeReverse. is alphabetically.

The next example computes dominator analysis. The first rule group initializes. Initially all nodes dominate all others except that the entry node does not dominate anyone.

  
EARS ComputeDominators()
{
 {
   RANGE b <= Dominators; b1 <= Dominators;
   RULES

   Dominators(b,b1) :- BlockGraph.pred(b,PredecessorBlock);
                     // initially a node dominates each other node.
                     // The dominators of the entry node, however, are left empty. 
   SelfDom(b,b);     // this predicate is used for adding each node to a 
                     // set Dominators during the processing in ComputeDominators
 }
 {
   RANGE b <= BlockGraph;
   RULES

   // a node dominates another if all predecessors dominate the other
   Dominators(b,b1) :- FORALL p: BlockGraph.pred(b,p), Dominators(p,b1);
   Dominators(b,b1) :- SelfDom(b,b1);            
 }
}

|BlockGraph.pred(b,p)| denotes all predecessors of .b. in the graph .BlockGraph.. For these .p. also the dominator relation to .b1. must hold. Note that .b. and .b1. are existentially quantified variables while .p. is all-quantified. The rule with predicate .SelfDom. is necessary because currently additions of single nodes to sets (in clauses) is not possible, everything has to be expressed in terms of edges (predicates).

provides functor transparency, i.e. it is transparent which functors have been used to implement the graphs. This is automatically infered from the data model. The code for the graph navigations (functor method calls, access function calls) is generated accordingly.

The call sequence in a calling program could be:

  
   ComputeDominators(BlockGraph, Dominators, SelfDom);

Note: The non-ground facts are computed first in each rule group.