This directory NONA contains code selector description translator.
NONA is a translator of a machine description (MD) into code for
solving code selection and possibly other back-end tasks.  The machine
description is mainly intended for describing code selection task
solution, i.e.  for determining by machine-independent way a
transformation of a low level internal representation of source
program into machine instruction level internal representation.  But
the machine description can be used also to locate machine dependent
code for solving other back-end task, e.g. register allocation.  To
describe machine description a special language is used.

An machine description describes mainly tree patterns of low level
internal representation with associated costs and semantic actions.
NONA generates the tree matcher which builds cover of low level
internal representation by the tree patterns with minimal cost on the
first bottom up pass and fulfills actions associated with the choiced
tree patterns on the second bottom up pass.  Usually the actions
contain code to output assembler instruction.

Analogous approach for solving code selection task is used by modern
generator generators such as BEG, Twig, Burg and Iburg.  The tree
matcher generated by NONA uses algorithm similar to one of BEG and
Iburg, i.e. the algorithm is based on dynamic programming during
fulfilling code selection.

Although the algorithm used by BURG and based on dynamic programming
during tree pattern matcher generation time is considerably more fast,
it is not acceptable for us.  Its main drawback which is to need usage
of less powerful machine description results in necessity of usage of
more machine-dependent low level internal representation.  For
example, the special internal representation node types for 8-bits,
16-bits constants besides 32-bits constants would be needed.  Also the
algorithm used by BURG is considerably more complex.

Tree pattern matchers generated by NONA also can work with directed
acyclic graphs besides trees.  This feature is useful when target
machine instruction is generated from the internal representation
which is result of some optimizations such as common sub-expression
elimination.

  To install NONA see file INSTALL in the current directory.

  Documentation of NONA is in files `nona.1', `nona.txt', `nona.dvi',
`nona.ps', `nona.info*', `nona*.html', `nona*.rtf'.

Please send bug reports and comments to [email protected]

Vladimir Makarov