-
Notifications
You must be signed in to change notification settings - Fork 0
/
nona-2.html
243 lines (216 loc) · 8.94 KB
/
nona-2.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
<!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): Code selector description language</TITLE>
<LINK HREF="nona-3.html" REL=next>
<LINK HREF="nona-1.html" REL=previous>
<LINK HREF="nona.html#toc2" REL=contents>
</HEAD>
<BODY>
<A HREF="nona-3.html">Next</A>
<A HREF="nona-1.html">Previous</A>
<A HREF="nona.html#toc2">Contents</A>
<HR>
<H2><A NAME="s2">2.</A> <A HREF="nona.html#toc2">Code selector description language</A></H2>
<P>An code selector description describes mainly tree patterns of low
level internal representation with associated usage constraints, costs
and semantic actions. The tree pattern may contains terminal
representing the low level internal representation node. Nonterminals
serves to designate the tree patterns. Each terminal or nonterminal
may have attribute which is evaluated in actions.</P>
<H2><A NAME="ss2.1">2.1</A> <A HREF="nona.html#toc2.1">Layout of code selector description</A>
</H2>
<P>Code selector description structure has the following layout which
is similar to one of YACC file.
<BLOCKQUOTE><CODE>
<PRE>
DECLARATIONS
%%
RULES
%%
ADDITIONAL C/C++ CODE
</PRE>
</CODE></BLOCKQUOTE>
The `%%' serves to separate the sections of description. All
sections are optional. The first `%%' starts section of rules and is
obligatory even if the section is empty, the second `%%' may be absent
if section of additional C/C++ code is absent too.</P>
<P>The section of declarations contains declarations of terminals by
names of constants which represent modes of the low level internal
representation nodes. The section also may contain declarations of
commutativeness of some terminals. Type and union declarations can be
used to declare types of terminal and nonterminal attributes. And
finally the section may contain subsections of code on C/C++.</P>
<P>The next section contains rules. Each rule describes tree pattern,
nonterminal designating the pattern, the pattern cost, its usage
constraint, and associated action. The rule list can be empty. In
this case the code selector description is used to locate machine
dependent code and generated code of the tree pattern matcher can not
be used.</P>
<P>The additional C/C++ code can contain any C/C++ code you want to use.
Often functions which are not generated by the translator but are
needed to work with code selector description go here. This code
without changes is placed at the end of file generated by the
translator.</P>
<H2><A NAME="ss2.2">2.2</A> <A HREF="nona.html#toc2.2">Declarations</A>
</H2>
<P>The section of declarations may contain the following construction:
<BLOCKQUOTE><CODE>
<PRE>
%term <TYPE> IDENTIFIER ...
</PRE>
</CODE></BLOCKQUOTE>
All terminals must be defined in constructions of such kind (or in
construction `%commutative'). The same identifier can be defined
repeatedly. The identifier is a name of constant which represents
mode of the low level internal representation node. If the user needs
usage of attributes of different types, the terminal attribute type
can be given in this construction. The union declaration can be used
for this.
<BLOCKQUOTE><CODE>
<PRE>
%union {
any thing that can go inside a `union' in C/C++
}
</PRE>
</CODE></BLOCKQUOTE>
The last such construction in the declarations section specifies the
entire collection of possible types for attribute values. For
example:
<BLOCKQUOTE><CODE>
<PRE>
%union {
IR_node_t node;
int number;
}
</PRE>
</CODE></BLOCKQUOTE>
This means that the two alternative types are `IR_node_t' and `int'.
They are given by names `node' and `number'. These names are used in
the type and commutativeness declarations to instruct type of
attribute for a terminal or nonterminal. The type declarations has
the following form:
<BLOCKQUOTE><CODE>
<PRE>
%type <TYPE> IDENTIFIER ...
</PRE>
</CODE></BLOCKQUOTE>
The construction can be used when union declaration is present.
Here `TYPE' is a name of type given in union declaration. If the type
of terminal or nonterminal is not given its type is believed to be
`CS_TYPE' (see next section). The identifier is one of terminal or
nonterminal. The construction
<BLOCKQUOTE><CODE>
<PRE>
%commutative <TYPE> TERMINAL_IDENTIFIER ...
</PRE>
</CODE></BLOCKQUOTE>
describes terminal and commutativeness of operator represented by
the terminal besides optional instruction for the terminal attribute
type. For example, if the terminal `plus' is described as commutative
then pattern `plus (register, constant)' simultaneously designates
pattern `plus (constant, register)'. There may be also the following
constructions in the declaration section
<BLOCKQUOTE><CODE>
<PRE>
%local {
C/C++ DECLARATIONS
}
%import {
C/C++ DECLARATION
}
and
%export {
C/C++ DECLARATION
}
</PRE>
</CODE></BLOCKQUOTE>
which contain any C/C++ declarations (types, variables, macros, and so
on) used in sections. The local C/C++ declarations are inserted at
the begin of generated implementation file (see code selector
description interface) but after include-directive of interface file.
C/C++ declarations which start with `%import' are inserted at the
begin of generated interface file. For example, such C/C++ code may
redefine some internal definitions, e.g. macro defining type of
attributes. C/C++ declarations which start with `%export' are
inserted at the end of generated interface file. For example, such
C/C++ code may contain definitions of of external variables and
functions which refer to definitions generated by NONA. All C/C++
declarations are placed in the same order as in the section of
declarations.</P>
<H2><A NAME="ss2.3">2.3</A> <A HREF="nona.html#toc2.3">Rules</A>
</H2>
<P>The section of declarations is followed by section of rules . A
rule is described the following construction
<BLOCKQUOTE><CODE>
<PRE>
nonterminal : pattern cost %if constraint action
</PRE>
</CODE></BLOCKQUOTE>
The rule connects tree pattern with nonterminal. Several tree
patterns can be connected to a nonterminal. Nonterminal is given by
its identifier. The rest constructions cost, constraint with keyword
`%if', and actions are optional. Cost is a integer expression on
C/C++ in brackets `[' and `]'. If the cost is omited in the rule,
then its value is believed to be zero. The cost value has to be
non-negative. Constraint which is given as a boolean expression on
C/C++ in brackets `[' and `]' defines a condition of the tree pattern
usage. In the case of absent constraint its value is believed to be
nonzero. The tree pattern will be never in a minimal cost cover if
constraint value is equal to zero during testing the tree pattern as a
candidate on inclusion into minimal cost cover. For example, the
following rule with constraint describes Am29k instruction CONST
<BLOCKQUOTE><CODE>
<PRE>
register : integer_constant [1]
%if [IR_value ($1) >=0 && IR_value ($1) < 256]
</PRE>
</CODE></BLOCKQUOTE>
The actions can contain any statements on C/C++ in figure brackets `{'
and `}'. Constructions `$$' and `$n' (n is a integer number here)
denote attributes of correspondingly nonterminal before `:' and
terminal or nonterminal in the pattern with order number equal to `n'.
The order numbers start with 1. These constructions may be present in
the cost, the constraint and the action. But it should be remembered
that definition of the moment of the cost and the constraint
evaluation is quite difficult. Moreover there is not guaranty that
given cost and constraint will be evaluated. Therefore side effects
should be not in the cost and in the constraint, and usage attributes
of nonterminals should be not in the cost and in the constraint. The
cost and the constraint may be fulfilled on the first bottom up pass.
It is known only that the cost is fulfilled after evaluation of
constraint give nonzero result. The action of the tree pattern which
is a part of result minimal cost cover is fulfilled on the second
bottom up pass. Tree pattern is given by one of the following forms:
<BLOCKQUOTE><CODE>
<PRE>
TERMINAL ( PATTERN , ...)
TERMINAL
NONTERMINAL
</PRE>
</CODE></BLOCKQUOTE>
For example, the following pattern describes Am29050 instruction DMSM
<BLOCKQUOTE><CODE>
<PRE>
double_addition (twin, double_multiplication (twin,
accumulator0))
</PRE>
</CODE></BLOCKQUOTE>
It should be remembered that each terminal must have fixed arity in
all patterns. It means that usage of the following patterns in a code
selector description will be erroneous.
<BLOCKQUOTE><CODE>
<PRE>
integer_addition (register, register)
integer_addition (register)
</PRE>
</CODE></BLOCKQUOTE>
Full YACC syntax of internal representation description language is
placed in Appendix 1.</P>
<HR>
<A HREF="nona-3.html">Next</A>
<A HREF="nona-1.html">Previous</A>
<A HREF="nona.html#toc2">Contents</A>
</BODY>
</HTML>