15.3.145  src/lib/compiler/back/low/regor/iterated-register-coalescing.api

## iterated-register-coalescing.api                                     "regor" is a contraction of "register allocator"
#
# This is the core of the new register allocator -- the part
# that uses only the codetemp interference graph, not the
# machcode controlflow graph.
#
# Comments are primarily in the implementation file:
#
#     src/lib/compiler/back/low/regor/iterated-register-coalescing.pkg

# Compiled by:
#     src/lib/compiler/back/low/lib/lowhalf.lib






stipulate
    package fil =  file__premicrothread;                                # file__premicrothread          is from   src/lib/std/src/posix/file--premicrothread.pkg
    package rkj =  registerkinds_junk;                                  # registerkinds_junk            is from   src/lib/compiler/back/low/code/registerkinds-junk.pkg
herein

    # This api is implemented in:
    #
    #     src/lib/compiler/back/low/regor/iterated-register-coalescing.pkg
    #
    api Iterated_Register_Coalescing {
        #
        package cig: Codetemp_Interference_Graph                        # Codetemp_Interference_Graph   is from   src/lib/compiler/back/low/regor/codetemp-interference-graph.api
                 =   codetemp_interference_graph;

        package mv:  Regor_Priority_Queue                               # Regor_Priority_Queue          is from   src/lib/compiler/back/low/regor/regor-priority-queue.api
                     where  Element == cig::Move;

        package fz:  Regor_Priority_Queue                               # Regor_Priority_Queue          is from   src/lib/compiler/back/low/regor/regor-priority-queue.api
                     where  Element == cig::Node;

        Move_Queue;
        Freeze_Queue;

        no_optimization:       cig::Mode;
        biased_selection:      cig::Mode;
        dead_copy_elim:        cig::Mode;
        compute_span:          cig::Mode;
        save_copy_temps:       cig::Mode;
        has_parallel_copies:   cig::Mode;


        # Basic functions


        # Dump the interference graph to a stream:
        #
        dump_codetemp_interference_graph
            :
            cig::Codetemp_Interference_Graph
            ->
            fil::Output_Stream
            ->
            Void;

        show:   cig::Codetemp_Interference_Graph
                ->
                cig::Node
                ->
                String;


        # Add an edge to the interference graph 
        #
        add_edge:  cig::Codetemp_Interference_Graph -> (cig::Node, cig::Node) -> Void;


        # Create new nodes:
        #
        new_nodes
            :
            cig::Codetemp_Interference_Graph
            -> 
            { cost:     Float,
              pt:       cig::Program_Point,
              defs:     List( rkj::Codetemp_Info ),
              uses:     List( rkj::Codetemp_Info )
            }
            -> 
            List( cig::Node );  #  Defs 


        # Update the colors of register to reflect the current interference graph:
        #
        update_register_colors:   cig::Codetemp_Interference_Graph -> Void;
        update_register_aliases:  cig::Codetemp_Interference_Graph -> Void;

        mark_dead_copies_as_spilled:  cig::Codetemp_Interference_Graph -> Void;


        # Return the spill location id of the interference graph 
        #
        spill_loc:            cig::Codetemp_Interference_Graph -> Int -> Int;
        spill_loc_to_string:  cig::Codetemp_Interference_Graph -> Int -> String;


        # Create an initial set of worklists
        # from a new interference graph
        # and a list of moves:
        #
        init_work_lists
            :
            cig::Codetemp_Interference_Graph
            -> 
            { moves:  List( cig::Move )
            }
            -> 
            { simplify_worklist:  List( cig::Node ), 
              move_worklist:      Move_Queue, 
              freeze_worklist:    Freeze_Queue, 
              spill_worklist:     List( cig::Node )   #  high degreee nodes 
            };


        # Clear the interference graph but keep the nodes table intact 
        #
        clear_graph:  cig::Codetemp_Interference_Graph -> Void;


        # Remove all adjacency lists from the nodes table.
        #
        clear_nodes:  cig::Codetemp_Interference_Graph -> Void;


        # Simplify, Coalesce and Freeze until the work list is done
        #
        iterated_coalescing
            :
            cig::Codetemp_Interference_Graph
            -> 
            { simplify_worklist:    List( cig::Node ), 
              move_worklist:        Move_Queue,
              freeze_worklist:      Freeze_Queue,
              stack:                List( cig::Node )
            }
            ->
            { stack:  List( cig::Node ) 
            };


        # Potentially spill a node.
        #
        potential_spill_node
            :  
            cig::Codetemp_Interference_Graph
            ->
            { node:   cig::Node,
              cost:   Float,
              stack:  List( cig::Node )
            }
            ->
            { move_worklist:    Move_Queue,
              freeze_worklist:  Freeze_Queue,
              stack:            List( cig::Node )
            };


        # Color nodes on the stack, using Briggs' optimistic spilling.  
        # Return a list of actual spills 
        #
        select
            :  
            cig::Codetemp_Interference_Graph
            -> 
            { stack:   List( cig::Node ) }
            ->
            { spills:  List( cig::Node ) };                                             # Actual spills.


        init_mem_moves:  cig::Codetemp_Interference_Graph -> Void;                      # Incorporate memory <-> register moves.


        move_savings:  cig::Codetemp_Interference_Graph -> (Int -> Float);              # Compute spill savings due to memory <-> register moves.
    };
end;

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