## pick-available-hardware-register-by-round-robin-g.pkg "regor" == "register allocator".
#
# See background comments in:
#
# src/lib/compiler/back/low/regor/pick-available-hardware-register.api#
# Compare to:
#
# src/lib/compiler/back/low/regor/pick-available-hardware-register-by-first-available-g.pkg# Compiled by:
# src/lib/compiler/back/low/lib/lowhalf.libstipulate
package rwv = rw_vector; # rw_vector is from src/lib/std/src/rw-vector.pkgherein
# We get invoked from:
#
# src/lib/compiler/back/low/regor/regor-risc-g.pkg # src/lib/compiler/back/low/intel32/regor/regor-intel32-g.pkg #
generic package pick_available_hardware_register_by_round_robin_g (
# =================================================
#
first_register: Int; # Round-robin allocation will start at this number.
register_count: Int; # Round-robin allocation will start over at first_register after checking this many registers.
locally_allocated_hardware_registers: List( Int ); # Round-robin allocation will only return numbers from this list.
) # All numbers on this list must be in the range first_register -> first_register+register_count-1 inclusive.
: (weak) Pick_Available_Hardware_Register # Pick_Available_Hardware_Register is from src/lib/compiler/back/low/regor/pick-available-hardware-register.api {
exception GET_REGISTER;
# For concreteness, on intel32 what is happening
# here for int registers is
# first_register = 0;
# regiser_count = 8;
# locally_allocated_hardware_registers = [ebp, esi, ebx, ecx, edx, eax];
# So we're cycling through the eight possibilities round-robin, but
# never returning either of the two globally allocated registers esp, edi.
# Set up a vector we can index into quickly to
# distinguish forbidden globally-allocated registers
# from the locally-allocated ones we're allowed to use:
#
length_of_register_is_available = first_register + register_count;
#
register_is_available = rwv::make_rw_vector (length_of_register_is_available, FALSE); my _ =
#
apply
(\\ r = rwv::set (register_is_available, r, TRUE))
#
locally_allocated_hardware_registers;
# Set up the round-robin pointer.
# This runs from
#
last_reg = REF first_register; # XXX SUCKO FIXME More icky thread-hostile global mutable state.
fun reset_register_picker_state ()
=
last_reg := first_register;
# We are called (only) from:
#
# src/lib/compiler/back/low/regor/iterated-register-coalescing.pkg #
# Here register_is_taken is conceptually a boolean vector of
# register numbers which we may not pick because they are
# already taken -- conceptually a register is already taken iff
#
# register_is_taken [ register ]
#
# However, actually using a boolean vector would require us
# (well, our caller) to clear it each time, which is slow,
# so we use a standard little speed trick instead in which
# we increment a true_value in lieu of clearing, and say that
# a register is taken iff
#
# register_is_taken [ register ] == true_value.
#
# (In effect, each time we increment true_value, all the
# previously true values become false.)
#
# In practice, register_is_taken contains the colors (assigned registers)
# from our already-colored neighboring nodes in the codetemp interference
# graph -- this gets set up by the 'fill_in__register_is_taken__vector'
# functions in
#
# src/lib/compiler/back/low/regor/iterated-register-coalescing.pkg #
# But we don't need to konw that here:
#
fun pick_available_hardware_register
{
preferred_registers, # In practice this is currently always [].
register_is_taken,
true_value: Int # for use in test: register_is_taken[register] == true_value.
}
=
check_preferred preferred_registers
where
# Use preferred registers
# whenever possible:
#
fun check_preferred (register ! registers)
=>
if ( rwv::get (register_is_taken, register) != true_value # if register is not taken.
and rwv::get (register_is_available, register) # and if register is locally-allocatable (i.e., not globally allocated like esp)
)
register; # then we can return it -- success!
else
check_preferred registers; # Owell -- try next preferred register.
fi;
check_preferred [] => do_round_robin_search *last_reg; # None of the preferred registers are available.
end
# If not, use the round robin
# scheme to pick a register:
#
also # Not actually mutually recursive.
fun do_round_robin_search start
=
{ found = search start; # Do the round-robin search, latch the result.
next = found + 1; # Remember where to pick up on next call.
next = if (next >= length_of_register_is_available) first_register;
else next;
fi;
last_reg := next;
found; # Return the register we picked.
}
where
fun search r
=
if (rwv::get (register_is_taken, r) != true_value # If register is not taken.
and rwv::get (register_is_available, r)) # and if register is locally-allocatable (i.e., not globally-allocated like esp)
#
r; # then we can return it -- success!
else
r = r+1; # Owell -- try next register in round-robin.
r = if (r >= length_of_register_is_available) first_register; # Wrap around properly to start at end of round-robin sequence.
else r;
fi;
if (r != start) search r; # If we haven't checked all possiblities, we're good to go.
else raise exception GET_REGISTER; # Oops, there are no eligible registers. Caller supposedly guarantees this cannot happen.
fi;
fi;
end;
end;
last_reg_pair = REF first_register; # XXX BUGGO FIXME More icky thread-hostile global mutable state.
fun pick_available_hardware_registerpair # This is a stillborn idea -- never used.
{
preferred_registers,
register_is_taken,
true_value: Int
}
=
find *last_reg_pair
where
# If not, use the round robin scheme
# to get a register:
#
fun find start
=
{ limit = rwv::length register_is_available;
fun search r
=
if (rwv::get (register_is_taken, r ) != true_value
and rwv::get (register_is_taken, r+1) != true_value
and rwv::get (register_is_available, r )
and rwv::get (register_is_available, r+1)
)
r;
else
nxt = r+1;
nxt_r = if (nxt+1 >= limit) first_register;
else nxt;
fi;
if (nxt_r != start) search nxt_r;
else raise exception GET_REGISTER;
fi;
fi;
found = search start;
next = found + 1;
next = next+1 >= limit ?? first_register
:: next;
last_reg_pair := next;
found;
};
end;
};
end;
## COPYRIGHT (c) 1996 Bell Laboratories.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.