-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnona-1.html
59 lines (55 loc) · 2.71 KB
/
nona-1.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
<META NAME="GENERATOR" CONTENT="LinuxDoc-Tools 0.9.66">
<TITLE>NONA (code selector description translator): Introduction</TITLE>
<LINK HREF="nona-2.html" REL=next>
<LINK HREF="nona.html#toc1" REL=contents>
</HEAD>
<BODY>
<A HREF="nona-2.html">Next</A>
Previous
<A HREF="nona.html#toc1">Contents</A>
<HR>
<H2><A NAME="s1">1.</A> <A HREF="nona.html#toc1">Introduction</A></H2>
<P>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.</P>
<P>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.</P>
<P>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.</P>
<P>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.</P>
<P>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.</P>
<HR>
<A HREF="nona-2.html">Next</A>
Previous
<A HREF="nona.html#toc1">Contents</A>
</BODY>
</HTML>