PreviousUpNext

15.4.364  src/lib/compiler/back/low/regor/register-spilling-with-renaming-g.pkg

## register-spilling-with-renaming.pkg

# Compiled by:
#     src/lib/compiler/back/low/lib/register-spilling.lib



# This version also performs local renaming on the spill code.
# For example, spilling t below
#
#    t <- ...
#    .. <- t
#    ....
#    ....
#    .. <- t
#    .. <- t
#
# would result in
#
#    tmp1 <- ...
#    mem[t] <- tmp1
#    .. <- tmp1      <---- rename from t to tmp1
#    ....
#    ....
#    tmp2 <- mem[t]
#    .. <- tmp2
#    .. <- tmp2      <---- rename from t to tmp2
#
# That is, we try to avoid inserting reload code whenever it is possible.
# This is done by keeping track of which values are live locally.
#
# Allen (5/9/00)
#


#
# This module manages the spill/reload process. 
# The reason this is detached from the main module is that 
# I can't understand the old code. 
#
# Okay, now I understand the code.
#
# The new code does things slightly differently.
# Here, we are given an op and a list of registers to spill
# and reload.  We rewrite the op until all instances of these
# registers are rewritten.
#
# (12/13/99) Some major caveats when spill coalescing/coloring is used:
# When parallel copies are generated and spill coalescing/coloring is used,
# two special cases have to be identified:
#
# Case 1 (spill_loc dst = spill_loc src)
#        Suppose we have a parallel copy
#             (u, v) <- (x, y)
#        where u has to be spilled and y has to reloaded.  When both
#        u and y are mapped to location M.  The following wrong code may
#        be generated:
#                M <- x  (spill u)
#                v <- M  (reload y)
#        This is incorrect.  Instead, we generate a dummy copy and
#        delay the spill after the reload, like this:  
#               
#               tmp <- x (save value of u)
#               v <- M   (reload y)
#               M <- tmp (spill u)
# Case 2 (spill_loc copyTmp = spill_loc src)
#        Another case that can cause problems is when the spill location of
#        the copy temporary is the same as that of one of the sources:
#
#              (a, b, v) <- (b, a, u)  where spill_loc (u) = spill_loc (tmp) = v
#
#        The incorrect code is
#              (a, b) <- (b, a) 
#              v <- M
#        But then the shuffle code for the copy can clobber the location M.
#
#              tmp <- M
#              (a, b) <- (b, a) 
#              v <- tmp
#
#       (Note that spill_loc copyTmp = spill_loc src can never happen) 

# -- Allen Leung


stipulate
    package iht =  int_hashtable;                                               # int_hashtable                         is from   src/lib/src/int-hashtable.pkg
    package irc =  iterated_register_coalescing;                                # iterated_register_coalescing          is from   src/lib/compiler/back/low/regor/iterated-register-coalescing.pkg
    package lem =  lowhalf_error_message;                                       # lowhalf_error_message                 is from   src/lib/compiler/back/low/control/lowhalf-error-message.pkg
    package rkj =  registerkinds_junk;                                          # registerkinds_junk                    is from   src/lib/compiler/back/low/code/registerkinds-junk.pkg
    #
    debug = FALSE;
herein
    # This generic is nowhere invoked;  it provides an alternative to
    #
    #     src/lib/compiler/back/low/regor/register-spilling-g.pkg
    #
    generic package   register_spilling_with_renaming_g   (
        #             =================================
        #
        package mu:  Machcode_Universals;                                       # Machcode_Universals                   is from   src/lib/compiler/back/low/code/machcode-universals.api

        package ae:  Machcode_Codebuffer                                        # Machcode_Codebuffer                   is from   src/lib/compiler/back/low/emit/machcode-codebuffer.api
                     where
                         mcf == mu::mcf;                                        # "mcf" == "machcode_form" (abstract machine code).

        # Spilling a variable v creates tiny live-ranges at all its definitions
        # and uses.  The following parameter is the maximal distance of
        # live-ranges created between a definition and its use,
        # measured in the number of ops.  If, max_dist = D, then
        # the spill routine will never create a new live-range that is more
        # than D ops apart.
        #
        max_dist:  Ref( Int );

        # When this parameter is on, the spill routine will keep track of
        # multiple values for the renaming process.  This is recommended
        # if the architecture has a lot of free registers.  But it should
        # probably be turned off on the intel32.
        #
         keep_multiple_values:  Ref( Bool );
    )
    : (weak)  Register_Spilling                                                 # Register_Spilling             is from   src/lib/compiler/back/low/regor/register-spilling.api
    {
        # Export to client packages:
        #       
        package mcf =  mu::mcf;                                                 # "mcf" == "machcode_form" (abstract machine code).
        package rgk =  mcf::rgk;                                                # "rgk" == "registerkinds".
        package cig =  irc::cig;                                                # "cig" == "codetemp_interference_graph".

        stipulate
            fun error msg
                =
                lem::error("register_spilling_with_renaming_g", msg);

            fun dec1 n
                =
                unt::to_int_x (unt::from_int n - 0u1);

            fun dec { block, op }
                =
                { block, op=>dec1 op };


            package rst = regor_spill_types_g( mcf );                           # regor_spill_types_g           is from   src/lib/compiler/back/low/regor/regor-spill-types-g.pkg
        herein
            include rst;                                                        # Export it all to client packages.

            fun uniq codetemps
                =
                rkj::sortuniq_colored_codetemps  codetemps;


            fun pt2s { block, op }
                =
                "b" + int::to_string block + ":" + int::to_string op;

            buf = ae::make_codebuffer  [];

            # spilled_copy_tmps = lowhalf_control::get_counter "ra-spilled-copy-temps"; 


            # The following function performs spilling.
            #
            fun spill_rewrite
                { graph=> cig as cig::CODETEMP_INTERFERENCE_GRAPH { show_reg, spilled_regs, node_hashtable, mode, is_globally_allocated_register_or_codetemp, ... },
                  spill:       Spill, 
                  spill_copy_tmp:  Spill_Copy_Tmp, 
                  spill_src:   Spill_Src, 
                  rename_src:  Rename_Src,
                  reload:      Reload, 
                  reload_dst:  Reload_Dst, 
                  copy_instr:  Copy_Instr, 
                  registerkind,
                  spill_set,
                  reload_set,
                  kill_set
                }
                =
                { 
                    # Must do this to make sure
                    # the interference graph is 
                    # reflected to the registers

                    irc::update_register_aliases cig;

                    get_spill_loc = irc::spill_loc cig;

                    fun spill_loc_of (rkj::CODETEMP_INFO { id, ... } )
                        =
                        get_spill_loc id;

                    spill_locs_of =  map  spill_loc_of;

                    getnode =  (fn rkj::CODETEMP_INFO { id, ... } =  iht::get  node_hashtable  id);

                    max_dist' = *max_dist;

                    op_def_use = mu::def_use registerkind;

                    fun contains_locally_allocatable_registers  registers               # Return FALSE if all registers in list are globally allocated (like esp and edi on intel32), else return TRUE.
                        =
                        loop registers
                        where
                            fun loop [] =>   FALSE;
                                #
                                loop (register ! rest)
                                    =>
                                    if (is_globally_allocated_register_or_codetemp (rkj::interkind_register_id_of register))   loop rest;       # On intel32 esp, edi and virtual_framepointer are globally allocated (and thus unavailable to the register allocator).
                                    else                                                                                       TRUE;
                                    fi;
                            end;
                        end;


                    # Merge prohibited registers 

                    enter_spill =   iht::set  spilled_regs;

                    add_prohibited
                        =
                        apply   (fn register =  enter_spill (rkj::interkind_register_id_of register, TRUE)); 

                    get_spills  =  cig::ppt_hashtable::find spill_set;
                    get_spills  =  fn p =  case (get_spills p)
                                               THE s => s;
                                               NULL  => [];
                                           esac;

                    get_reloads =  cig::ppt_hashtable::find reload_set;

                    get_reloads =  fn p =   case (get_reloads p)
                                                # 
                                                THE s => s;
                                                NULL  => [];
                                            esac;

                    get_kills   =  cig::ppt_hashtable::find kill_set;
                    get_kills   =  fn p =  case (get_kills p)
                                               THE s => s;
                                               NULL  => [];
                                           esac;

                    fun get_loc (cig::NODE { color=>REF (cig::ALIASED n),    ... }) =>  get_loc n;
                        #
                        get_loc (cig::NODE { color=>REF (cig::RAMREG(_, m)), ... }) =>  cig::SPILL_TO_RAMREG m;
                        #
                        get_loc (cig::NODE { color=>REF (cig::SPILL_LOC s),  ... }) =>  cig::SPILL_TO_FRESH_FRAME_SLOT  s;
                        get_loc (cig::NODE { color=>REF (cig::SPILLED), id,  ... }) =>  cig::SPILL_TO_FRESH_FRAME_SLOT  id;
                        get_loc (cig::NODE { color=>REF (cig::CODETEMP),  id,  ... }) =>  cig::SPILL_TO_FRESH_FRAME_SLOT  id;
                        #
                        get_loc _ => error "get_loc";
                    end;

                    fun print_regs regs
                        = 
                        apply
                            (fn r
                                =
                                print (cat [ rkj::register_to_string r, " [", irc::spill_loc_to_string cig (rkj::universal_register_id_of r), "] " ])
                            )
                            regs;

                    parallel_copies
                        =
                        unt::bitwise_and (irc::has_parallel_copies, mode)  !=  0u0;


                    fun chase (rkj::CODETEMP_INFO { color => REF (rkj::ALIASED c), ... } ) =>   chase c;
                        chase c                                                   =>         c;
                    end;

                    fun register_id (rkj::CODETEMP_INFO { id, ... } )
                        =
                        id;


                    fun same_register
                          (
                            rkj::CODETEMP_INFO { id=>x, ... },
                            rkj::CODETEMP_INFO { id=>y, ... }
                          )
                        =
                        x == y;


                    fun same (x, reg_to_spill)
                        =
                        same_register (chase x, reg_to_spill);


                    # Rewrite the op given
                    # that a bunch of registers have 
                    # to be spilled and reloaded.
                    #
                    fun spill_rewrite { pt, ops, notes }
                        = 
                        {   # Dictionary manipulation functions.
                            # The dictionary is just a list of triples.

                            fun update (pt, dictionary, r, NULL)
                                    =>
                                    kill (dictionary, r);

                                update (pt, dictionary, r, THE make_reg)
                                    =>
                                    (r, make_reg, pt)
                                    !
                                    if *keep_multiple_values  dictionary;
                                    else                      [];
                                    fi;
                            end 

                            also
                            fun kill (dictionary, r)
                                =
                                loop (dictionary, [])
                                where
                                    fun loop ([], dictionary')
                                            =>
                                            dictionary';

                                        loop((naming as (r', _, _)) ! dictionary, dictionary')
                                            =>
                                            loop
                                              ( dictionary, 

                                                (rkj::codetemps_are_same_color (r, r'))
                                                   ??           dictionary'
                                                   ::  naming ! dictionary'
                                              );
                                    end;
                                end;


                            # Insert reloading code for an op.
                            # Note: reload code goes after the op, if any.
                            #
                            fun reload_instr (pt, op, reg_to_spill, dictionary, spill_loc)
                                = 
                                {   my { code, prohibitions, make_reg }
                                        =
                                        reload { instruction => op, reg=>reg_to_spill, spill_loc, notes };

                                    add_prohibited  prohibitions; 

                                    (code, update (pt, dictionary, reg_to_spill, make_reg));
                                };


                            # Renaming the source for an op.
                            #
                            fun rename_instr (pt, op, reg_to_spill, dictionary, to_src)
                                = 
                                {   my { code, prohibitions, make_reg }
                                        =
                                        rename_src { instruction => op, from_src=>reg_to_spill, to_src };

                                    add_prohibited  prohibitions;

                                    (code, update (pt, dictionary, reg_to_spill, make_reg));
                                };


                            # Remove uses of reg_to_spill from a set of parallel copies.
                            # If there are multiple uses, then return multiple moves.
                            #
                            fun extract_uses (reg_to_spill, rds, rss)
                            =
                            loop (rds, rss, [], [], [])
                            where
                                fun loop (rd ! rds, rs ! rss, new_rds, rds', rss')
                                        =>
                                        if   (same (rs, reg_to_spill))

                                             loop (rds, rss, rd ! new_rds, rds', rss');
                                        else loop (rds, rss, new_rds, rd ! rds', rs ! rss');
                                        fi;

                                    loop (_, _, new_rds, rds', rss')
                                        =>
                                        (new_rds, rds', rss');
                                end;
                            end;


                            # Insert reload code for the sources of a copy.
                            # Transformation:
                            #    d1..dn <- s1..sn
                            # =>
                            #    d1..dn/r <- s1...sn/r.
                            #    reload code
                            #    reload copies
                            #
                            fun reload_copy_src (op, reg_to_spill, dictionary, spill_loc)
                                = 
                                {   (mu::move_dst_src  op)
                                        ->
                                        (dst, src);


                                    (extract_uses (reg_to_spill, dst, src))
                                        ->
                                        (rds, copy_dst, copy_src);



                                    fun process_moves ([], reload_code)
                                            =>
                                            reload_code; 

                                        process_moves (rd ! rds, reload_code)
                                            =>
                                            {   code = reload_dst { spill_loc, reg=>reg_to_spill, dst=>rd, notes };

                                                process_moves (rds, code@reload_code);
                                            };
                                    end;

                                    reload_code = process_moves (rds, []);

                                    case copy_dst
                                        #
                                        [] =>  (reload_code, dictionary);
                                        _  =>  ( copy_instr((copy_dst, copy_src), op) @ reload_code,
                                                 dictionary
                                               );
                                    esac;
                                }; 

                            fun diff ( { block=>b1: Int, op=>i1 },{ block=>b2, op=>i2 } )
                                =
                                if (b1 == b2)   i1 - i2;
                                else        max_dist' + 1;
                                fi;


                            # Insert reload code
                            #
                            fun reload (pt, op, reg_to_spill, dictionary, spill_loc)
                                =
                                if (mu::move_instruction op)
                                    #     
                                    reload_copy_src (op, reg_to_spill, dictionary, spill_loc); 
                                else
                                    lookup dictionary
                                    where
                                        fun lookup []
                                                =>
                                                reload_instr (pt, op, reg_to_spill, dictionary, spill_loc);

                                            lookup((r, current_reg, def_pt) ! dictionary)
                                                =>
                                                if (not (rkj::codetemps_are_same_color (r, reg_to_spill)))
                                                    #
                                                    lookup dictionary;
                                                else
                                                    if (def_pt == pt)
                                                        #
                                                        lookup dictionary;              # This is NOT the right renaming!  XXX BUGGO FIXME
                                                    else
                                                        if (diff (def_pt, pt) <= max_dist')
                                                             #
                                                             rename_instr (pt, op, reg_to_spill, dictionary, current_reg);
                                                        else reload_instr (pt, op, reg_to_spill, dictionary, spill_loc);
                                                        fi;
                                                    fi;
                                                fi;
                                        end;
                                    end;
                                fi;


                            # Check whether the id is in a list
                            #
                            fun contains_id (id, [])                                 =>   FALSE;
                                contains_id (id: rkj::Universal_Register_Id, r ! rs) =>   r == id or contains_id (id, rs);
                            end;

                            fun spill_conflict (cig::SPILL_TO_FRESH_FRAME_SLOT loc,                rs) =>   contains_id (-loc, rs);
                                spill_conflict (cig::SPILL_TO_RAMREG (rkj::CODETEMP_INFO { id, ... } ), rs) =>   contains_id (  id, rs);
                            end;

                            fun contains (r',     []) =>   FALSE;
                                contains (r', r ! rs) =>   same_register (r', r) or contains (r', rs);
                            end;


                            # Insert spill code for an op.
                            # Spill code occur after the op.
                            # If the value in regToSpill is never used, the client also
                            # has the opportunity to remove the op.
                            #
                            fun spill_instr (pt, op, reg_to_spill, spill_loc, kill, dictionary)
                                = 
                                {   my { code, prohibitions, make_reg }
                                        =
                                        spill { instruction => op, 
                                                kill, spill_loc,
                                                reg=>reg_to_spill, notes
                                              };

                                    add_prohibited  prohibitions;

                                    (code, update (pt, dictionary, reg_to_spill, make_reg));
                                };

                            # Remove the definition regToSpill <- from 
                            # parallel copies rds <- rss.
                            # Note, there is a guarantee that regToSpill is not aliased
                            # to another register in the rds set.
                            #
                            fun extract_def (reg_to_spill, rds, rss, kill)
                                =
                                loop (rds, rss, [], [])
                                where
                                    fun loop (rd ! rds, rs ! rss, rds', rss')
                                            =>
                                            if (spill_loc_of rd == spill_loc_of rs)  (rs, rds@rds', rss@rss', TRUE);
                                            elif (same (rd, reg_to_spill))           (rs, rds@rds', rss@rss', kill);
                                            else                               loop (rds, rss, rd ! rds', rs ! rss');
                                            fi;

                                       loop _
                                           =>
                                           {   fun pr r
                                                   =
                                                   print (cat [
                                                       rkj::register_to_string r, ":", int::to_string (spill_loc_of r), " "
                                                     ]);

                                               print("rds="); 
                                               apply pr rds;
                                               print("\nrss="); 
                                               apply pr rss;
                                               print "\n";
                                               error("extractDef: " + rkj::register_to_string reg_to_spill);
                                           };
                                    end;
                                end;


                            # Insert spill code for a destination of a copy
                            #    suppose d = r and we have a copy d <- s in
                            #    d1...dn <- s1...sn
                            #
                            #    d1...dn <- s1...sn
                            # =>
                            #    spill s to spill_loc 
                            #    d1...dn/d <- s1...sn/s
                            #
                            #    However, if the spill code may ovewrite the spill location
                            #    shared by other uses, we do the following less 
                            #    efficient scheme:  
                            #
                            #    # save the result of d
                            #    d1...dn, tmp <- s1...sn, s
                            #    spill tmp to spill_loc    # spill d
                            #
                            fun spill_copy_dst (pt, op, reg_to_spill, spill_loc, kill, dictionary, don't_overwrite)
                                = 
                                {   (mu::move_dst_src  op)
                                        ->
                                        (dst, src);


                                    (extract_def (reg_to_spill, dst, src, kill))
                                        ->
                                        (mv_src, copy_dst, copy_src, kill);


                                    copy = case copy_dst
                                               [] =>  [];
                                               _  =>  copy_instr ((copy_dst, copy_src), op);
                                           esac;

                                    if kill                                  # Kill the move.
                                        #
                                        # print ("Copy " + int::to_string (hd mvDst) + " <- " +
                                        #         int::to_string (hd mvSrc) + " removed\n");
                                        (copy, dictionary);
                                    else
                                        # Normal spill. 

                                        if (spill_conflict (spill_loc, don't_overwrite))
                                            #
                                            # Cycle found 

                                            # print("Register r" + int::to_string regToSpill  +  
                                            #         " overwrites [" + int::to_string spill_loc + "]\n")

                                            tmp  =  mcf::rgk::clone_codetemp_info  reg_to_spill;        #  new temporary 

                                            copy =  copy_instr((tmp ! copy_dst, mv_src ! copy_src),
                                                                     op); 

                                            spill_code = spill_src { src=>tmp, reg=>reg_to_spill,
                                                                    spill_loc,
                                                                    notes };

                                            (copy @ spill_code, [(reg_to_spill, tmp, pt)]);

                                        else
                                            # Spill the move op.

                                            spill_code
                                                =
                                                spill_src
                                                  { src => mv_src,
                                                    reg => reg_to_spill,
                                                    spill_loc,
                                                    notes
                                                  };

                                            (spill_code @ copy, [(reg_to_spill, mv_src, pt)]);
                                        fi;
                                    fi;
                                };                      # fun spill_copy_dst

                            # Insert spill code for a copy
                            #
                            fun spill_copy (pt, op, reg_to_spill, spill_loc, kill, dictionary, don't_overwrite)
                                =
                                case (mu::move_tmp_r op)
                                    #                         
                                    NULL =>
                                        spill_copy_dst (pt, op, reg_to_spill, spill_loc, kill, dictionary,
                                                      don't_overwrite);
                                    THE tmp
                                        => 
                                        if (same (tmp, reg_to_spill))
                                            #
                                            #  spilledCopyTmps := *spilledCopyTmps + 1; 
                                            ( [spill_copy_tmp { copy=>op, spill_loc, reg=>reg_to_spill, notes } ],
                                              []
                                            );
                                        else
                                            spill_copy_dst (pt, op, reg_to_spill, spill_loc, kill, dictionary, don't_overwrite);
                                        fi;
                                esac;

                            # Insert spill code
                            #
                            fun spill (pt, op, reg_to_spill, spill_loc, kill_set, dictionary, don't_overwrite)
                                =
                                {   kill =  contains (reg_to_spill, kill_set);

                                    if (mu::move_instruction op)
                                         #    
                                         spill_copy  (pt, op, reg_to_spill, spill_loc, kill, dictionary, don't_overwrite);
                                    else spill_instr (pt, op, reg_to_spill, spill_loc, kill, dictionary);
                                    fi;
                                };

                            fun contains ([],     reg) =>  FALSE;
                                contains (r ! rs, reg) =>  same (r, reg) or contains (rs, reg);
                            end;

                            fun has_def (i, reg) =  contains (#1 (op_def_use i), reg);
                            fun has_use (i, reg) =  contains (#2 (op_def_use i), reg);

                            fun spill_one_reg (pt,[], _, _, _, dictionary, _)
                                    =>
                                    ([], dictionary);

                                spill_one_reg (pt, i ! ops, r, spill_loc, kill_set, dictionary, don't_overwrite)
                                    =>
                                    if (has_def (i, r))
                                        #
                                        (spill (pt, i, r, spill_loc, kill_set, dictionary, don't_overwrite))
                                            ->
                                            (ops', dictionary);

                                        spill_one_reg (pt, ops' @ ops, r, spill_loc, kill_set, dictionary, don't_overwrite);

                                    else
                                        (spill_one_reg (pt, ops, r, spill_loc, kill_set, dictionary, don't_overwrite))
                                            ->
                                            (ops, dictionary);

                                        (i ! ops, dictionary);
                                    fi;
                            end;


                            fun reload_one_reg (pt,[], _, dictionary, _)
                                    =>
                                    ([], dictionary);

                                reload_one_reg (pt, i ! ops, r, dictionary, spill_loc)
                                    => 
                                    if (has_use (i, r))
                                        #
                                        (reload (pt, i, r, dictionary, spill_loc))
                                            ->
                                            (ops', dictionary);

                                        reload_one_reg (pt, ops' @ ops, r, dictionary, spill_loc);

                                    else
                                        (reload_one_reg (pt, ops, r, dictionary, spill_loc))
                                            ->
                                            (ops, dictionary);

                                        (i ! ops, dictionary); 
                                    fi;
                            end;


                            # This function spills a set of
                            # registers for an op:
                            #
                            fun spill_all (pt, ops, [], kill_set, dictionary, don't_overwrite)
                                    =>
                                    (ops, dictionary);

                                spill_all (pt, ops, r ! rs, kill_set, dictionary, don't_overwrite)
                                    => 
                                    {   node      = getnode r;
                                        spill_loc = get_loc node;

                                        (spill_one_reg (pt, ops, r, spill_loc, kill_set, dictionary, don't_overwrite))
                                            ->
                                            (ops, dictionary);

                                        spill_all (pt, ops, rs, kill_set, dictionary, don't_overwrite);
                                    };
                            end;


                            # This function reloads a set of
                            # registers for an op:
                            #
                            fun reload_all (pt, ops, dictionary,[])
                                    =>
                                    (ops, dictionary);

                                reload_all (pt, ops, dictionary, r ! rs)
                                    => 
                                    {   node     = getnode r;
                                        spill_loc = get_loc node;

                                        (reload_one_reg (pt, ops, r, dictionary, spill_loc))
                                            ->
                                            (ops, dictionary);

                                        reload_all (pt, ops, dictionary, rs);
                                    };
                            end;

                            fun loop ([], pt, dictionary, new_ops)
                                    =>
                                    new_ops;

                                loop (op ! rest, pt, dictionary, new_ops)
                                    => 
                                    {   spill_regs  =  get_spills  pt;
                                        reload_regs =  get_reloads pt;

                                        case (spill_regs, reload_regs)
                                            #
                                            ([], [])
                                                => 
                                                {   dictionary'
                                                        =
                                                        case dictionary
                                                            #
                                                            [] => []; #  An approximation here 

                                                            _  =>
                                                               {   my (defs, uses)
                                                                       =
                                                                       op_def_use op;

                                                                   (contains_locally_allocatable_registers  defs or
                                                                    contains_locally_allocatable_registers  uses
                                                                   )
                                                                      ?? []
                                                                      :: dictionary;
                                                               };
                                                        esac;

                                                    # Should be handled better  XXX BUGGO FIXME
                                                    #
                                                    loop (rest, dec pt, dictionary', op ! new_ops);
                                                };

                                            _   =>
                                                {   #  Eliminate duplicates from the spill/reload candidates 

                                                    kill_regs   =  get_kills pt;
                                                    spill_regs  =  uniq spill_regs;
                                                    reload_regs =  uniq reload_regs;


                                                    # Spill locations that we can't overwrite
                                                    # if we are spilling a parallel copy

                                                    don't_overwrite
                                                        = 
                                                        if parallel_copies   spill_locs_of reload_regs;
                                                        else                 [];
                                                        fi;

                                                    fun pr_dictionary dictionary
                                                        =
                                                        {   print("Dictionary=");

                                                            apply
                                                                (fn (r, v, _)
                                                                    =
                                                                    print (cat [
                                                                        rkj::register_to_string r, "=>",
                                                                        rkj::register_to_string v, " "
                                                                      ]))
                                                                dictionary;

                                                            print "\n";
                                                        };

                                                    my (ops, dictionary)
                                                        = 
                                                        spill_all (pt,[op], spill_regs, kill_regs,
                                                                 dictionary, don't_overwrite);

                                                    if debug
                                                        #
                                                        print("pt=" + pt2s pt + "\n");

                                                        case spill_regs
                                                            #
                                                            [] => ();

                                                            _  =>
                                                               {   print("Spilling "); 
                                                                   print_regs spill_regs;
                                                                   print "\n";
                                                               };
                                                        esac;

                                                        case reload_regs
                                                            #
                                                            [] => ();
                                                            _  =>
                                                               {   print("Reloading "); 
                                                                   print_regs reload_regs; 
                                                                   print "\n";
                                                               };
                                                        esac;

                                                        print "Before:";
                                                        buf.put_op op;
                                                        pr_dictionary dictionary;
                                                    fi;

                                                    (reload_all (pt, ops, dictionary, reload_regs))
                                                        ->
                                                        (ops, dictionary);

                                                    if debug
                                                        #
                                                        print "After:";
                                                        apply  buf.put_op  ops;
                                                        print "------------------\n";
                                                    fi;

                                                    fun cat (   [], l) =>  l;
                                                        cat (a ! b, l) =>  cat (b, a ! l);
                                                    end;

                                                    loop (rest, dec pt, dictionary, cat (ops, new_ops)); 
                                                };
                                        esac;
                                    };
                            end;                        # fun loop

                            loop (reverse ops, pt, [], []);

                        };                              # fun spill_rewrite
                    spill_rewrite;                                              # Should probably rename this spill_rewrite' ...
                };                                      # fun spill_rewrite
        end;                                            # stipulate
    };                                                  # generic package  register_spilling_with_renaming_g
end;                                                    # stipulate


## COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2013,
## released per terms of SMLNJ-COPYRIGHT.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext