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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 4886, Wed Oct 10 16:54:46 2018 UTC revision 5024, Wed May 1 17:17:19 2019 UTC
# Line 4  Line 4 
4   * All rights reserved.   * All rights reserved.
5   *)   *)
6    
 (*********************************************************************  
                    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.  
 *********************************************************************)  
   
7  signature PRIMOP =  signature PRIMOP =
8    sig    sig
9    
# Line 131  Line 14 
14        | FLOAT of int        | FLOAT of int
15  (* QUESTION: what about IntInf.int? *)  (* 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        = ADD | SUB | MUL | NEG                   (* int or float *)        = IADD | ISUB | IMUL | IDIV | IMOD | IQUOT | IREM | INEG
23        | FDIV | 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        | DIV | MOD | QUOT | REM                  (* int only *)     * test for zero is done before the operation).
27       *)
28        datatype pureop
29          = ADD | SUB | MUL | QUOT | REM | NEG
30          | LSHIFT | RSHIFT | RSHIFTL
31          | ORB | XORB | ANDB | NOTB
32          | FDIV | FABS | FSQRT | FSIN | FCOS | FTAN
33    
34      (* comparison operators *)
35      datatype cmpop      datatype cmpop
36        = GT | GTE | LT | LTE                     (* signed comparisons *)        = GT | GTE | LT | LTE | EQL | NEQ
       | LEU | LTU | GEU | GTU                   (* unsigned comparisons *)  
       | EQL | NEQ                               (* equality *)  
       | FSGN                                    (* floating point only *)  
37    
38    (* datatype primop:    (* datatype primop:
39     * Various primitive operations. Those that are designated "inline" (L:) in     * Various primitive operations. Those that are designated "inline" (L:) in
40     * the comments are expanded into lambda code in terms of other operators,     * the comments are expanded into lambda code in terms of other operators.
    * as are the "checked=true" versions of NUMSUBSCRIPT and NUMUPDATE (L?:).  
41     * "Environmental" primops (occurring in the InLine structure) are indicated     * "Environmental" primops (occurring in the InLine structure) are indicated
42     * by "E:" in the comment.     * 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 {                              (* E: arithmetic ops *)        = IARITH of {                             (* E: integer arithmetic ops *)
48              oper: arithop, overflow: bool, kind: numkind              oper : arithop, sz : int            (* kind = INT sz *)
49            }            }
50          | PURE_ARITH of {                         (* E: arithmetic ops *)
51                oper : pureop, kind : numkind
52              }
53          | INLDIV of numkind                       (* E: integer div *)
54          | INLMOD of numkind                       (* E: integer mod *)
55          | INLQUOT of numkind                      (* E: integer/word quot *)
56          | INLREM of numkind                       (* E: integer/word rem *)
57        | INLLSHIFT of numkind                    (* E: left shift *)        | INLLSHIFT of numkind                    (* E: left shift *)
58        | INLRSHIFT of numkind                    (* E: right shift *)        | INLRSHIFT of numkind                    (* E: right shift *)
59        | INLRSHIFTL of numkind                   (* E: right shift logical *)        | INLRSHIFTL of numkind                   (* E: right shift logical *)
60        | CMP of {oper: cmpop, kind: numkind}     (* E: generic compare *)        | CMP of {oper: cmpop, kind: numkind}     (* E: generic compare *)
61          | FSGN of int                             (* E: floating point sign test *)
62          | INLCHR                                  (* E: inline int to char conversion *)
63        | TESTU of int * int                      (* E: conversions to int, e.g. testu_31_31 *)        | TESTU of int * int                      (* E: conversions to int, e.g. testu_31_31 *)
64        | TEST of int * int                       (* E: conversions to int, e.g. test_32_31_w *)        | TEST of int * int                       (* E: conversions to int, e.g. test_32_31_w *)
65        | TRUNC of int * int                      (* E: truncations to smaller int/word, e.g. trunc_32_31_i *)        | TRUNC of int * int                      (* E: truncations to smaller int/word, e.g. trunc_32_31_i *)
# Line 168  Line 69 
69        | TRUNC_INF of int                        (* E: intinf truncations, e.g. trunc_inf_31 *)        | TRUNC_INF of int                        (* E: intinf truncations, e.g. trunc_inf_31 *)
70        | EXTEND_INF of int                       (* E: intinf extensions, e.g. extend_8_inf *)        | EXTEND_INF of int                       (* E: intinf extensions, e.g. extend_8_inf *)
71        | COPY_INF of int                         (* E: conversions to intinf, e.g. copy_8_inf *)        | COPY_INF of int                         (* E: conversions to intinf, e.g. copy_8_inf *)
72        | ROUND of {                              (* E: floor, round *)        | REAL_TO_INT of {                        (* E: floor, round *)
73              floor: bool, fromkind: numkind, tokind: numkind              floor: bool, from: int, to: int
           }  
       | REAL of {                               (* E: real, real32 *)  
             fromkind: numkind, tokind: numkind  
           }  
       | NUMSUBSCRIPT of {                       (* E: L?: ordof, etc. *)  
             kind: numkind, checked: bool, immutable: bool  
74            }            }
75        | NUMUPDATE of {                          (* E: L?: store, etc. *)        | INT_TO_REAL of {                        (* E: real, real32 *)
76              kind: numkind, checked: bool              from: int, to: int
77            }            }
78          | NUMSUBSCRIPT of numkind                 (* E: unchecked numeric array subscript *)
79          | NUMSUBSCRIPTV of numkind                (* E: unchecked numeric vector subscript *)
80          | NUMUPDATE of numkind                    (* E: unchecked numeric array update *)
81          | INLNUMSUBSCRIPT of numkind              (* E: L: checked numeric array subscript *)
82          | INLNUMSUBSCRIPTV of numkind             (* E: L: checked numeric vector subscript *)
83          | INLNUMUPDATE of numkind                 (* E: L: checked numeric array update *)
84        | SUBSCRIPT                               (* E: polymorphic array subscript *)        | SUBSCRIPT                               (* E: polymorphic array subscript *)
85        | SUBSCRIPTV                              (* E: poly vector subscript *)        | SUBSCRIPTV                              (* E: poly vector subscript *)
86        | INLSUBSCRIPT                            (* E: L: poly array subscript *)        | INLSUBSCRIPT                            (* E: L: poly array subscript *)
# Line 241  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 or tag_fblock.      * the same as RECORD with tag tag_raw or tag_raw64.
146      *)      *)
147        | RAW_RECORD of { fblock: bool }  (* E: *)        | RAW_RECORD of { align64 : bool }  (* E: *)
148    
149      (* non-environmental primops (not found in InLine) *)      (* non-environmental primops (not found in InLine) *)
150        | UNBOXEDASSIGN                   (* assignment to integer reference *)        | UNBOXEDASSIGN                   (* assignment to integer reference *)
# Line 266  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 IADD : primop  (* default integer addition *)  
     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 UIEQL : primop  (* for UINT kind, may not matter *)  
   
     val mkIEQL : int -> primop   (* make equality primop for other sizes *)  
     val mkUIEQL : int -> primop  (* and for unsigned (kind = UINT) *)  
   
     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.4886  
changed lines
  Added in v.5024

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