## 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 pp = standard_prettyprinter; # standard_prettyprinter is from src/lib/prettyprint/big/src/standard-prettyprinter.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_Pp # Machcode_Codebuffer_Pp is from src/lib/compiler/back/low/emit/machcode-codebuffer-pp.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 package 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;
# 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 = (\\ 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 (\\ register = enter_spill (rkj::interkind_register_id_of register, TRUE));
get_spills = cig::ppt_hashtable::find spill_set;
get_spills = \\ p = case (get_spills p)
THE s => s;
NULL => [];
esac;
get_reloads = cig::ppt_hashtable::find reload_set;
get_reloads = \\ p = case (get_reloads p)
#
THE s => s;
NULL => [];
esac;
get_kills = cig::ppt_hashtable::find kill_set;
get_kills = \\ 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
(\\ 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
(\\ (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:";
print (pp::prettyprint_to_string [] {.
buf = ae::make_codebuffer #pp [];
buf.put_op op;
});
pr_dictionary dictionary;
fi;
(reload_all (pt, ops, dictionary, reload_regs))
->
(ops, dictionary);
if debug
#
print "After:";
print (pp::prettyprint_to_string [] {.
buf = ae::make_codebuffer #pp [];
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-2015,
## released per terms of SMLNJ-COPYRIGHT.