PreviousUpNext

15.3.211  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 format, which preserves expression tree structure) is the second backend code representation, and the first used for optimization.
#     5)  Nextcode ("continuation-passing style", a single-assignment basic-block-graph form where call and return are essentially the same) 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-PASSES.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
#     unnest_nextcode_fns                       src/lib/compiler/back/top/closures/unnest-nextcode-fns.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::Uniqtype, and 
# hut::Uniqtypoid 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 hut =  highcode_uniq_types;                                         # highcode_uniq_types           is from   src/lib/compiler/back/top/highcode/highcode-uniq-types.pkg
    package pp  =  standard_prettyprinter;                                      # standard_prettyprinter        is from   src/lib/prettyprint/big/src/standard-prettyprinter.pkg
    package tmp =  highcode_codetemp;                                           # highcode_codetemp             is from   src/lib/compiler/back/top/highcode/highcode-codetemp.pkg
herein

    api Highcode_Form {
        #

        # We define hut::Uniqkind, hut::Uniqtype,
        # and hut::Uniqtypoid 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::Uniqtype, and hut::Uniqtypoid 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::Uniqtype, and hut::Uniqtypoid:
        #
        include api Highcode_Type;              # Highcode_Type         is from   src/lib/compiler/back/top/highcode/highcode-type.api

        # Functions for constructing Uniqkinds:
        #
        make_n_arg_typefun_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 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;

        make_typevar_i_uniqtype:        Int             -> hut::Uniqtype;       # Make typevar with de Bruijn depth==di::innermost and index==i
        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;

        # Prebuilt basetype uniqtypoids:
        #
        int_uniqtypoid:                 hut::Uniqtypoid;
        int1_uniqtypoid:                hut::Uniqtypoid;
        float64_uniqtypoid:             hut::Uniqtypoid;
        string_uniqtypoid:              hut::Uniqtypoid;
        exception_uniqtypoid:           hut::Uniqtypoid;
        truevoid_uniqtypoid:            hut::Uniqtypoid;
        void_uniqtypoid:                hut::Uniqtypoid;
        bool_uniqtypoid:                hut::Uniqtypoid;

        # Uniqtypoid constructors:
        #
        make_typevar_i_uniqtypoid:      Int             -> hut::Uniqtypoid;
        make_ref_uniqtypoid:            hut::Uniqtypoid -> hut::Uniqtypoid;
        make_rw_vector_uniqtypoid:      hut::Uniqtypoid -> hut::Uniqtypoid;
        make_ro_vector_uniqtypoid:      hut::Uniqtypoid -> hut::Uniqtypoid;
        make_exception_tag_uniqtypoid:  hut::Uniqtypoid -> hut::Uniqtypoid;

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

        # Testing the equivalence for types
        # and ltys with relaxed constraints:
        #
        similar_uniqtypes:              (hut::Uniqtype,   hut::Uniqtype  ) -> Bool;
        similar_uniqtypoids:            (hut::Uniqtypoid, hut::Uniqtypoid) -> Bool;

        # Prettyprinting of uniqkinds, uniqtypes, and uniqtypoids:
        #
        uniqkind_to_string:                                     hut::Uniqkind   -> String;
        uniqtype_to_string:                                     hut::Uniqtype   -> String;
        uniqtypoid_to_string:                                   hut::Uniqtypoid -> String;
        #
        prettyprint_uniqkind:           pp::Prettyprinter -> hut::Uniqkind   -> Void;
        prettyprint_uniqtype:           pp::Prettyprinter -> hut::Uniqtype   -> Void;
        prettyprint_uniqtypoid:         pp::Prettyprinter -> hut::Uniqtypoid -> Void;

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

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

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


        # Mapping highcode variables to their uniqtypoids.
        # Note that hut::Uniqtypoid is depth-dependent:
        #
        Highcode_Variable_To_Uniqtypoid_Map;
        #
        exception HIGHCODE_VARIABLE_NOT_FOUND;
        #
        empty_highcode_variable_to_uniqtypoid_map:  Highcode_Variable_To_Uniqtypoid_Map;
        #
        get_uniqtypoid_for_var:  (Highcode_Variable_To_Uniqtypoid_Map, tmp::Codetemp, di::Debruijn_Depth)                       -> hut::Uniqtypoid;
        #
        set_uniqtypoid_for_var:  (Highcode_Variable_To_Uniqtypoid_Map, tmp::Codetemp, hut::Uniqtypoid, di::Debruijn_Depth)      -> Highcode_Variable_To_Uniqtypoid_Map;



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

        exception KIND_TYPE_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::Uniqtypoid, List(hut::Uniqtype), hut::Debruijn_To_Uniqkind_Listlist)
             -> List(hut::Uniqtypoid);



        # Substitution of named type variables in Uniqtypes and Uniqtypoids.
        #
        # ** 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::Uniqtype))
            -> di::Debruijn_Depth
            -> hut::Uniqtype
            -> hut::Uniqtype;
        #
        lt_named_typevar_elimination_thunk                              # Evaluating the thunk allocates a new dictionary.
            :
            Void
            -> ((tmp::Codetemp, di::Debruijn_Depth) -> Null_Or(hut::Uniqtype)) 
            -> di::Debruijn_Depth
            -> hut::Uniqtypoid
            -> hut::Uniqtypoid;

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

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

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

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

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

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

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

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

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

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

        # Translating the hut::Uniqkind into the corresponding type:
        #
        uniqkind_to_uniqtypoid:       hut::Uniqkind -> hut::Uniqtypoid;

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

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

    };                                                                  # api Highcode 
end;                                                                    # stipulate

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


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext