(*
regalloc.ml
15-411
by Arthur O'Dwyer
*)
(* @version $Id: regalloc.ml,v 1.4 2004/11/01 09:21:32 ajo Exp $ *)
(*
The register-allocation function maps a program and a positive
integer number of registers onto a /new/ program (with spill code
inserted), a nonnegative integer number of stackslots that need
to be set up by the standard prelude, and a synthesized function
mapping individual temps onto their register or stackslot assignments.
This module implements Chaitin's algorithm for register allocation
and assignment, as described in class.
regalloc : instr list -> int -> (instr list * int * (temp -> regalloc_t))
*)
module A = Assem
module E = Errormsg
module P = Printf
open Types
exception RegallocBug of string
let print_instr i =
let temp2string t = Printf.sprintf "t%d" t
in print_string(A.format temp2string i)
let print_instrlist prog = List.iter print_instr prog
let print_live_1 livelst =
let eachitem res t = res ^ (match t with
| TEMP t -> Printf.sprintf " t%d" t
| REGISTER r -> Printf.sprintf " r%d" r
| _ -> " whoops!")
in print_string ((List.fold_left eachitem "" livelst) ^ "\n")
let print_live_in lstlst = List.iter print_live_1 lstlst
(*
An |igraph| is a mapping from temps to their |inode| data and
a list of their neighbors in the interference graph. Thus, all
entries in the table are of the form |(REGISTER r, ...)| or else
of the form |(TEMP t, ...)|. And the |REGISTER| entries are just
in there for completeness; they are pre-colored as |I_REGISTER|
and do not participate in the clever parts of Chaitin's algorithm.
This means that we can iterate over all the relevant entries
in the graph using |iota numtemps| or else using
|for t=1 to numtemps do|.
The second field of the data record, the |boolean| value, is
|true| if this node is a member of the graph and |false| otherwise.
This is so we don't have to actually destroy the whole graph during
the "destroy the graph" phase of Chaitin's algorithm; we just mark
deleted nodes with |false|, and remember not to count them as
neighbors of any remaining undeleted nodes.
*)
type inode = I_CAND of register
| I_CAND_REG of register
| I_REGISTER of register
| I_STACKSLOT of stackslot
type halfgraph = (regalloc_t,
(bool * inode * (regalloc_t list))
) Hashtbl.t
type igraph = int * halfgraph
(*
chaitin_init : (regalloc_t list list * int numregs) -> (igraph)
chaitin_iter : (igraph ref * int numregs) -> (int list temps_to_spill)
chaitin_final : (igraph ref) -> (temp -> reg_or_slot)
*)
let print_igraph mygraph =
let (numtemps, grph) = !mygraph in
Printf.printf "-------------------START_GRAPH\n";
for t = 1 to numtemps do
let (b,ra,nb) = Hashtbl.find grph (TEMP t) in
Printf.printf "%s\t" (if b then "true" else "false");
(match ra with
| I_CAND r -> Printf.printf "I_CAND %d\t" r
| I_CAND_REG r -> Printf.printf "I_CAND_REG %d\t" r
| I_REGISTER r -> Printf.printf "I_REGISTER %d\t" r
| I_STACKSLOT s -> Printf.printf "I_STACKSLOT %d\t" s
);
Printf.printf "with neighbors ";
for i=0 to (List.length nb)-1 do
match List.nth nb i with
| REGISTER r -> Printf.printf "r%d " r
| STACKSLOT s -> Printf.printf "s%d " s
| TEMP t -> Printf.printf "t%d " t
done;
Printf.printf "\n";
done;
print_string "-------------------END_GRAPH\n"
(*
The |iota| function returns the list $1..n$ for any given $n>=1$.
*)
let iota x =
let rec iota' x = if (x <= 0) then [] else (x :: iota'(x-1)) in
List.rev (iota' x)
(*
A couple of functions to deal with sets of things: |setplus|
and |setminus|. The arguments to these functions must be
lists, each of which contains no duplicate items. The lists
returned by these functions satisfy the same constraint.
type 'a set = ('a -> int) * BitList
set_of_list : 'a list -> ('a -> int) * (int -> 'a) -> int -> 'a set
set_to_list : 'a set -> 'a list
setplus : ('a set * 'a set) -> 'a set
setminus : ('a set * 'a set) -> 'a set
list_setplus : ('a list * 'a list) -> 'a list
list_setminus : ('a list * 'a list) -> 'a list
*)
type 'a set = ('a -> int) * (int -> 'a) * Bitlist.bitList_t
let set_of_list (a2i, i2a) len ali =
let bitli = Bitlist.newBitList len in
List.iter (fun a -> Bitlist.setBit bitli (a2i a)) ali;
(a2i, i2a, bitli)
let set_to_list (a2i, i2a, bitli) =
let rc = ref [] in
Bitlist.iterTrue (fun i -> rc := (i2a i)::!rc) bitli;
!rc
let setplus ((a2i, i2a, bitli1), (_, _, bitli2)) =
let bitli3 = Bitlist.orBLnew bitli1 bitli2 in
(a2i, i2a, bitli3)
let setminus ((a2i, i2a, bitli1), (_, _, bitli2)) =
let bitli3 = Bitlist.notBLnew bitli2 in
Bitlist.andBLto2 bitli1 bitli3;
(a2i, i2a, bitli3)
let sets_equal ((_, _, bitli1), (_, _, bitli2)) =
Bitlist.isEqual bitli1 bitli2
let rat2i = function
| REGISTER r -> r
| TEMP t -> (t+8)
let i2rat = function
| i when i<8 -> REGISTER i
| i -> TEMP (i-8)
let ratset = set_of_list (rat2i, i2rat)
let rec list_setplus = function
| (a, []) -> a
| ([], b) -> b
| (h::t, b) -> if (List.mem h b) then list_setplus(t,b)
else list_setplus(t,h::b)
let rec list_setminus = function
| (a, []) -> a
| ([], b) -> []
| (h::t, b) -> if (List.mem h b) then list_setminus(t,b)
else h::list_setminus(t,b)
(*
Remove duplicates from a list.
*)
let list_set_of_list ali =
let ali = List.fast_sort compare ali in
let rec help = function
| [] -> [] | [a] -> [a]
| a::b::t -> if (a=b) then help (b::t) else a::(help (b::t))
in help ali
let use_in = function
| MOVE(_,s,d) -> [s]
| OPER(_,s,d) | LIVEOPER(_,s,d) -> s
| JUMP _ | LABEL _ | COMMENT _ -> []
and def_in = function
| MOVE(_,s,d) -> [d]
| OPER(_,s,d) | LIVEOPER(_,s,d) -> d
| JUMP _ | LABEL _ | COMMENT _ -> []
(*
The function |get_live_in| takes a list of instructions
of length $N$ and returns a list of |livein| sets of length
$N+1$.
We ought to also remove any "dead code"---|MOVE| or |OPER|
instructions whose destination sets are not live. Those instructions
we just throw away. We do /not/ throw away |LIVEOPER| instructions,
which may have side effects not reflected by their "use" or "def"
lists.
get_live_in : instr list ref -> livein list
*)
let get_live_in prog ntemps =
let plen = List.length !prog in
let jumps_to_memo = Hashtbl.create 100 in
let jumps_to marker = (
let rec help n = function
| [] -> []
| (JUMP _ as j)::t ->
if (A.marker j = marker) then n::help (n+1) t
else help (n+1) t
| _::t -> help (n+1) t
in try (
Hashtbl.find jumps_to_memo marker
) with Not_found -> (
let result = help 0 !prog in
Hashtbl.add jumps_to_memo marker result;
result
)
) in
let find_label_memo = Hashtbl.create 100 in
let find_label marker = (
let rec help n = function
| [] -> plen
| (LABEL _ as k)::t ->
if (A.marker k = marker) then n
else help (n+1) t
| _::t -> help (n+1) t
in try (
Hashtbl.find find_label_memo marker
) with Not_found -> (
let result = help 0 !prog in
Hashtbl.add find_label_memo marker result;
result
)
) in
let pred i = (try (
match (List.nth !prog i) with
| LABEL _ as k when i=0 -> (jumps_to (Assem.marker k))
| LABEL _ as k -> (i-1)::(jumps_to (Assem.marker k))
| _ when i=0 -> []
| _ -> [i-1]
) with _->[i-1]
) in
let succ i = (try (
match (List.nth !prog i) with
| JUMP _ as j -> find_label (Assem.marker j) :: [i+1]
| _ -> [i+1]
) with _ -> []
) in
let usex = Array.init (plen+1) (fun i -> ratset ntemps
(try use_in(List.nth !prog i) with _->[REGISTER 1]))
and defx = Array.init (plen+1) (fun i -> ratset ntemps
(try def_in(List.nth !prog i) with _->[]))
and inx: regalloc_t set array = Array.init (plen+1) (fun i -> ratset
ntemps
(try use_in(List.nth !prog i) with _->[REGISTER 1]))
and outx: regalloc_t set array = Array.init (plen+1) (fun i -> ratset
ntemps [])
and notdone = ref true in
begin
while !notdone do
notdone := false;
ignore(E.debugf "GO LIVEIN! plen=%d\n" plen);
for i=plen downto 0 do
let help s = outx.(i) <- setplus(outx.(i), inx.(s)) in
List.iter help (succ i)
done;
for i=plen downto 0 do
let new_inxi = setplus(setminus(outx.(i), defx.(i)), inx.(i)) in
if not (sets_equal(new_inxi, inx.(i))) then notdone := true;
inx.(i) <- new_inxi;
done;
(*
if (!E.debug) then (
List.iter (function i ->
Printf.printf "%d) " (i-1);
(try print_instr (List.nth !prog (i-1))
with _ -> (print_string "---\n"));
print_string "usex: "; print_live_1 usex.(i-1);
print_string "defx: "; print_live_1 defx.(i-1);
print_string "inx: "; print_live_1 inx.(i-1);
print_string "outx: "; print_live_1 outx.(i-1)
) (iota (plen+1))
)
*)
done;
List.map set_to_list (Array.to_list inx)
end
(*
The function |get_all_temps| takes a list of instructions
and returns a set of all the temps mentioned in the source
and destination lists for that program.
get_all_temps : instr list -> temp list
count_temps : instr list -> int
*)
let get_all_temps prog =
let get_all_temps_helper ins set =
match ins with
| OPER(_,s,d) | LIVEOPER(_,s,d) -> (set @ d @ s)
| MOVE(_,s,d) -> s::d::set
| JUMP _ | LABEL _ | COMMENT _ -> set
in
List.fold_right get_all_temps_helper prog []
let count_temps prog =
let rec get_max_temp = function
| [] -> 0
| TEMP(h)::t -> max h (get_max_temp t)
| _::t -> get_max_temp t
in
get_max_temp (get_all_temps prog)
let chaitin_init initial_call mygraph
(interflist, numregs, numtemps, progr) =
let proga = Array.of_list !progr in
let rec populate_from n = function
| [] -> (
for i=1 to numtemps do
let (b, node, neighb) = Hashtbl.find (snd !mygraph) (TEMP i) in
let neighb = list_set_of_list neighb in
Hashtbl.replace (snd !mygraph) (TEMP i) (b, node, neighb);
done;
for i=1 to numregs do
let (b, node, neighb) = Hashtbl.find (snd !mygraph) (REGISTER i) in
let neighb = list_set_of_list neighb in
Hashtbl.replace (snd !mygraph) (REGISTER i) (b, node, neighb);
done
)
| h::t -> begin (try
populate_helper proga.(n) (list_setplus(h, def_in proga.(n)))
with _ -> populate_helper (LIVEOPER("",[],[])) h);
populate_from (n+1) t
end
and populate_helper ins lst = match lst with
| [] -> ()
| h::t -> begin
populate_helper_helper ins h t;
populate_helper ins t
end
and populate_helper_helper ins ra lst = try match lst with
| [] -> ()
| h::t -> (
(match ins with
| MOVE(_,s,d) when (s=ra) && (d=h) -> ()
| MOVE(_,s,d) when (s=h) && (d=ra) -> ()
| MOVE(_,s,d) when (s=d) -> ()
| _ -> (
let (rab, ranode, raneighbors) = Hashtbl.find (snd !mygraph) ra
and (hb, hnode, hneighbors) = Hashtbl.find (snd !mygraph) h in
let raneighbors = h::raneighbors
and hneighbors = ra::hneighbors in
Hashtbl.replace (snd !mygraph) h (hb, hnode, hneighbors);
Hashtbl.replace (snd !mygraph) ra (rab, ranode, raneighbors)
)
);
populate_helper_helper ins ra t
)
with
| Not_found -> raise (RegallocBug "population_h_h Not_found");
in
let initialize mygraph =
let allregs = iota numregs in
begin
Hashtbl.clear (snd !mygraph);
for r = 1 to numregs do
Hashtbl.add (snd !mygraph) (REGISTER r) (true, (I_REGISTER r),
List.map (fun x -> REGISTER x) (list_setminus(allregs, [r])))
done;
for t = 1 to numtemps do
Hashtbl.add (snd !mygraph) (TEMP t) (true, I_CAND 0, [])
done
end
in begin
if (initial_call) then begin
initialize mygraph
end;
populate_from 0 interflist;
mygraph := (numtemps, snd !mygraph)
end
let chaitin_final mygraph =
(fun t -> try match (Hashtbl.find (snd !mygraph) (TEMP t)) with
| (_, I_STACKSLOT s, _) -> STACKSLOT s
| (_, I_CAND r, _) -> if (r>0) then REGISTER r
else raise (RegallocBug
(Printf.sprintf "CAND Temp %d was not assigned!" t))
| (_, I_CAND_REG r, _) -> if (r>0) then REGISTER r
else raise (RegallocBug
(Printf.sprintf "CAND_REG Temp %d was not assigned!" t))
| _ -> raise (RegallocBug
(Printf.sprintf "ELSE Temp %d was not assigned!" t))
with Not_found -> raise (RegallocBug
(Printf.sprintf "NOTFOUND Temp %d was not assigned!" t))
)
exception RemovedAllNodes
exception SpillRandomTemp of regalloc_t
let chaitin_iter(mygraph, numregs) =
let mystack: temp list ref = ref []
and (numtemps,grph) = !mygraph
and temps_to_spill = ref [] in
let remove_a_graph_node() =
begin
(*
If there exists a node of degree $<= numregs$, remove it.
Otherwise, remove a node at random. If no nodes are left
at all, then raise the exception |RemovedAllNodes|.
*)
let is_undeleted t =
let (b,_,_) = Hashtbl.find grph t in (b)
and is_nonstack t =
let (_,ra,_) = Hashtbl.find grph t in
match ra with I_STACKSLOT _ -> false | _ -> true
in
let has_degree_less_than k t =
let (_,_,nb) = Hashtbl.find grph t in
let real_nb = List.filter is_undeleted nb in
let nonstack_nb = List.filter is_nonstack nb in
(List.length nb < k)
in
let poss = List.map (fun x->TEMP x) (List.rev (iota numtemps)) in
let good = List.filter is_undeleted poss in
let better = List.filter (has_degree_less_than numregs) good in
let deTemp = function TEMP x->x | _->raise (RegallocBug "detemp") in
let to_remove =
match better with
| h::t -> ignore(E.debugf "Better %d.\n" (deTemp h)); h
| [] -> match good with
| h::t -> ignore(E.debugf "Good %d.\n" (deTemp h)); h
| [] -> raise RemovedAllNodes
in begin
let (x,y,z) = Hashtbl.find grph to_remove in
Hashtbl.replace grph to_remove (false,y,z);
mystack := (deTemp to_remove) :: !mystack
end
end in
let rec replace_nodes (lst: temp list) = match lst with
| [] -> !temps_to_spill
| h::t -> try
ignore(E.debugf "Trying to color t%d...\n" h);
(*
Color this node, or else add it to the list of temps to spill.
*)
let rec get_nb_regset nblist succ = match nblist with
| [] -> succ
| h::t ->
let (exists,ra,_) = Hashtbl.find grph h in begin
if (not exists) then get_nb_regset t succ
else match ra with
| I_REGISTER(r) -> get_nb_regset t (list_setplus(succ, [r]))
| I_CAND_REG(r) -> get_nb_regset t (list_setplus(succ, [r]))
| I_CAND(r) -> get_nb_regset t (list_setplus(succ, [r]))
| _ -> get_nb_regset t succ
end
in
let th = TEMP(h) in
let (_,hra,hnb) = Hashtbl.find grph th in
begin
match hra with
| I_CAND _ -> begin
let nb_regset = get_nb_regset hnb [] in
let okay_colors = List.filter
(fun x -> not (List.mem x nb_regset)) (iota numregs) in
match okay_colors with
| [] -> (
(* Spill this temp, |h|. *)
temps_to_spill := h :: !temps_to_spill;
Hashtbl.replace grph th (true, I_STACKSLOT 0, hnb)
)
| newcol::_ ->
Hashtbl.replace grph th (true, I_CAND newcol, hnb)
end
| I_CAND_REG _ -> begin
let nb_regset = get_nb_regset hnb [] in
let okay_colors = List.filter
(fun x -> not (List.mem x nb_regset)) (iota numregs) in
match okay_colors with
| [] -> begin
(*
This is a tricky part of Chaitin's algorithm. We have
here a temp that has been marked as |I_CAND_REG|, which
means it definitely must go in a register. But we have
colored ourselves into a corner here! We can't spill
this register; we must spill another one.
What I've done here is to pick a random spillable
register to spill. That's very icky, and I'm not
entirely convinced it will always work, either.
*)
let is_spillable t =
match (Hashtbl.find grph t) with
| (_,I_CAND _,_) -> true
| _ -> false
in
let poss = List.map (fun x->TEMP x) (iota numtemps) in
let good = List.filter is_spillable poss in
match good with
| h::t -> raise (SpillRandomTemp h)
| [] -> raise (RegallocBug "We have hit a serious \
error, which is probably a bug.\nThe graph \
is completely full of I_CAND_REG nodes, and \
it's still uncolorable!\nThere is nothing I \
can do. I'm going to crash now.")
end
| newcol::_ ->
Hashtbl.replace grph th (true, I_CAND_REG newcol, hnb)
end
| I_REGISTER _
| I_STACKSLOT _ -> (* do nothing but add the node to the graph *)
Hashtbl.replace grph th (true, hra, hnb)
end;
replace_nodes t
with SpillRandomTemp (TEMP t) -> (t :: !temps_to_spill)
in
begin
(* Initialize every candidate temp to being-in-the-graph. *)
for t = 1 to numtemps do try
let (_,ra,neighbors) = Hashtbl.find grph (TEMP t) in
Hashtbl.replace grph (TEMP t) (true,ra,neighbors)
with Not_found -> raise (RegallocBug (Printf.sprintf
"numtemps foo %d" t));
done;
try
while true do
remove_a_graph_node()
done;
raise (RegallocBug "-9999") (* never reached *)
with RemovedAllNodes -> replace_nodes(!mystack)
end
let rec trim_extra_moves alloc_fn instrlst = begin
match instrlst with
| [] -> []
| (MOVE(_,TEMP s,TEMP d) as h)::t -> begin
let s_assignment = alloc_fn(s)
and d_assignment = alloc_fn(d) in
if (s_assignment = d_assignment) then
trim_extra_moves alloc_fn t
else
h :: (trim_extra_moves alloc_fn t)
end
| (MOVE(_,TEMP s,REGISTER d) as h)::t -> begin
let s_assignment = alloc_fn(s) in
if (s_assignment = REGISTER d) then
trim_extra_moves alloc_fn t
else
h :: (trim_extra_moves alloc_fn t)
end
| (MOVE(_,REGISTER s,TEMP d) as h)::t -> begin
let d_assignment = alloc_fn(d) in
if (REGISTER s = d_assignment) then
trim_extra_moves alloc_fn t
else
h :: (trim_extra_moves alloc_fn t)
end
| (_ as h)::t -> h :: (trim_extra_moves alloc_fn t)
end
let regalloc (numregs, stackstart) prog =
let maxtemp = ref (count_temps prog) in
let get_new_temp() = begin maxtemp := !maxtemp+1; !maxtemp end in
let maxslot = ref stackstart in
let get_new_stackslot() = begin maxslot := !maxslot+1; !maxslot end in
let curprog = ref prog
and mygraph = ref (0, Hashtbl.create 0) in
let rec rewrite_program(prog, to_spill) = begin
let tempReplace(what,how) lst =
let repl x = if (x = what) then how else x
in List.map repl lst
in
match prog with
| [] -> []
| OPER(s,srcl,dstl) :: t -> begin
if (List.mem to_spill srcl) or (List.mem to_spill dstl) then
let tmp = TEMP(get_new_temp()) in
let result = ref [] in
mygraph := (1+fst !mygraph, snd !mygraph);
Hashtbl.replace (snd !mygraph) tmp (true, I_CAND_REG 0, []);
if (List.mem to_spill dstl) then begin
result := MOVE("movl\t's0, 'd0", tmp, to_spill) :: !result
end;
result := OPER(s, tempReplace(to_spill, tmp) srcl,
tempReplace(to_spill, tmp) dstl) :: !result;
if (List.mem to_spill srcl) then begin
result := MOVE("movl\t's0, 'd0", to_spill, tmp) :: !result
end;
!result @ rewrite_program(t, to_spill)
else
OPER(s,srcl,dstl) :: rewrite_program(t, to_spill)
end
| LIVEOPER(s,srcl,dstl) :: t -> begin
if (List.mem to_spill srcl) or (List.mem to_spill dstl) then
let tmp = TEMP(get_new_temp()) in
let result = ref [] in
mygraph := (1+fst !mygraph, snd !mygraph);
Hashtbl.replace (snd !mygraph) tmp (true, I_CAND_REG 0, []);
if (List.mem to_spill dstl) then begin
result := MOVE("movl\t's0, 'd0", tmp, to_spill) :: !result
end;
result := LIVEOPER(s, tempReplace(to_spill, tmp) srcl,
tempReplace(to_spill, tmp) dstl) :: !result;
if (List.mem to_spill srcl) then begin
result := MOVE("movl\t's0, 'd0", to_spill, tmp) :: !result
end;
!result @ rewrite_program(t, to_spill)
else
LIVEOPER(s,srcl,dstl) :: rewrite_program(t, to_spill)
end
| MOVE(s,src,dst) :: t -> begin
if (src = to_spill) && (dst = to_spill) then begin
(* Move from here to itself? Get rid of that! *)
rewrite_program(t, to_spill)
end
else if (src = to_spill) then begin
let tmp = TEMP(get_new_temp()) in
mygraph := (1+fst !mygraph, snd !mygraph);
Hashtbl.replace (snd !mygraph) tmp (true, I_CAND_REG 0, []);
MOVE("movl\t's0, 'd0", src, tmp) ::
MOVE(s, tmp, dst) ::
rewrite_program(t, to_spill)
end
else if (dst = to_spill) then begin
let tmp = TEMP(get_new_temp()) in
mygraph := (1+fst !mygraph, snd !mygraph);
Hashtbl.replace (snd !mygraph) tmp (true, I_CAND_REG 0, []);
MOVE(s, src, tmp) ::
MOVE("movl\t's0, 'd0", tmp, dst) ::
rewrite_program(t, to_spill)
end
else
MOVE(s,src,dst) :: rewrite_program(t, to_spill)
end
| JUMP(s)::t -> (JUMP s) :: rewrite_program(t, to_spill)
| LABEL(s)::t -> (LABEL s) :: rewrite_program(t, to_spill)
| COMMENT(s)::t -> (COMMENT s) :: rewrite_program(t, to_spill)
end
in
begin
if (!E.debug) then print_instrlist !curprog;
let to_spill = ref [-1] in
let interflist: regalloc_t list list = get_live_in curprog !maxtemp in
if (!E.debug) then print_instrlist !curprog;
if (!E.debug) then print_live_in interflist;
chaitin_init true mygraph (interflist, numregs, !maxtemp, curprog);
while (!to_spill <> []) do
let interflist = get_live_in curprog !maxtemp in
chaitin_init false mygraph (interflist, numregs, !maxtemp, curprog);
to_spill := chaitin_iter(mygraph, numregs);
if (!E.debug) then print_igraph mygraph;
List.iter (fun to_spill ->
let newslot = get_new_stackslot() in
ignore(E.debugf "Spilling temp %d to slot %d..." to_spill newslot);
Hashtbl.replace (snd !mygraph) (TEMP to_spill)
(true, (I_STACKSLOT newslot), []);
curprog := rewrite_program(!curprog, TEMP to_spill);
ignore(E.debugf " done.\n")
) !to_spill;
if (!E.debug) then print_instrlist !curprog;
ignore(E.debugf "\n--------------------------\n")
done;
(*
This last part is just a bit of extra credit. It offends
my sense of elegance to leave in all those extraneous |MOVE|
instructions, so let's get rid of them.
*)
let alloc_fn = chaitin_final mygraph in
curprog := trim_extra_moves alloc_fn !curprog;
(!curprog, !maxslot, alloc_fn)
end