Meta modeling as a method allows to devise languages suited for speci c application domains, e.g. for describing the structural or behavioral aspects of software systems. As meta models constitute an abstract syntax (often enriched with static semantics) there exist obvious similarities to the area of formal languages. The research e ort described in this paper is intended to examine to what extent and to what bene t compiler construction concepts, namely the data- ow analysis method, can be transferred to the modeling domain in order to validate static semantics and perform abstract interpretations on models.
language which is mainly intended to be used to validate constraints by performing static queries on a model's elements, OCL does not contain semantics which would enable a xed-point analysis since, in the case of cyclic dependencies this would require a continuous reevaluation the DFA's equation system. Finally, complex navigation statements make OCL rules very prone to be invalidated if the structure of the underlying meta model changes, often requiring extensive adjustments.
Since models comprise a graph structure, de ning and calculating information ow enables an advanced analysis of a model's properties. These may either be properties of the graph structure itself, e.g. strongly connected component regions, or semantic attributes, e.g. the availability of a resource created at one point in a control- ow model in some other part of the model, This research is dedicated to adapting the data- ow analysis (DFA) approach commonly used in compiler construction for deriving optimizations from a program's control- ow graph, to modeling, thus enabling a xed-point analysis on (meta) models. 2
Since the de nition of static semantics is a vital step when developing formal languages, many di erent techniques have been considered for this purpose.
The OCL can be considered a comparatively simple language for
requirements exceeding syntactic expressiveness and by design is very well-integrated
into the modeling domain. A critical evaluation of its expressive power can be
found in [
Approaches considering the use of formal semantics include graph
transformations, abstract state machines or rst order logic (cf. [
Several authors use DFA-based methods to derive information from models.
In [
The focus in these cases is, however, directed towards implementing a speci c case study. To the best of our knowledge, there is no other research e ort with the goal of applying the concept of a xed-point based DFA calculation to models. 3
Both meta models and (context-free) grammars operate on di erent layers of abstraction. For grammars, these usually consist of EBNF, CFGs and language expressions. In the widely-used MOF one distinguishes between meta-meta (M3), meta (M2) and model (M1) layer. Because of conceptual similarity, both techniques can be aligned according to their levels of abstraction. This alignment requires that data- ow equations are attached to language artefacts (i.e. M2 meta classes) and instantiated/executed for expressions, i.e. M1 objects.
Since attribute grammars are a well-proven extension of this design, it was decided that this strategy will also be employed in the de nition of data- ow equations: An attribute de nition consisting of an identi er and a data-type can be bound to several meta model classes through the use of attribute occurrences. Semantic rules (corresponding to data- ow equations) are assigned to attribute de nitions and attribute occurrences to calculate initialization and iteration values, respectively. Data- ow between attributes occurs if a semantic rule requests the value of another attribute as input.
(a) Data- ow analysis meta model (b) Calculate predecessors To stay consistent with the notion of modeling and to minimize frictional losses between di erent techniques, it is desirable to represent DFAs themselves as models, i.e. to provide a meta model which in the described alignment hierarchy acts as an extension of the M3 layer (cf. Figure 1(a)).
To calculate a DFA for a given model, attribute occurrences assigned to meta classes need to be instantiated for model elements derived from these classes. While the instantiation process is straightforward, it has to be noted that this must happen in compliance with principles like generalization, i.e. if de ned for a super class, attributes must be inherited by instances of sub classes.
An example is shown in Figure 1(b) which calculates the transitive closure of predecessor nodes in a simple control- ow graph. The class node has an assigned attribute occurrence of the type all predecessors. The associated rule, which is repeatedly executed for all nodes, recursively creates the union of direct predecessors and the value of all predecessors at preceding nodes.
The xed-point calculation signi cant di ers from traditional DFA techniques: Since semantic rules may request the value of arbitrary attributes as input when they are executed, there exists neither an inherent ow direction nor any prior knowledge about output relationships between attribute instances. Since the commonly used worklist algorithm depends on this information, it is not applicable in this context. To accomodate for this, an algorithm has been developed that dynamically records input/output relationships by executing the rules recursively to create a dependency graph which can then be used as a basis to derive a nearly optimal execution order, thus minimizing the amount of rule executions.
The research e ort described in this abstract has to cover the following issues: De nition and Alignment To transfer the method of DFA to the modeling domain, similarities and di erences between both application areas must be identi ed and a new de nition language has to be devised and aligned with the modeling techniques.
DFA Algorithms Suitable algorithms for calculating DFA equation systems have to be devised and proven to be correct.
Complexity and Performance The practical and theoretical performance of di erent DFA solving algorithms has to be evaluated.
Tooling and Use Cases To prove the feasability of this approach, a tooling environment has to be provided alongside the implementation of several use cases which need to be evaluated against implementations based on alternative theoretical foundations.
While e orts for DFA de nition and integration into modeling are well advanced (as described in the previous section), a formalization of these results is still in order. The same goes for the DFA solving algorithm which has proven to perform very well in comparison to adaptions of conventional algorithms like the work list method.
The Model Analysis Framework (MAF2) is a fully functional prototype providing tooling support for the described concepts. It is built upon Eclipse modeling techniques, namely the Eclipse Modeling Framework (EMF), an implementation of the MOF standard. Once all artefacts required for an analysis (i.e. meta models, models and attributions based on the meta model shown in Figure 1(a)) are loaded into the respective repositories, the de ned attributes are instantiated for the model's elements and handed to the selected evaluation algorithm. First experiments have shown that the developed algorithm preforms much better in calculating the result values than a traditional worklist algorithm that has been enhanced with the ability to handle dynamically discovered output dependencies.
Currently implemented case studies (which are available from the code
repository) include: Calculating properties of control- ow graphs like transitive
predecessor/successor sets and strongly connected components (SCC), de nition/use
relationships in work ows and the hierarchical subdivision of control- ows into
its Single-Entry-Single-Exit (SESE) components using a token- ow algorithm
(cf. [