10 #include "iredges_t.h"
13 #include "bespilloptions.h"
21 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
23 typedef struct daemel_env_t daemel_env_t;
25 spill_env_t *spill_env;
27 const arch_env_t *arch_env;
28 const arch_register_class_t *cls;
30 bitset_t *spilled_nodes;
33 typedef struct spill_candidate_t spill_candidate_t;
34 struct spill_candidate_t {
40 int compare_spill_candidates_desc(const void *d1, const void *d2)
42 const spill_candidate_t *c1 = d1;
43 const spill_candidate_t *c2 = d2;
45 return (int) (c2->costs - c1->costs);
49 double get_spill_costs(daemel_env_t *env, ir_node *node)
51 const ir_edge_t *edge;
52 spill_env_t *spill_env = env->spill_env;
53 double costs = be_get_spill_costs(spill_env, node, node);
55 foreach_out_edge(node, edge) {
56 ir_node *use = get_edge_src_irn(edge);
59 int in = get_edge_src_pos(edge);
60 ir_node *block = get_nodes_block(use);
62 costs += be_get_reload_costs_on_edge(spill_env, node, block, in);
64 costs += be_get_reload_costs(spill_env, node, use);
72 * spills a node by placing a reload before each usage
75 void spill_node(daemel_env_t *env, ir_node *node)
77 const ir_edge_t *edge;
78 spill_env_t *spill_env = env->spill_env;
79 const arch_register_class_t *cls = env->cls;
81 foreach_out_edge(node, edge) {
82 ir_node *use = get_edge_src_irn(edge);
85 int in = get_edge_src_pos(edge);
86 ir_node *block = get_nodes_block(use);
88 be_add_reload_on_edge(spill_env, node, block, in, cls, 1);
90 be_add_reload(spill_env, node, use, cls, 1);
94 bitset_set(env->spilled_nodes, get_irn_idx(node));
98 * spill @p n nodes from a nodeset. Removes the nodes from the nodeset and
99 * sets the spilled bits in env->spilled_nodes.
102 void spill_nodes(daemel_env_t *env, ir_nodeset_t *nodes, ir_node *spill_phis_in)
104 size_t node_count = ir_nodeset_size(nodes);
105 int registers = env->n_regs;
106 spill_candidate_t *candidates;
107 ir_nodeset_iterator_t iter;
110 int spills_needed = node_count - registers;
112 if(spills_needed <= 0)
115 candidates = malloc(node_count * sizeof(candidates[0]));
117 /* construct array with spill candidates and calculate their costs */
119 foreach_ir_nodeset(nodes, node, iter) {
120 spill_candidate_t *candidate = & candidates[i];
122 candidate->node = node;
123 candidate->costs = get_spill_costs(env, node);
126 assert(i == node_count);
128 /* sort spill candidates */
129 qsort(candidates, node_count, sizeof(candidates[0]),
130 compare_spill_candidates_desc);
132 /* spill cheapest ones */
133 DBG((dbg, LEVEL_2, "\tspills needed: %d\n", spills_needed));
134 for(i = registers; i < node_count; ++i) {
135 spill_candidate_t *candidate = &candidates[i];
136 ir_node *node = candidate->node;
138 DBG((dbg, LEVEL_3, "\tspilling %+F (costs %f)\n",
139 node, candidate->costs));
141 spill_node(env, node);
142 if(spill_phis_in != NULL && is_Phi(node) &&
143 get_nodes_block(node) == spill_phis_in) {
144 be_spill_phi(env->spill_env, node);
152 * make sure register pressure in a block is always equal or below the number
153 * of available registers
156 void spill_block(ir_node *block, void *data)
158 daemel_env_t *env = data;
159 const arch_env_t *arch_env = env->arch_env;
160 const arch_register_class_t *cls = env->cls;
161 const be_lv_t *lv = env->lv;
162 ir_nodeset_t live_nodes;
163 ir_nodeset_iterator_t iter;
165 bitset_t *spilled_nodes = env->spilled_nodes;
167 DBG((dbg, LEVEL_1, "spilling block %+F\n", block));
169 ir_nodeset_init(&live_nodes);
170 be_liveness_end_of_block_ir_nodeset(lv, arch_env, cls, block, &live_nodes);
172 foreach_ir_nodeset(&live_nodes, node, iter) {
173 DBG((dbg, LEVEL_2, "\t%+F is live-in... ", node));
174 if(bitset_is_set(spilled_nodes, get_irn_idx(node))) {
175 DBG((dbg, LEVEL_2, "but spilled; removing.\n"));
177 DBG((dbg, LEVEL_2, "keeping.\n"));
181 sched_foreach_reverse(block, node) {
185 be_liveness_transfer_ir_nodeset(arch_env, cls, node, &live_nodes);
186 /* TODO: do custom liveness transfer and don't add already spilled
189 spill_nodes(env, &live_nodes, NULL);
192 spill_nodes(env, &live_nodes, block);
194 ir_nodeset_destroy(&live_nodes);
197 void be_spill_daemel(be_irg_t *birg, const arch_register_class_t *cls)
200 ir_graph *irg = be_get_birg_irg(birg);
201 int n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
206 be_invalidate_liveness(birg);
207 be_assure_liveness(birg);
209 env.spill_env = be_new_spill_env(birg);
211 env.arch_env = be_get_birg_arch_env(birg);
213 env.lv = be_get_birg_liveness(birg);
214 env.spilled_nodes = bitset_malloc(get_irg_last_idx(irg));
216 irg_block_walk_graph(irg, spill_block, NULL, &env);
218 bitset_free(env.spilled_nodes);
220 be_insert_spills_reloads(env.spill_env);
222 be_delete_spill_env(env.spill_env);
225 void be_init_daemelspill(void)
227 static be_spiller_t daemel_spiller = {
231 be_register_spiller("daemel", &daemel_spiller);
232 FIRM_DBG_REGISTER(dbg, "ir.be.spilldaemel");
235 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_doedelspill);