## register-spilling-per-chaitin-heuristic.pkg
#
# This module implements the Chaitin heuristic (but weighted by priorities).
#
# This is the register spill heuristic used on RISC machines -- see
# src/lib/compiler/back/low/main/pwrpc32/backend-lowhalf-pwrpc32.pkg# src/lib/compiler/back/low/main/sparc32/backend-lowhalf-sparc32.pkg#
# See also:
# src/lib/compiler/back/low/regor/register-spilling-per-chow-hennessy-heuristic.pkg# src/lib/compiler/back/low/regor/register-spilling-per-improved-chaitin-heuristic-g.pkg# src/lib/compiler/back/low/regor/register-spilling-per-improved-chow-hennessy-heuristic-g.pkg# Compiled by:
# src/lib/compiler/back/low/lib/lowhalf.libstipulate
package cig = codetemp_interference_graph; # codetemp_interference_graph is from src/lib/compiler/back/low/regor/codetemp-interference-graph.pkgherein
package register_spilling_per_chaitin_heuristic
: (weak) Register_Spilling_Per_Xxx_Heuristic # Register_Spilling_Per_Xxx_Heuristic is from src/lib/compiler/back/low/regor/register-spilling-per-xxx-heuristic.api {
exception NO_CANDIDATE;
mode = iterated_register_coalescing::no_optimization;
fun init () = ();
# Potential spill phase.
# Find a cheap node to spill according to Chaitin's heuristic.
#
fun choose_spill_node
{
codetemp_interference_graph,
has_been_spilled,
spill_worklist
}
=
{ fun chase (cig::NODE { color=>REF (cig::ALIASED n), ... }) => chase n; # Find out what an ALIASED chain actually points to.
chase n => n;
end;
infinite_cost = 123456789.0;
don't_use = 223456789.0;
# The spill worklist is maintained only lazily. So we have
# to prune away those nodes that are already removed from the
# interference graph. After pruning the spillWkl,
# it may be the case that there aren't anything to be
# spilled after all.
# Choose node with the lowest cost
# and the maximal degree:
#
fun chaitin ([], best, lowest_cost, spill_worklist)
=>
(best, lowest_cost, spill_worklist);
chaitin (node ! rest, best, lowest_cost, spill_worklist)
=>
case (chase node)
#
node as
cig::NODE { id, priority, defs, uses, degree=>REF deg, color=>REF cig::CODETEMP, ... }
=>
{ fun cost () = *priority / float deg;
#
cost = case (*defs, *uses)
(_,[]) => -1.0 - float deg; # Defs but no use
([d],[u]) # Defs after use; don't use.
=>
{ fun plus ({ block, op }, n)
=
{ block, op => op + n };
(d == plus (u, 1) or d == plus (u, 2))
?? don't_use
:: cost ();
};
_ => cost();
esac;
if (cost < lowest_cost
and not (has_been_spilled id))
#
case best
NULL => chaitin (rest, THE node, cost, spill_worklist);
THE best => chaitin (rest, THE node, cost, best ! spill_worklist);
esac;
else
chaitin (rest, best, lowest_cost, node ! spill_worklist);
fi;
};
_ => chaitin (rest, best, lowest_cost, spill_worklist); # Discard node.
esac;
end; # fun chaitin
# print("["$int::to_string (length spillWkl)$"]")
(chaitin (spill_worklist, NULL, infinite_cost, []))
->
(potential_spill_node, cost, new_spill_worklist);
case (potential_spill_node, new_spill_worklist)
#
(THE node, spill_worklist) => { node => THE node, cost, spill_worklist };
(NULL, []) => { node => NULL, cost, spill_worklist => [] };
#
(NULL, _) => raise exception NO_CANDIDATE;
esac;
}; # fun choose_spill_node
}; # package register_spilling_per_chaitin_heuristic
end;