Next: Examples and Miscellaneous Up: Meta-Optimizations for XGRS code Previous: Bidirectional edge optimization

Index edge optimization

(only tested in CoSy-fSDL-mode)

If an XGRS has order 2, and uses attribute equality tests on its rule test root nodes, it can be speed up by the use of index structures.

$\begin{verbsyntax}\onerule{IndexDeclaration}{'INDEX' Variable ':' IndexName [ 'F... ...List ] ';'} \onerule{IndexName}{'HASHTABLE' \vert 'PLAINTABLE'} \end{verbsyntax}$

If an index is specified on a variable, the code generation changes as follows. First the order loop node domain of the specified variable is traversed to collect all objects into the index structure. Then the index is used as virtual edge between the two root nodes of the rule. This virtual edge is traversed during rule test. The rule (and may be the rule group) gets order 1 and will be generated with other rules that have the same (single) range.

Currently there are hash tables (multi-valued index) and plain pointer tables (one-valued).^4.1 emits calls to C modules which both can be found in the sol-library.

$\begin{examplefoot}EARS EquivalenceOfExpressions() \{ RANGE i1 <= consset(Expre... ...onst{ Value => V1 }, V == V1 // attribute equality test ; \} \end{examplefoot}$

transforms logically into

$\begin{examplefoot}EARS EquivalenceOfExpressions() \{ RANGE i1 <= consset(Expre... ...{ Value => V }, i2 ~ IntConst{ Value => V1 }, V == V1 ; \} \end{examplefoot}$

The index function may be accompanied with the following functions in order:

1.

hash function: Hashes an object into a int hash value. C signature:

$\begin{examplefoot}int hash(<NodeType> n); \end{examplefoot}$

2.

compare function: compares two objects on equality. Should behave like strcmp: give back 0 if object 1 is equal to object 2, -1 if smaller, 1 if greater. Example:

$\begin{examplefoot}int compare_Expression(Expression e, Expression e2) \{ if (e... ...d) return 0; if (e->Kind > e2->Kind) return 1; return -1; \} \end{examplefoot}$

If one of them is left out, chooses a standard function (probably behaving inefficient). Choosing appropriate hash functions is quite important. Also note that the hash function has to be specified anyway: if it is left out, a dummy void function has to be specified instead.

Next: Examples and Miscellaneous Up: Meta-Optimizations for XGRS code Previous: Bidirectional edge optimization

Uwe Assmann
1998-12-22