Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/compiler/ElabData/prim/primop.sig
ViewVC logotype

Annotation of /sml/trunk/compiler/ElabData/prim/primop.sig

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4886 - (view) (download) (as text)

1 : jhr 4431 (* primop.sig
2 :     *
3 :     * COPYRIGHT (c) 2017 The Fellowship of SML/NJ (http://www.smlnj.org)
4 :     * All rights reserved.
5 :     *)
6 : monnier 16
7 :     (*********************************************************************
8 :     Integer/Word Conversions Explained
9 :    
10 :     All integer/word conversion operations are expressed using five
11 :     primitive conversion operators. Algebraic equations over these
12 :     operators are easy to define and can be used to simplify composition
13 :     of conversion operations.
14 :    
15 :     The five basic conversion operators are (in all cases, we assume
16 :     that (n >= m):
17 :    
18 : jhr 4804 TEST(n,m) -- map an n-bit, 2's complement signed value to an
19 :     m-bit, 2's complement signed value;
20 : monnier 16 raise Overflow if the value is too large.
21 :    
22 : jhr 4804 TESTU(n,m) -- map an unsigned n-bit value to an m-bit 2's
23 :     complement value; raise Overflow if the value
24 : monnier 16 is too large.
25 :    
26 :     EXTEND(m,n) -- sign extend an m-bit value to a n-bit value
27 :    
28 :     TRUNC(n,m) -- truncate an n-bit value to an m-bit value.
29 :    
30 :     COPY(m,n) -- copy an m-bit value to an n-bit value.
31 :    
32 :     TEST, TESTU, and TRUNC are used to go from large values to small
33 :     ones, and EXTEND and COPY are used to go from small values to
34 :     large. The operators EXTEND, TRUNC, and COPY are "pure," while TEST
35 : jhr 4804 and TESTU may raise Overflow.
36 : monnier 16
37 :     Conversions where the sizes are the same can be simplified to copies:
38 :    
39 :     TEST(n,n) == COPY(n,n)
40 :     EXTEND(n,n) == COPY(n,n) Note: this does not apply to TESTU
41 :     TRUNC(n,n) == COPY(n,n)
42 :    
43 :     The translation of conversion operations in the Word32 and Word8
44 :     structures (for example) is given by:
45 :    
46 : jhr 4804 Module function => Implemented by
47 : monnier 16 ----------------------------------------------------------
48 : jhr 4804 Word32 toLargeInt => TESTU(32,32)
49 : monnier 16 toLargeIntX => EXTEND(32,32) = COPY(32,32)
50 : jhr 4804 fromLargeInt => COPY(32,32)
51 :     toInt => TESTU(32,31)
52 :     toIntX => TEST(32,31)
53 :     fromInt => EXTEND(31,32)
54 :     toLargeWord => COPY(32,32)
55 : monnier 16 toLargeWordX => EXTEND(32,32) = COPY(32,32)
56 :     fromLargeWord => TRUNC(32,32) = COPY(32,32)
57 :    
58 : jhr 4804 Word8 toLargeInt => COPY(8,32)
59 :     toLargeIntX => EXTEND(8,32)
60 :     fromLargeInt => TRUNC(32,8)
61 :     toInt => COPY(8,31)
62 :     toIntX => EXTEND(8,31)
63 :     fromInt => TRUNC(31,8)
64 :     toLargeWord => COPY(8,32)
65 :     toLargeWordX => EXTEND(8,32)
66 :     fromLargeWord => TRUNC(32,8)
67 : monnier 16
68 :    
69 :     Each operator composed with itself is itself, but with different parameters:
70 :    
71 : jhr 4804 TEST(n,m) o TEST(p,n) == TEST(p,m)
72 :     TESTU(n,m) o TESTU(p,n) == TESTU(p,m)
73 :     EXTEND(n,m) o EXTEND(p,n) == EXTEND(p,m)
74 :     TRUNC(n,m) o TRUNC(p,n) == TRUNC(p,m)
75 :     COPY(n,m) o COPY(p,n) == COPY(p,m)
76 : monnier 16
77 :     The composition of these operators can be described by a simple algebra.
78 :    
79 : jhr 4804 EXTEND(n,m) o COPY(p,n) == COPY(p,m) if (n > p)
80 :     == EXTEND(p,m) if (n = p)
81 :     COPY(n,m) o EXTEND(p,n) == EXTEND(p,m) if (n = m)
82 : monnier 16
83 : jhr 4804 TRUNC(n,m) o COPY(p,n) == COPY(p,m) if (m >= p)
84 :     == TRUNC(p,m) if (m < p)
85 : monnier 16
86 : jhr 4804 COPY(n,m) o TRUNC(p,n) == TRUNC(p,m) if (n = m)
87 : monnier 16
88 : jhr 4804 TEST(n,m) o COPY(p,n) == COPY(p,m) if (m >= p)
89 :     == TEST(p,m) if (m < p)
90 : monnier 16
91 : jhr 4804 TESTU(n,m) o COPY(p,n) == COPY(p,m) if (m >= p)
92 :     == TESTU(p,m) if (m < p)
93 : monnier 16
94 : jhr 4804 COPY(n,m) o TEST(p,n) == TEST(p,m) if (n = m)
95 : monnier 16
96 : jhr 4804 COPY(n,m) o TESTU(p,n) == TESTU(p,m) if (n = m)
97 : monnier 16
98 : jhr 4804 TRUNC(n,m) o EXTEND(p,n) == EXTEND(p,m) if (m >= p)
99 :     == TRUNC(p,m) if (m < p)
100 : monnier 16
101 : jhr 4804 TEST(n,m) o EXTEND(p,n) == EXTEND(p,m) if (m >= p)
102 :     == TEST(p,m) if (m < p)
103 : monnier 16
104 : jhr 4804 TESTU(n,m) o EXTEND(p,n) == EXTEND(p,m) if (m >= p)
105 :     == TESTU(p,m) if (m < p)
106 :    
107 : monnier 16 For example, consider:
108 :     Word.toInt o Word.fromLargeWord o Word8.toLargeWord
109 :    
110 :     This translates to:
111 :     TESTU(31,31) o TRUNC(32,31) o COPY(8,32)
112 :    
113 :     and simplifies to:
114 :     TESTU(31,31) o COPY(8,31)
115 :    
116 :     This further simplifies to:
117 :     COPY(8, 31)
118 :    
119 :     Since both 8-bit and 31-bit quantities are tagged the same way, this
120 :     gets translated to a MOVE. With a smart register allocator that MOVE
121 :     can be eliminated.
122 :     *********************************************************************)
123 :    
124 : jhr 4804 signature PRIMOP =
125 : jhr 4431 sig
126 : monnier 16
127 : jhr 4431 (* numkind includes kind and number of bits *)
128 : jhr 4804 datatype numkind
129 :     = INT of int
130 :     | UINT of int
131 : jhr 4431 | FLOAT of int
132 :     (* QUESTION: what about IntInf.int? *)
133 : jhr 4804
134 : jhr 4431 datatype arithop
135 : jhr 4432 = ADD | SUB | MUL | NEG (* int or float *)
136 :     | FDIV | ABS | FSQRT | FSIN | FCOS | FTAN (* floating point only *)
137 : jhr 4431 | LSHIFT | RSHIFT | RSHIFTL (* int only *)
138 :     | ANDB | ORB | XORB | NOTB (* int only *)
139 : jhr 4432 | DIV | MOD | QUOT | REM (* int only *)
140 : monnier 16
141 : jhr 4431 datatype cmpop
142 :     = GT | GTE | LT | LTE (* signed comparisons *)
143 :     | LEU | LTU | GEU | GTU (* unsigned comparisons *)
144 :     | EQL | NEQ (* equality *)
145 :     | FSGN (* floating point only *)
146 : monnier 16
147 : jhr 4431 (* datatype primop:
148 :     * Various primitive operations. Those that are designated "inline" (L:) in
149 :     * the comments are expanded into lambda code in terms of other operators,
150 :     * as are the "checked=true" versions of NUMSUBSCRIPT and NUMUPDATE (L?:).
151 :     * "Environmental" primops (occurring in the InLine structure) are indicated
152 :     * by "E:" in the comment.
153 :     *)
154 :     datatype primop
155 :     = ARITH of { (* E: arithmetic ops *)
156 :     oper: arithop, overflow: bool, kind: numkind
157 :     }
158 :     | INLLSHIFT of numkind (* E: left shift *)
159 :     | INLRSHIFT of numkind (* E: right shift *)
160 :     | INLRSHIFTL of numkind (* E: right shift logical *)
161 :     | CMP of {oper: cmpop, kind: numkind} (* E: generic compare *)
162 :     | TESTU of int * int (* E: conversions to int, e.g. testu_31_31 *)
163 :     | TEST of int * int (* E: conversions to int, e.g. test_32_31_w *)
164 :     | TRUNC of int * int (* E: truncations to smaller int/word, e.g. trunc_32_31_i *)
165 :     | EXTEND of int * int (* E: extensions to int32, word32 *)
166 :     | COPY of int * int (* E: conversions, e.g. copy_32_32_ii *)
167 :     | TEST_INF of int (* E: intinf conversions, e.g. test_inf_31 *)
168 :     | TRUNC_INF of int (* E: intinf truncations, e.g. trunc_inf_31 *)
169 :     | EXTEND_INF of int (* E: intinf extensions, e.g. extend_8_inf *)
170 :     | COPY_INF of int (* E: conversions to intinf, e.g. copy_8_inf *)
171 :     | ROUND of { (* E: floor, round *)
172 :     floor: bool, fromkind: numkind, tokind: numkind
173 :     }
174 :     | REAL of { (* E: real, real32 *)
175 :     fromkind: numkind, tokind: numkind
176 :     }
177 :     | NUMSUBSCRIPT of { (* E: L?: ordof, etc. *)
178 :     kind: numkind, checked: bool, immutable: bool
179 :     }
180 :     | NUMUPDATE of { (* E: L?: store, etc. *)
181 :     kind: numkind, checked: bool
182 : jhr 4804 }
183 : jhr 4431 | SUBSCRIPT (* E: polymorphic array subscript *)
184 :     | SUBSCRIPTV (* E: poly vector subscript *)
185 :     | INLSUBSCRIPT (* E: L: poly array subscript *)
186 :     | INLSUBSCRIPTV (* E: L: poly vector subscript *)
187 :     | INLMKARRAY (* E: L: poly array creation *)
188 :     | PTREQL | PTRNEQ (* E: pointer equality *)
189 :     | POLYEQL | POLYNEQ (* E: polymorphic equality *)
190 :     | BOXED | UNBOXED (* E: boxity tests *)
191 :     | LENGTH (* E: vector, string, array, ... length *)
192 :     | OBJLENGTH (* E: length of arbitrary heap object *)
193 :     | CAST (* E: cast *)
194 :     | GETHDLR | SETHDLR (* E: get/set exn handler pointer *)
195 :     | GETVAR | SETVAR (* E: get/set var register *)
196 :     | MAKEREF (* E: allocate a ref cell *)
197 :     | CALLCC | CAPTURE | THROW (* E: continuation operations *)
198 :     | ISOLATE (* E: isolating a function *)
199 :     | DEREF (* E: dereferencing *)
200 :     | ASSIGN (* E: assignment *)
201 :     | UPDATE (* E: array or reference update (maybe boxed) *)
202 :     | INLUPDATE (* E: L: array update (maybe boxed) *)
203 :     | UNBOXEDUPDATE (* E: update array of integers WITH tags
204 :     * removed by Zhong, put back by Matthias
205 :     * (see FLINT/trans/primopmap.sml) *)
206 :     | GETTAG (* E: extract the tag portion of an
207 :     * object's descriptor as an ML int *)
208 :     | MKSPECIAL (* E: make a special object *)
209 :     | SETSPECIAL (* E: set the state of a special object *)
210 :     | GETSPECIAL (* E: get the state of a special object *)
211 :     | INLMIN of numkind (* E: L: min *)
212 :     | INLMAX of numkind (* E: L: max *)
213 :     | INLABS of numkind (* E: L: abs *)
214 :     | INLNOT (* E: L: bool not operator *)
215 :     | INLCOMPOSE (* E: L: compose "op o" operator *)
216 : jhr 4804 | INLBEFORE (* E: L: "before" operator *)
217 : jhr 4431 | INLIGNORE (* E: L: "ignore" function *)
218 :     (* primops to support new array representations *)
219 :     | NEW_ARRAY0 (* E: allocate zero-length array header *)
220 :     | GET_SEQ_DATA (* E: get data pointer from arr/vec header *)
221 :     | SUBSCRIPT_REC (* E: record subscript operation *)
222 :     | SUBSCRIPT_RAW64 (* E: raw64 subscript operation *)
223 :     | INLIDENTITY (* E: polymorphic identity *)
224 :     | CVT64 (* E: convert between external and
225 :     * internal representation of compiler
226 :     * simulated 64-bit scalars, e.g. w64p *)
227 :     (* Primops to support C FFI. *)
228 :     | RAW_LOAD of numkind (* E: load from arbitrary memory location *)
229 :     | RAW_STORE of numkind (* E: store to arbitrary memory location *)
230 :     (* E: make a call to a C-function;
231 : blume 773 * The primop carries C function prototype information and specifies
232 :     * which of its (ML-) arguments are floating point. C prototype
233 :     * information is for use by the backend, ML information is for
234 :     * use by the CPS converter. *)
235 : jhr 4431 | RAW_CCALL of {
236 : jhr 4432 c_proto: PrimCTypes.c_proto,
237 : jhr 4431 ml_args: ccall_type list,
238 :     ml_res_opt: ccall_type option,
239 :     reentrant: bool
240 :     } option
241 : leunga 1174 (* Allocate uninitialized storage on the heap.
242 :     * The record is meant to hold short-lived C objects, i.e., they
243 : jhr 4804 * are not ML pointers. The representation is
244 : dbm 4428 * the same as RECORD with tag tag_raw32 or tag_fblock.
245 : leunga 1174 *)
246 : jhr 4431 | RAW_RECORD of { fblock: bool } (* E: *)
247 : monnier 16
248 : jhr 4431 (* non-environmental primops (not found in InLine) *)
249 :     | UNBOXEDASSIGN (* assignment to integer reference *)
250 : mblume 1347
251 : jhr 4431 | WCAST (* ? *)
252 :     | MARKEXN (* mark an exception value with a string *)
253 : mblume 1683
254 : jhr 4431 | INL_ARRAY (* L: polymorphic array allocation *)
255 :     | INL_VECTOR (* L: polymorphic vector allocation *)
256 :     | INL_MONOARRAY of numkind (* L: monomorphic array allocation *)
257 :     | INL_MONOVECTOR of numkind (* L: monomorphic vector allocation *)
258 : dbm 4428
259 : jhr 4431 | MKETAG (* make a new exception tag *)
260 :     | WRAP (* box a value by wrapping it *)
261 :     | UNWRAP (* unbox a value by unwrapping it *)
262 : dbm 4428
263 : jhr 4431 and ccall_type =
264 :     CCI32 | (* passed as int32 *)
265 :     CCI64 | (* int64, currently unused *)
266 :     CCR64 | (* passed as real64 *)
267 :     CCML (* passed as Unsafe.Object.object *)
268 : dbm 4428
269 : jhr 4431 val IADD : primop (* default integer addition *)
270 :     val ISUB : primop (* default integer subtraction *)
271 :     val IMUL : primop
272 :     val IDIV : primop
273 :     val INEG : primop
274 : monnier 45
275 : jhr 4431 val FEQLd : primop
276 :     val IEQL : primop
277 :     val INEQ : primop
278 :     val IGT : primop
279 :     val ILT : primop
280 :     val ILE : primop
281 :     val IGE : primop
282 : dbm 4791 val UIEQL : primop (* for UINT kind, may not matter *)
283 : jhr 4804
284 : dbm 4791 val mkIEQL : int -> primop (* make equality primop for other sizes *)
285 :     val mkUIEQL : int -> primop (* and for unsigned (kind = UINT) *)
286 : monnier 16
287 : jhr 4431 val prNumkind : numkind -> string
288 :     val prPrimop: primop -> string
289 :     val mayRaise : primop -> bool
290 : monnier 16
291 : jhr 4431 (* This should return more than just a boolean.
292 :     * True means "can not be dead-code eliminated" *)
293 :     val effect : primop -> bool
294 : monnier 16
295 : jhr 4431 end (* signature PRIM_OP *)
296 : monnier 16

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0