Single source path problems (SSPPs)

There is a special variant of EARS which can solve single source path problems (SSPPs) [Tar81]. An SSPP is a path problem in a graph which is described by a path expression (or a set of predicates, like in EARS) and which is applied to one single source node of the graph. It delivers all nodes which are reachable from the source node under the predicates (the path expression). These nodes are called result set.

A GRS may contain several SSPP rules. The the source node of the SSPP and the result set of such a rule can be declared with a range declaration (section 3.3). The node is then initialized to the corresponding parameter of the generated routine, and the parameter set of the range declaration is used as the result set. SSPP rule tests are not generated among those rule tests which result from normal rules (in the order loops). Instead they are extracted and printed after them.

The following example solves a SSPP for a procedure and all its statements. It collects all assignments that are in the blocks' statement lists.

EARS PrepareReachingDefinitions()
{
   RANGE Proc <= ProcGlobal <-> list_of_definitions: SET(STMT);
   RULES
   list_of_definitions(Proc,Ass) :-
      Body(Proc,PBody),
      LinearBlocks(PBody,Block),
      Stmts(Block,Ass),
      Ass ~ Assign
   ;
}

SSPP rules can also be used nicely to write down walking e.g. over statement lists and perform actions on them. The following example collects all assignment statements in a parameter set list_of_definitions. They also are entered into a global class of definitions for objects, with a target predicate side effect action. This global class is attached to global state handle (e.g. of a CoSy engine), and must be passed as parameter to the generated routine CollectAssigns.

EARS CollectAssigns(state: StateType)
{
   RANGE Proc <= ProcGlobal <-> list_of_definitions: SET(STMT);
   RULES
   list_of_definitions(Proc,Ass), 
      {* EnterInDefinitionClasses(state,Ass); *}
   :-
      Body(Proc,PBody),
      LinearBlocks(PBody,Block),
      Stmts(Block,Ass),
      Ass ~ Assign
   ;
}