PreviousUpNext

15.3.209  src/lib/compiler/back/top/highcode/highcode-form.api

## highcode-form.api                            # "ltybasic.sig" in SML/NJ
#
# CONTEXT:
#
#     The Mythryl compiler code representations used are, in order:
#
#     1)  Raw Syntax is the initial frontend code representation.
#     2)  Deep Syntax is the second and final frontend code representation.
#     3)  Lambdacode (polymorphically typed lambda calculus) is the first backend code representation, used only transitionally.
#     4)  Anormcode (A-Normal form) is the second backend code representation, and the first used for optimization.
#     5)  Nextcode ("Continuation Passing Style") is the third and chief backend tophalf code representation.
#     6)  Treecode is the backend tophalf/lowhalf transitional code representation. It is typically slightly specialized for each target architecture, e.g. Intel32 (x86).
#     7)  Machcode abstracts the target architecture machine instructions. It gets specialized for each target architecture.
#     8)  Execode is absolute executable binary machine instructions for the target architecture.
#
# For higher-level context, read 
#
#     src/A.COMPILER.OVERVIEW
#
# For authoritative background see Zhong Shao's PhD thesis:
#
#     Compiling Standard ML for Efficient Execution on Modern Machines
#     http://flint.cs.yale.edu/flint/publications/zsh-thesis.html
#
# Here and in
#
#     src/lib/compiler/back/top/highcode/highcode-type.api
#
# we implement the client-code interface to the
# hash-consed intermediate-code form implemented in
#
#     src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg
#
# This file is part of the compiler backend
# tophalf's machine-independent optimizer,
# "highcode", derived from the Yale FLINT
# project:  http://flint.cs.yale.edu/
#
# In nextcode return addresses are made into explicit "fate"
# arguments to functions (hence the name).
#
# This has the disadvantage of losing the original
# explicit function-call hierarchy, but the advantage
# of exposing the return-address machinery for
# optimization and register allocation etc.
#
# The deep syntax trees produced by the front end
# are first translated by
#
#     src/lib/compiler/back/top/translate/translate-deep-syntax-to-lambdacode.pkg
#
# into A-Normal Form, where various optimziations are
# performed, for which see the comments in:
#
#     src/lib/compiler/back/top/anormcode/anormcode-form.api
#
# After that, code is translated from A-Normal Form to nextcode by:
#
#    src/lib/compiler/back/top/nextcode/translate-anormcode-to-nextcode-g.pkg
#
# Here we define a relatively abstract nextcode interface
# for use by nextcode client code.   The full internal implementation
# datastructure, and core code operating on it, are defined in
#
#     src/lib/compiler/back/top/highcode/highcode-uniq-types.api
#     src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg
#
# Also see
#
#     src/lib/compiler/back/top/nextcode/nextcode-form.api
#
# The selection and ordering of nextcode compiler passes is
# performed by
#
#     src/lib/compiler/back/top/main/backend-tophalf-g.pkg
#
# The nextcode code transformation passes are:
#
#     nextcode_preimprover_transform   src/lib/compiler/back/top/nextcode/nextcode-preimprover-transform-g.pkg
#     optional_nextcode_improvers      src/lib/compiler/back/top/improve-nextcode/run-optional-nextcode-improvers-g.pkg
#
#     split_off_nextcode_literals          src/lib/compiler/back/top/main/make-nextcode-literals-bytecode-vector.pkg
#     literal_expression_to_bytevector     "                                     "
#
#     make_nextcode_closures               src/lib/compiler/back/top/closures/make-nextcode-closures-g.pkg
#     nextcode_globalfix                   src/lib/compiler/back/top/closures/nextcode-globalfix.pkg
#     spill_nextcode_registers             src/lib/compiler/back/low/main/nextcode/spill-nextcode-registers-g.pkg
#     nextcode_inlining_g                  src/lib/compiler/back/top/closures/dummy-nextcode-inlining-g.pkg
#     heap limit checking                  src/lib/compiler/back/low/main/nextcode/pick-nextcode-fns-for-heaplimit-checks.pkg
#     ... (to be completed)
#
#
#  
# The above 'optional_nextcode_improvers' meta-pass applies
# the following nextcode optimization subpasses
#
#     eta reduction  src/lib/compiler/back/top/improve-nextcode/inline-nextcode-buckpass-calls.pkg
#                    src/lib/compiler/back/top/improve-nextcode/uncurry-nextcode-functions-g.pkg
#                    src/lib/compiler/back/top/improve-nextcode/split-nextcode-fns-into-known-vs-escaping-versions-g.pkg
#
#     unrolling      src/lib/compiler/back/top/improve-nextcode/run-optional-nextcode-improvers-g.pkg (fn 'cycle')
#                    src/lib/compiler/back/top/improve-nextcode/clean-nextcode-g.pkg
#                    src/lib/compiler/back/top/improve-nextcode/convert-monoarg-to-multiarg-nextcode-g.pkg
#                    src/lib/compiler/back/top/improve-nextcode/do-nextcode-inlining-g.pkg
#
#     printing       src/lib/compiler/back/top/nextcode/prettyprint-nextcode.pkg
    
# Compiled by:
#     src/lib/compiler/core.sublib





# This interface hides the implementation details of nextcode Highcode_Kind, hut::Uniqtyp, and 
# hut::Uniqtype defined inside highcode_uniq_types. For each entity, we provide a series of 
# constructor funtions, deconstructor functions, predicate functions,
# and other utility functions.
#
# The client interface to highcode functionality is defined in
#     src/lib/compiler/back/top/highcode/highcode-form.api
#     src/lib/compiler/back/top/highcode/highcode-form.pkg
# A types-only version is available in
#     src/lib/compiler/back/top/highcode/highcode-type.api
#     src/lib/compiler/back/top/highcode/highcode-type.pkg
#
# This interface should only refer to packages such as debruijn_index, highcode_uniq_types, 
# highcode_basetypes, Symbol, and lty_basic (indirectly highcode_type).




###                "Have you heard about the software developer's wife?
###                 She died a virgin, because all he did was sit on
###                 the bed telling her how good it was going to be."




###                        "Pure mathematics is, in its way,
###                         the poetry of logical ideas."
###
###                                       -- Albert Einstein


stipulate
    package acf =  anormcode_form;                                              # anormcode_form                is from   src/lib/compiler/back/top/anormcode/anormcode-form.pkg
    package di  =  debruijn_index;                                              # debruijn_index                is from   src/lib/compiler/front/typer/basics/debruijn-index.pkg
    package hbo =  highcode_baseops;                                            # highcode_baseops              is from   src/lib/compiler/back/top/highcode/highcode-baseops.pkg
    package tmp =  highcode_codetemp;                                           # highcode_codetemp             is from   src/lib/compiler/back/top/highcode/highcode-codetemp.pkg
    package hut =  highcode_uniq_types;                                         # highcode_uniq_types           is from   src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg
herein

    api Highcode_Form {
        #

        # We define hut::Uniqkind, hut::Uniqtyp,
        # and hut::Uniqtype elsewhere:
        #
        #     src/lib/compiler/back/top/highcode/highcode-type.api
        #     src/lib/compiler/back/top/highcode/highcode-type.pkg
        #
        # The idea is that those two files should change
        # very rarely while the rest of the interface for
        # highcode may change often. The client should
        # refer to highcode_type if using only types names
        # and to highcode otherwise.

        # The internal implementation of hut::Uniqkind,
        # hut::Uniqtyp, and hut::Uniqtype are in:
        #
        #     src/lib/compiler/back/top/highcode/highcode-uniq-types.api
        #     src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg
        #
        # Client code should not need to understand
        # what is going on inside highcode_uniq_types.


        # The definitions of hut::Uniqkind,
        # hut::Uniqtyp, and hut::Uniqtype:
        #
        include Highcode_Type;          # Highcode_Type         is from   src/lib/compiler/back/top/highcode/highcode-type.api

        # Functions for constructing Uniqkinds:
        #
        make_n_arg_typ_fun_uniqkind:     Int -> hut::Uniqkind;          # Kind for fn with n typelocked-type args.
        n_plaintype_uniqkinds:     Int -> List(hut::Uniqkind);          # Kind for list of n typelocked types.

        # Bases and utility functions for Calling_Convention:
        #
        rawraw_variable_calling_convention:      hut::Calling_Convention;
        update_calling_convention:              (hut::Calling_Convention,   { arg_is_raw: Bool, body_is_raw: Bool }) -> hut::Calling_Convention;
        unpack_calling_convention:               hut::Calling_Convention -> { arg_is_raw: Bool, body_is_raw: Bool };

        # Prebuilt basetype uniqtyps:
        #
              int_uniqtyp:              hut::Uniqtyp;
            int1_uniqtyp:               hut::Uniqtyp;
          float64_uniqtyp:              hut::Uniqtyp;
           string_uniqtyp:              hut::Uniqtyp;
        exception_uniqtyp:              hut::Uniqtyp;
         truevoid_uniqtyp:              hut::Uniqtyp;
             void_uniqtyp:              hut::Uniqtyp;
             bool_uniqtyp:              hut::Uniqtyp;

        make_typevar_i_uniqtyp: Int             -> hut::Uniqtyp;        # Make typevar with de Bruijn depth==di::innermost and index==i
        make_ref_uniqtyp:               hut::Uniqtyp    -> hut::Uniqtyp;
        make_rw_vector_uniqtyp: hut::Uniqtyp    -> hut::Uniqtyp;
        make_ro_vector_uniqtyp: hut::Uniqtyp    -> hut::Uniqtyp;
        make_exception_tag_uniqtyp:     hut::Uniqtyp    -> hut::Uniqtyp;

        # Prebuilt basetype uniqtypes:
        #
        int_uniqtype:                   hut::Uniqtype;
        int1_uniqtype:                  hut::Uniqtype;
        float64_uniqtype:               hut::Uniqtype;
        string_uniqtype:                hut::Uniqtype;
        exception_uniqtype:             hut::Uniqtype;
        truevoid_uniqtype:              hut::Uniqtype;
        void_uniqtype:                  hut::Uniqtype;
        bool_uniqtype:                  hut::Uniqtype;

        # Uniqtype constructors:
        #
        make_typevar_i_uniqtype:        Int             -> hut::Uniqtype;
        make_ref_uniqtype:              hut::Uniqtype   -> hut::Uniqtype;
        make_rw_vector_uniqtype:        hut::Uniqtype   -> hut::Uniqtype;
        make_ro_vector_uniqtype:        hut::Uniqtype   -> hut::Uniqtype;
        make_exception_tag_uniqtype:    hut::Uniqtype   -> hut::Uniqtype;

        # Testing equivalence of uniqkinds, uniqtyps, uniqtypes,
        # calling_conventions, and useless_recordflags:
        #
        same_uniqkind:                  (hut::Uniqkind,           hut::Uniqkind          ) -> Bool;
        same_uniqtyp:           (hut::Uniqtyp,    hut::Uniqtyp   ) -> Bool;
        same_uniqtype:                  (hut::Uniqtype,           hut::Uniqtype          ) -> Bool;
        same_callnotes:                 (hut::Calling_Convention, hut::Calling_Convention) -> Bool;
        same_recordflag:                (hut::Useless_Recordflag, hut::Useless_Recordflag) -> Bool;

        # Testing the equivalence for typs
        # and ltys with relaxed constraints:
        #
        similar_uniqtyps:               (hut::Uniqtyp,    hut::Uniqtyp   ) -> Bool;
        similar_uniqtypes:              (hut::Uniqtype,           hut::Uniqtype          ) -> Bool;

        # Prettyprinting of uniqkinds, uniqtyps, and uniqtypes:
        #
        uniqkind_to_string:             hut::Uniqkind   -> String;
        uniqtyp_to_string:              hut::Uniqtyp -> String;
        uniqtype_to_string:             hut::Uniqtype   -> String;

        # Adjusting a hut::Uniqtype or hut::Uniqtyp
        # from one depth to another:
        #
        change_depth_of_uniqtyp:      (hut::Uniqtyp, di::Debruijn_Depth, di::Debruijn_Depth) -> hut::Uniqtyp;
        change_depth_of_uniqtype:      (hut::Uniqtype,   di::Debruijn_Depth, di::Debruijn_Depth) -> hut::Uniqtype;

        # These two fns are like change_depth_of_uniqtype and change_depth_of_uniqtyp.
        # They adjust a hut::Uniqtype (or hut::Uniqtyp) from depth d+k to depth nd+k,
        # assuming the last k levels are type abstractions.
        #
        # So change_depth_of_uniqtype is really change_k_depth_of_uniqtype with k set to 0.
        #
        # These fns are only called by improve-anormcode-quickly.pkg:
        #
        change_k_depth_of_uniqtyp:    (hut::Uniqtyp, di::Debruijn_Depth, di::Debruijn_Depth, Int) -> hut::Uniqtyp;      # Never used.
        change_k_depth_of_uniqtype:      (hut::Uniqtype,   di::Debruijn_Depth, di::Debruijn_Depth, Int) -> hut::Uniqtype;       # Never used.

        # Finding out the depth for a Type's
        # innermost-bound free variables:
        #
        max_freevar_depth_in_uniqtyp:  (hut::Uniqtyp, di::Debruijn_Depth) -> di::Debruijn_Depth;
        max_freevar_depth_in_uniqtyps: (List( hut::Uniqtyp ), di::Debruijn_Depth) -> di::Debruijn_Depth;


        # Mapping highcode variables to their uniqtypes.
        # Note that hut::Uniqtype is depth-dependent:
        #
        Highcode_Variable_To_Uniqtype_Map;
        #
        exception HIGHCODE_VARIABLE_NOT_FOUND;
        #
        empty_highcode_variable_to_uniqtype_map:  Highcode_Variable_To_Uniqtype_Map;
        #
        get_uniqtype_for_var:  (Highcode_Variable_To_Uniqtype_Map, tmp::Codetemp, di::Debruijn_Depth)                   -> hut::Uniqtype;
        #
        set_uniqtype_for_var:  (Highcode_Variable_To_Uniqtype_Map, tmp::Codetemp, hut::Uniqtype, di::Debruijn_Depth)    -> Highcode_Variable_To_Uniqtype_Map;



        # Instantiating a typeagnostic type
        # or a higher-order constructor:
        #
        apply_typeagnostic_type_to_arglist:                       (hut::Uniqtype, List(hut::Uniqtyp))   ->   List(hut::Uniqtype);
        apply_typeagnostic_type_to_arglist_with_single_result:    (hut::Uniqtype, List(hut::Uniqtyp))   ->        hut::Uniqtype;

        exception KIND_TYP_CHECK_FAILED;
        exception APPLY_TYPEFUN_CHECK_FAILED;

        apply_typeagnostic_type_to_arglist_with_checking_thunk
            :
            Void                                                                                        # Evaluating the thunk allocates a new memo dictionary.
             -> (hut::Uniqtype, List(hut::Uniqtyp), hut::Debruijn_To_Uniqkind_Listlist)
             -> List(hut::Uniqtype);



        # Substitution of named type variables in Uniqtyps and Uniqtypes.
        #
        # ** CLEAN THIS UP **           XXX BUGGO FIXME

        tc_named_typevar_elimination_thunk                              # Evaluating the thunk allocates a new dictionary.
            :
            Void
            -> ((tmp::Codetemp, di::Debruijn_Depth) -> Null_Or(hut::Uniqtyp))
            -> di::Debruijn_Depth
            -> hut::Uniqtyp
            -> hut::Uniqtyp;
        #
        lt_named_typevar_elimination_thunk                              # Evaluating the thunk allocates a new dictionary.
            :
            Void
            -> ((tmp::Codetemp, di::Debruijn_Depth) -> Null_Or(hut::Uniqtyp)) 
            -> di::Debruijn_Depth
            -> hut::Uniqtype
            -> hut::Uniqtype;

        # !! BEWARE !!
        # The `subst' argument is assumed to be sorted with increasing tvars:
        #
        tc_nvar_subst_fn:  Void -> List( (tmp::Codetemp, hut::Uniqtyp) ) -> hut::Uniqtyp -> hut::Uniqtyp;
        lt_nvar_subst_fn:  Void -> List( (tmp::Codetemp, hut::Uniqtyp) ) -> hut::Uniqtype -> hut::Uniqtype;

        tc_nvar_cvt_fn:  Void -> List  ((tmp::Codetemp, Int)) -> di::Debruijn_Depth -> hut::Uniqtyp -> hut::Uniqtyp;

        lt_nvar_cvt_fn:  Void -> List  ((tmp::Codetemp, Int)) -> di::Debruijn_Depth -> hut::Uniqtype -> hut::Uniqtype;

        # The equivalent to make_typeagnostic_uniqtype for the nvar case:
        #
        lt_nvpoly:  (List ((tmp::Codetemp, hut::Uniqkind)), List( hut::Uniqtype )) -> hut::Uniqtype;

        # Special adjustment functions used during type specializations:
        #
        lt_sp_adj:  (List(hut::Uniqkind), hut::Uniqtype,   List( hut::Uniqtyp ), Int, Int) -> hut::Uniqtype;
        tc_sp_adj:  (List(hut::Uniqkind), hut::Uniqtyp, List( hut::Uniqtyp ), Int, Int) -> hut::Uniqtyp;
        #
        lt_sp_sink: (List(hut::Uniqkind), hut::Uniqtype,   di::Debruijn_Depth, di::Debruijn_Depth) -> hut::Uniqtype;
        tc_sp_sink: (List(hut::Uniqkind), hut::Uniqtyp, di::Debruijn_Depth, di::Debruijn_Depth) -> hut::Uniqtyp;

        # Utility functions used in nextcode only, should go away soon !                        XXX BUGGO FIXME
        #
        lt_is_fate:    hut::Uniqtype -> Bool;
        ltw_is_fate:   (hut::Uniqtype, (List( hut::Uniqtype ) -> X), (List( hut::Uniqtyp ) -> X), (hut::Uniqtype -> X)) -> X;

        # Other utility functions --- requires clean up!
        #
        lt_get_field:  (hut::Uniqtype, Int) -> hut::Uniqtype;
        lt_swap:       hut::Uniqtype       -> hut::Uniqtype;

        # Functions that manipulate the highcode function and record types:
        #
        ltc_fkfun:    (acf::Function_Notes, List(hut::Uniqtype), List(hut::Uniqtype)) -> hut::Uniqtype;
        ltd_fkfun:    hut::Uniqtype -> (List(hut::Uniqtype), List(hut::Uniqtype));                              # function_notes omitted 

        ltc_rkind:    (acf::Record_Kind, List( hut::Uniqtype )) -> hut::Uniqtype;
        ltd_rkind:    (hut::Uniqtype, Int) -> hut::Uniqtype;

        # Given a hut::Uniqtyp, select the appropriate update baseop:
        #
        tc_upd_prim:  hut::Uniqtyp -> hbo::Baseop;

        # Translating the hut::Uniqkind into the corresponding type:
        #
        uniqkind_to_uniqtype:       hut::Uniqkind -> hut::Uniqtype;

        # twrap type translation generator,
        # used by wrapping::wrapping:
        #
        twrap_fn:    Bool -> ( hut::Uniqtyp -> hut::Uniqtyp,
                               hut::Uniqtype   -> hut::Uniqtype,
                               hut::Uniqtyp -> hut::Uniqtyp,
                               hut::Uniqtype   -> hut::Uniqtype,
                               Void                 -> Void
                             );

        # tnarrow type translation generator,
        # used by src/lib/compiler/back/top/forms/drop-types-from-anormcode.pkg:
        #
        tnarrow_fn:  Void -> ( hut::Uniqtyp -> hut::Uniqtyp,
                               hut::Uniqtype   -> hut::Uniqtype,
                               Void            -> Void
                             );

    };                                                                  # api Highcode 
end;                                                                    # stipulate

## Copyright (c) 1998 YALE FLINT PROJECT 
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2013,
## released per terms of SMLNJ-COPYRIGHT.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext