NONA is a translator of a code selector description (CS) into code for solving code selection and possibly other back-end tasks. The code selector 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 code selector description can be used also to locate machine dependent code for solving other back-end task, e.g. register allocation. To describe code selector description a special language is used.
An code selector 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 code selector 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.