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

# SCM Repository

[smlnj] Diff of /sml/trunk/compiler/ElabData/prim/primop.sig
 [smlnj] / sml / trunk / compiler / ElabData / prim / primop.sig

# Diff of /sml/trunk/compiler/ElabData/prim/primop.sig

sml/trunk/compiler/FLINT/kernel/primop.sig revision 2162, Thu Nov 2 21:20:47 2006 UTC sml/trunk/compiler/ElabData/prim/primop.sig revision 5026, Thu May 2 11:44:23 2019 UTC
# Line 1  Line 1
1  (* Copyright 1996 by AT&T Bell Laboratories *)  (* primop.sig
2  (* primop.sig *)   *
3     * COPYRIGHT (c) 2017 The Fellowship of SML/NJ (http://www.smlnj.org)
5                     Integer/Word Conversions Explained   *)

All integer/word conversion operations are expressed using five
primitive conversion operators. Algebraic equations over these
operators are easy to define and can be used to simplify composition
of conversion operations.

The five basic conversion operators are (in all cases, we assume
that (n >= m):

TEST(n,m)     -- map an n-bit, 2's complement signed value to an
m-bit, 2's complement signed value;
raise Overflow if the value is too large.

TESTU(n,m)    -- map an unsigned n-bit value to an m-bit 2's
complement value; raise Overflow if the value
is too large.

EXTEND(m,n)   -- sign extend an m-bit value to a n-bit value

TRUNC(n,m)    -- truncate an n-bit value to an m-bit value.

COPY(m,n)     -- copy an m-bit value to an n-bit value.

TEST, TESTU, and TRUNC are used to go from large values to small
ones, and EXTEND and COPY are used to go from small values to
large. The operators EXTEND, TRUNC, and COPY are "pure," while TEST
and TESTU may raise Overflow.

Conversions where the sizes are the same can be simplified to copies:

TEST(n,n)     == COPY(n,n)
EXTEND(n,n)   == COPY(n,n)    Note: this does not apply to TESTU
TRUNC(n,n)    == COPY(n,n)

The translation of conversion operations in the Word32 and Word8
structures (for example) is given by:

Module        function     => Implemented by
----------------------------------------------------------
Word32        toLargeInt    => TESTU(32,32)
toLargeIntX   => EXTEND(32,32)          = COPY(32,32)
fromLargeInt  => COPY(32,32)
toInt         => TESTU(32,31)
toIntX        => TEST(32,31)
fromInt       => EXTEND(31,32)
toLargeWord   => COPY(32,32)
toLargeWordX  => EXTEND(32,32)          = COPY(32,32)
fromLargeWord => TRUNC(32,32)           = COPY(32,32)

Word8         toLargeInt    => COPY(8,32)
toLargeIntX   => EXTEND(8,32)
fromLargeInt  => TRUNC(32,8)
toInt         => COPY(8,31)
toIntX        => EXTEND(8,31)
fromInt       => TRUNC(31,8)
toLargeWord   => COPY(8,32)
toLargeWordX  => EXTEND(8,32)
fromLargeWord => TRUNC(32,8)

Each operator composed with itself is itself, but with different parameters:

TEST(n,m) o TEST(p,n)         == TEST(p,m)
TESTU(n,m) o TESTU(p,n)       == TESTU(p,m)
EXTEND(n,m) o EXTEND(p,n)     == EXTEND(p,m)
TRUNC(n,m) o TRUNC(p,n)       == TRUNC(p,m)
COPY(n,m) o COPY(p,n)         == COPY(p,m)

The composition of these operators can be described by a simple algebra.

EXTEND(n,m) o COPY(p,n)       == COPY(p,m)   if (n > p)
== EXTEND(p,m) if (n = p)
COPY(n,m) o EXTEND(p,n)       == EXTEND(p,m) if (n = m)

TRUNC(n,m) o COPY(p,n)        == COPY(p,m)   if (m >= p)
== TRUNC(p,m)  if (m < p)

COPY(n,m) o TRUNC(p,n)        == TRUNC(p,m)  if (n = m)

TEST(n,m) o COPY(p,n)         == COPY(p,m)   if (m >= p)
== TEST(p,m)   if (m < p)

TESTU(n,m) o COPY(p,n)        == COPY(p,m)   if (m >= p)
== TESTU(p,m)  if (m < p)

COPY(n,m) o TEST(p,n)         == TEST(p,m)   if (n = m)

COPY(n,m) o TESTU(p,n)        == TESTU(p,m)  if (n = m)

TRUNC(n,m) o EXTEND(p,n)      == EXTEND(p,m) if (m >= p)
== TRUNC(p,m)  if (m < p)

TEST(n,m) o EXTEND(p,n)       == EXTEND(p,m) if (m >= p)
== TEST(p,m)   if (m < p)

TESTU(n,m) o EXTEND(p,n)      == EXTEND(p,m) if (m >= p)
== TESTU(p,m)  if (m < p)

For example, consider:
Word.toInt o Word.fromLargeWord o Word8.toLargeWord

This translates to:
TESTU(31,31) o TRUNC(32,31) o COPY(8,32)

and simplifies to:
TESTU(31,31) o COPY(8,31)

This further simplifies to:
COPY(8, 31)

Since both 8-bit and 31-bit quantities are tagged the same way, this
gets translated to a MOVE. With a smart register allocator that MOVE
can be eliminated.
*********************************************************************)
6
7  signature PRIM_OP =  signature PRIMOP =
8  sig  sig
9
10  (* numkind includes kind and number of bits *)  (* numkind includes kind and number of bits *)
# Line 126  Line 12
12    = INT of int    = INT of int
13    | UINT of int    | UINT of int
14    | FLOAT of int    | FLOAT of int
15    (* QUESTION: what about IntInf.int? *)
16
17      (* arithmetic operations that may overflow; for the division operators,
18       * we assume that the second argument is never zero (i.e., an explicit
19       * test for zero is done before the operation).
20       *)
21  datatype arithop  datatype arithop
22    = + | - | * | / | ~                           (* int or float *)        = IADD | ISUB | IMUL | IDIV | IMOD | IQUOT | IREM | INEG
23    | ABS | FSQRT | FSIN | FCOS | FTAN            (* floating point only *)
24    | LSHIFT | RSHIFT | RSHIFTL                   (* int only *)    (* arithmetic operations that do not overflow; for the division operators,
25    | ANDB | ORB | XORB | NOTB                    (* int only *)     * we assume that the second argument is never zero (i.e., an explicit
26    | REM | DIV | MOD                             (* int only *)     * test for zero is done before the operation).
27       *)
28  datatype cmpop = > | >= | < | <= | LEU | LTU | GEU | GTU | EQL | NEQ      datatype pureop
29          = ADD | SUB | MUL | QUOT | REM | NEG
30  (*        | LSHIFT | RSHIFT | RSHIFTL
31   * Various primitive operations.  Those that are designated "inline" are        | ORB | XORB | ANDB | NOTB
32   * expanded into lambda code in terms of other operators,        | FDIV | FABS | FSQRT | FSIN | FCOS | FTAN
33   * as is the "checked=true" version of NUMSUBSCRIPT or NUMUPDATE.
34   * NUMSUBSCRIPT and NUMUPDATE are for arrays of floats or integers    (* comparison operators *)
35   * stored WITHOUT boxing or tags.      datatype cmpop
36          = GT | GTE | LT | LTE | EQL | NEQ
37
38      (* datatype primop:
39       * Various primitive operations. Those that are designated "inline" (L:) in
40       * the comments are expanded into lambda code in terms of other operators.
41       * "Environmental" primops (occurring in the Inline structure) are indicated
42       * by "E:" in the comment.
43       *
44       * See dev-notes/conversions.md for an explanation of the conversion operators.
45   *)   *)
46  datatype primop  datatype primop
47    = ARITH of {oper: arithop, overflow: bool, kind: numkind}        = IARITH of {                             (* E: integer arithmetic ops *)
48    | INLLSHIFT of numkind              oper : arithop, sz : int            (* kind = INT sz *)
49    | INLRSHIFT of numkind            }
50    | INLRSHIFTL of numkind        | PURE_ARITH of {                         (* E: arithmetic ops *)
51    | CMP of {oper: cmpop, kind: numkind}              oper : pureop, kind : numkind
52              }
53    | TESTU of int * int        | INLDIV of numkind                       (* E: integer div *)
54    | TEST of int * int        | INLMOD of numkind                       (* E: integer mod *)
55    | TRUNC of int * int        | INLQUOT of numkind                      (* E: integer/word quot *)
56    | EXTEND of int * int        | INLREM of numkind                       (* E: integer/word rem *)
57    | COPY of int * int        | INLLSHIFT of numkind                    (* E: left shift *)
58          | INLRSHIFT of numkind                    (* E: right shift *)
59    | TEST_INF of int                     (* inf -> i *)        | INLRSHIFTL of numkind                   (* E: right shift logical *)
60    | TRUNC_INF of int                    (* inf -> i *)        | CMP of {oper: cmpop, kind: numkind}     (* E: generic compare *)
61    | EXTEND_INF of int                   (* i -> inf *)        | FSGN of int                             (* E: floating point sign test *)
62    | COPY_INF of int                     (* i -> inf *)        | INLCHR                                  (* E: inline int to char conversion *)
63          | TESTU of int * int                      (* E: conversions to int, e.g. testu_31_31 *)
64    | ROUND of {floor: bool, fromkind: numkind, tokind: numkind}        | TEST of int * int                       (* E: conversions to int, e.g. test_32_31_w *)
65    | REAL of {fromkind: numkind, tokind: numkind}        | TRUNC of int * int                      (* E: truncations to smaller int/word, e.g. trunc_32_31_i *)
66          | EXTEND of int * int                     (* E: extensions to int32, word32 *)
67    | NUMSUBSCRIPT of {kind: numkind, checked: bool, immutable: bool}        | COPY of int * int                       (* E: conversions, e.g. copy_32_32_ii *)
68    | NUMUPDATE of {kind: numkind, checked: bool}        | TEST_INF of int                         (* E: intinf conversions, e.g. test_inf_31 *)
69          | TRUNC_INF of int                        (* E: intinf truncations, e.g. trunc_inf_31 *)
70    | SUBSCRIPT                  (* polymorphic array subscript *)        | EXTEND_INF of int                       (* E: intinf extensions, e.g. extend_8_inf *)
71    | SUBSCRIPTV                 (* poly vector subscript *)        | COPY_INF of int                         (* E: conversions to intinf, e.g. copy_8_inf *)
72    | INLSUBSCRIPT               (* inline poly array subscript *)        | REAL_TO_INT of {                        (* E: floor, round *)
73    | INLSUBSCRIPTV              (* inline poly vector subscript *)              floor: bool, from: int, to: int
74    | INLMKARRAY                 (* inline poly array creation *)            }
75          | INT_TO_REAL of {                        (* E: real, real32 *)
76    | PTREQL | PTRNEQ            (* pointer equality *)              from: int, to: int
77    | POLYEQL | POLYNEQ          (* polymorphic equality *)            }
78    | BOXED | UNBOXED            (* boxity tests *)        | NUMSUBSCRIPT of numkind                 (* E: unchecked numeric array subscript *)
79    | LENGTH                     (* vector, string, array, ... length *)        | NUMSUBSCRIPTV of numkind                (* E: unchecked numeric vector subscript *)
80    | OBJLENGTH                  (* length of arbitrary heap object *)        | NUMUPDATE of numkind                    (* E: unchecked numeric array update *)
81    | CAST        | INLNUMSUBSCRIPT of numkind              (* E: L: checked numeric array subscript *)
82    | WCAST        | INLNUMSUBSCRIPTV of numkind             (* E: L: checked numeric vector subscript *)
83    | GETRUNVEC                  (* get the pointer to the run-vector *)        | INLNUMUPDATE of numkind                 (* E: L: checked numeric array update *)
84    | MARKEXN                    (* mark an exception value with a string *)        | SUBSCRIPT                               (* E: polymorphic array subscript *)
85    | GETHDLR | SETHDLR          (* get/set exn handler pointer *)        | SUBSCRIPTV                              (* E: poly vector subscript *)
86    | GETVAR | SETVAR            (* get/set var register *)        | INLSUBSCRIPT                            (* E: L: poly array subscript *)
87    | GETPSEUDO | SETPSEUDO      (* get/set pseudo registers *)        | INLSUBSCRIPTV                           (* E: L: poly vector subscript *)
88    | SETMARK | DISPOSE          (* capture/dispose frames *)        | INLMKARRAY                              (* E: L: poly array creation *)
89    | MAKEREF                    (* allocate a ref cell *)        | PTREQL | PTRNEQ                         (* E: pointer equality *)
90    | CALLCC | CAPTURE | THROW   (* continuation operations *)        | POLYEQL | POLYNEQ                       (* E: polymorphic equality *)
91    | ISOLATE                    (* isolating a function *)        | BOXED | UNBOXED                         (* E: boxity tests *)
92    | DEREF                      (* dereferencing *)        | LENGTH                                  (* E: vector, string, array, ... length *)
93    | ASSIGN                     (* assignment *)        | OBJLENGTH                               (* E: length of arbitrary heap object *)
94    | UNBOXEDASSIGN              (* assignment to integer reference *)        | CAST                                    (* E: cast *)
95    | UPDATE                     (* array update (maybe boxed) *)        | GETHDLR | SETHDLR                       (* E: get/set exn handler pointer *)
96    | INLUPDATE                  (* inline array update (maybe boxed) *)        | GETVAR | SETVAR                         (* E: get/set var register *)
97    | BOXEDUPDATE                (* boxed array update *)        | MAKEREF                                 (* E: allocate a ref cell *)
98    | UNBOXEDUPDATE              (* update array of integers WITH tags *)        | CALLCC | CAPTURE | THROW                (* E: continuation operations *)
99          | ISOLATE                                 (* E: isolating a function *)
100    | GETTAG                     (* extract the tag portion of an *)        | DEREF                                   (* E: dereferencing *)
101                                 (* object's descriptor as an ML int *)        | ASSIGN                                  (* E: assignment *)
102    | MKSPECIAL                  (* make a special object *)        | UPDATE                                  (* E: array or reference update (maybe boxed) *)
103    | SETSPECIAL                 (* set the state of a special object *)        | INLUPDATE                               (* E: L: array update (maybe boxed) *)
104    | GETSPECIAL                 (* get the state of a special object *)        | UNBOXEDUPDATE                           (* E: update array of integers WITH tags
105    | USELVAR | DEFLVAR                                                   * removed by Zhong, put back by Matthias
106    | INLMIN of numkind          (* inline min *)                                                   * (see FLINT/trans/primopmap.sml) *)
107    | INLMAX of numkind          (* inline max *)        | GETTAG                                  (* E: extract the tag portion of an
108    | INLABS of numkind          (* inline abs *)                                                   * object's descriptor as an ML int *)
109    | INLNOT                     (* inline bool not operator *)        | MKSPECIAL                               (* E: make a special object *)
110    | INLCOMPOSE                 (* inline compose "op o"  operator *)        | SETSPECIAL                              (* E: set the state of a special object *)
111    | INLBEFORE                  (* inline "before" operator *)        | GETSPECIAL                              (* E: get the state of a special object *)
112    | INLIGNORE                  (* inline "ignore" function *)        | INLMIN of numkind                       (* E: L: min *)
113    | INL_ARRAY                  (* inline polymorphic array allocation *)        | INLMAX of numkind                       (* E: L: max *)
114    | INL_VECTOR                 (* inline polymorphic vector allocation *)        | INLABS of numkind                       (* E: L: abs *)
115    | INL_MONOARRAY of numkind   (* inline monomorphic array allocation *)        | INLNOT                                  (* E: L: bool not operator *)
116    | INL_MONOVECTOR of numkind  (* inline monomorphic vector allocation *)        | INLCOMPOSE                              (* E: L: compose "op o"  operator *)
117          | INLBEFORE                               (* E: L: "before" operator *)
118    | MKETAG                     (* make a new exception tag *)        | INLIGNORE                               (* E: L: "ignore" function *)
119    | WRAP                       (* box a value by wrapping it *)      (* primops to support new array representations *)
120    | UNWRAP                     (* unbox a value by unwrapping it *)        | NEW_ARRAY0                              (* E: allocate zero-length array header *)
121  (* Primops to support new array representations *)        | GET_SEQ_DATA                            (* E: get data pointer from arr/vec header *)
122    | NEW_ARRAY0                  (* allocate zero-length array header *)        | SUBSCRIPT_REC                           (* E: record subscript operation *)
123    | GET_SEQ_DATA                (* get data pointer from arr/vec header *)        | SUBSCRIPT_RAW64                         (* E: raw64 subscript operation *)
124    | SUBSCRIPT_REC               (* record subscript operation *)        | INLIDENTITY                             (* E: polymorphic identity *)
125    | SUBSCRIPT_RAW64             (* raw64 subscript operation *)        | CVT64                                   (* E: convert between external and
126  (* Primops to support new experimental C FFI. *)                                                   * internal representation of compiler
127    | RAW_LOAD of numkind         (* load from arbitrary memory location *)                                                   * simulated 64-bit scalars, e.g. w64p *)
128    | RAW_STORE of numkind        (* store to arbitrary memory location *)      (* Primops to support C FFI. *)
129      (* make a call to a C-function;        | RAW_LOAD of numkind                     (* E: load from arbitrary memory location *)
130          | RAW_STORE of numkind                    (* E: store to arbitrary memory location *)
131        (* E: make a call to a C-function;
132       * The primop carries C function prototype information and specifies       * The primop carries C function prototype information and specifies
133       * which of its (ML-) arguments are floating point. C prototype       * which of its (ML-) arguments are floating point. C prototype
134       * information is for use by the backend, ML information is for       * information is for use by the backend, ML information is for
135       * use by the CPS converter. *)       * use by the CPS converter. *)
136    | RAW_CCALL of { c_proto: CTypes.c_proto,        | RAW_CCALL of {
137                c_proto: PrimCTypes.c_proto,
138                     ml_args: ccall_type list,                     ml_args: ccall_type list,
139                     ml_res_opt: ccall_type option,                     ml_res_opt: ccall_type option,
140                     reentrant : bool                     reentrant : bool
# Line 239  Line 142
142     (* Allocate uninitialized storage on the heap.     (* Allocate uninitialized storage on the heap.
143      * The record is meant to hold short-lived C objects, i.e., they      * The record is meant to hold short-lived C objects, i.e., they
144      * are not ML pointers.  The representation is      * are not ML pointers.  The representation is
145      * the same as RECORD with tag tag_raw32 (fblock = false),      * the same as RECORD with tag tag_raw or tag_raw64.
* or tag_fblock (fblock = true).
146      *)      *)
147    | RAW_RECORD of { fblock: bool }        | RAW_RECORD of { align64 : bool }  (* E: *)
148
149    | INLIDENTITY                         (* polymorphic identity *)      (* non-environmental primops (not found in Inline) *)
150          | UNBOXEDASSIGN                   (* assignment to integer reference *)
151
152          | WCAST                           (* ? *)
153          | MARKEXN                         (* mark an exception value with a string *)
154
155    | CVT64                               (* convert between external and        | INL_ARRAY                       (* L: polymorphic array allocation *)
156                                           * internal representation of        | INL_VECTOR                      (* L: polymorphic vector allocation *)
157                                           * simulated 64-bit scalars *)        | INL_MONOARRAY of numkind        (* L: monomorphic array allocation *)
158          | INL_MONOVECTOR of numkind       (* L: monomorphic vector allocation *)
159
160          | MKETAG                          (* make a new exception tag *)
161          | WRAP                            (* box a value by wrapping it *)
162          | UNWRAP                          (* unbox a value by unwrapping it *)
163
164  and ccall_type =  and ccall_type =
165      CCI32 |                             (* passed as int32 *)      CCI32 |                             (* passed as int32 *)
# Line 256  Line 167
167      CCR64 |                             (* passed as real64 *)      CCR64 |                             (* passed as real64 *)
168      CCML                                (* passed as Unsafe.Object.object *)      CCML                                (* passed as Unsafe.Object.object *)
169
val ISUB : primop  (* default integer subtraction *)
val IMUL : primop
val IDIV : primop
val INEG : primop

val FEQLd : primop
val IEQL : primop
val INEQ : primop
val IGT : primop
val ILT : primop
val ILE : primop
val IGE : primop

val prNumkind : numkind -> string
val prPrimop: primop -> string
val mayRaise : primop -> bool
(* This should return more than just a boolean.
* True means "can not be dead-code eliminated" *)
val effect : primop -> bool

170  end (* signature PRIM_OP *)  end (* signature PRIM_OP *)

Legend:
 Removed from v.2162 changed lines Added in v.5026