2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Linear Scan Spill algorithm
23 * @author Matthias Braun
33 #include "iredges_t.h"
36 #include "besched_t.h"
37 #include "bespilloptions.h"
43 /* a place in the program */
44 typedef struct place_t {
49 typedef struct interval_t {
56 static interval_t **intervals;
58 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
60 static struct obstack obst;
61 static const arch_env_t *arch_env;
62 static const arch_register_class_t *cls;
63 static spill_env_t *spill_env;
64 static unsigned n_regs;
65 static const be_lv_t *lv;
67 static double get_spill_costs(ir_node *node)
69 const ir_edge_t *edge;
70 ir_node *spill_place = skip_Proj(node);
71 double costs = be_get_spill_costs(spill_env, node,
73 foreach_out_edge(node, edge) {
74 ir_node *use = get_edge_src_irn(edge);
76 /* keeps should be directly below the node */
82 int in = get_edge_src_pos(edge);
83 ir_node *block = get_nodes_block(use);
85 costs += be_get_reload_costs_on_edge(spill_env, node, block, in);
87 costs += be_get_reload_costs(spill_env, node, use);
95 * spills a node by placing a reload before each usage
97 static void spill_node(ir_node *node)
99 const ir_edge_t *edge;
101 DBG((dbg, LEVEL_3, "\tspilling %+F\n", node));
103 foreach_out_edge(node, edge) {
104 ir_node *use = get_edge_src_irn(edge);
111 int in = get_edge_src_pos(edge);
112 ir_node *block = get_nodes_block(use);
114 be_add_reload_on_edge(spill_env, node, block, in, cls, 1);
116 be_add_reload(spill_env, node, use, cls, 1);
122 static int place_less(const place_t *place1, const place_t *place2)
124 if(place1->block_nr < place2->block_nr)
126 if(place1->block_nr > place2->block_nr)
129 return place1->timestep < place2->timestep;
132 static int place_equal(const place_t *place1, const place_t *place2)
134 return place1->block_nr == place2->block_nr
135 && place1->timestep == place2->timestep;
138 static void extend_interval(ir_node *value, const place_t *place)
140 interval_t *interval;
142 if(!irn_visited(value)) {
143 interval = obstack_alloc(&obst, sizeof(interval[0]));
144 interval->begin = *place;
145 interval->end = *place;
146 interval->value = value;
147 interval->spill_costs = 0;
149 ARR_APP1(interval_t*, intervals, interval);
151 set_irn_link(value, interval);
152 mark_irn_visited(value);
154 interval = get_irn_link(value);
156 if(place_less(place, &interval->begin)) {
157 interval->begin = *place;
159 if(place_less(&interval->end, place)) {
160 interval->end = *place;
166 * link live intervals to values, put all intervals into a list,
167 * sort the list. We process the blocks in a toplogical order (by ignoring
170 static void calculate_liveness_intervals(ir_node *block, unsigned block_nr)
176 set_irn_link(block, INT_TO_PTR(block_nr));
178 place.block_nr = block_nr;
181 be_lv_foreach(lv, block, be_lv_state_in, i) {
182 ir_node *node = be_lv_get_irn(lv, block, i);
183 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node))
186 extend_interval(node, &place);
189 sched_foreach_reverse(block, node) {
194 place.timestep = sched_get_time_step(node);
196 if(get_irn_mode(node) == mode_T) {
197 const ir_edge_t *edge;
199 foreach_out_edge(node, edge) {
200 ir_node *proj = get_edge_src_irn(edge);
201 if(arch_irn_consider_in_reg_alloc(arch_env, cls, proj)) {
202 extend_interval(proj, &place);
205 } else if(arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
206 extend_interval(node, &place);
209 arity = get_irn_arity(node);
210 for(i = 0; i < arity; ++i) {
211 ir_node *op = get_irn_n(node, i);
213 if(arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
214 extend_interval(op, &place);
220 be_lv_foreach(lv, block, be_lv_state_end, i) {
221 ir_node *node = be_lv_get_irn(lv, block, i);
222 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node))
225 extend_interval(node, &place);
228 ir_printf("processing block %+F(%u)\n", block, block_nr);
231 static unsigned next_block_nr;
234 * process blocks in a toplogical order (we ignore backedges and create a
235 * topological order from the remaining edges)
237 static void process_block(ir_node *block)
243 if(irn_visited(block))
245 mark_irn_visited(block);
247 n_preds = get_Block_n_cfgpreds(block);
248 for(i = 0; i < n_preds; ++i) {
251 if(is_backedge(block, i))
254 pred_block = get_Block_cfgpred_block(block, i);
255 process_block(pred_block);
258 block_nr = next_block_nr;
260 calculate_liveness_intervals(block, block_nr);
263 static void print_interval(const interval_t *interval)
265 ir_fprintf(stderr, "%+F [%u,%d] -> [%u,%d]\n", interval->value,
266 interval->begin.block_nr, interval->begin.timestep,
267 interval->end.block_nr, interval->end.timestep);
270 static int compare_spill_costs(const void *d1, const void *d2)
272 const interval_t *interval1 = *((const interval_t**)d1);
273 const interval_t *interval2 = *((const interval_t**)d2);
274 if (interval2->spill_costs < interval1->spill_costs)
279 static void do_spilling(void)
281 interval_t **live_intervals;
282 unsigned n_live_intervals;
283 interval_t **intervals_to_allocate;
284 unsigned n_intervals_to_allocate;
288 live_intervals = alloca(n_regs * sizeof(live_intervals[0]));
289 n_live_intervals = 0;
290 intervals_to_allocate = alloca(n_regs * sizeof(intervals_to_allocate[0]));
292 len = ARR_LEN(intervals);
293 for (i = 0; i < len; ) {
294 const place_t place = intervals[i]->begin;
297 n_intervals_to_allocate = 0;
299 interval_t *interval = intervals[i];
301 print_interval(interval);
303 intervals_to_allocate[n_intervals_to_allocate] = intervals[i];
304 ++n_intervals_to_allocate;
306 } while (i < len && place_equal(&intervals[i]->begin, &place));
308 spills_needed = n_live_intervals + n_intervals_to_allocate - n_regs;
310 /* first expire intervals whose endpoint is above our current place */
311 if (spills_needed > 0) {
314 for (a = 0; a < n_live_intervals; ) {
315 interval_t *live_interval = live_intervals[a];
316 if(place_less(&place, &live_interval->end)) {
319 fprintf(stderr, "expired: ");
320 print_interval(live_interval);
321 live_intervals[a] = live_intervals[n_live_intervals-1];
326 spills_needed = n_live_intervals + n_intervals_to_allocate - n_regs;
328 /* spill intervals */
329 if (spills_needed > 0) {
330 ir_fprintf(stderr, "need to spill %d values at %u,%d\n",
331 spills_needed, place.block_nr, place.timestep);
333 for(a = 0; a < n_live_intervals; ++a) {
334 interval_t *live_interval = live_intervals[a];
335 if(live_interval->spill_costs == 0) {
336 ir_node *value = live_interval->value;
337 live_interval->spill_costs = get_spill_costs(value);
338 ir_fprintf(stderr, "spillcosts for %+F: %f\n", value,
339 live_interval->spill_costs);
343 qsort(live_intervals, n_live_intervals, sizeof(live_intervals[0]),
344 compare_spill_costs);
346 a = n_live_intervals - spills_needed;
347 for ( ; a < n_live_intervals; ++a) {
348 const interval_t *live_interval = live_intervals[a];
349 ir_node *value = live_interval->value;
351 ir_fprintf(stderr, "spilling %+F (%f)\n", value, live_interval->spill_costs);
354 n_live_intervals -= spills_needed;
357 assert(n_regs - n_live_intervals >= n_intervals_to_allocate);
359 for (a = 0; a < n_intervals_to_allocate; ++a) {
360 live_intervals[n_live_intervals] = intervals_to_allocate[a];
363 assert(n_live_intervals <= n_regs);
367 static int cmp_interval(const void *d1, const void *d2)
369 const interval_t *interval1 = *((const interval_t**) d1);
370 const interval_t *interval2 = *((const interval_t**) d2);
372 return !place_less(&interval1->begin, &interval2->begin);
375 static void be_spill_linearscan(be_irg_t *birg,
376 const arch_register_class_t *new_cls)
380 ir_graph *irg = be_get_birg_irg(birg);
382 be_liveness_assure_sets(be_assure_liveness(birg));
384 arch_env = be_get_birg_arch_env(birg);
386 intervals = NEW_ARR_F(interval_t*, 0);
387 spill_env = be_new_spill_env(birg);
388 lv = be_get_birg_liveness(birg);
389 n_regs = cls->n_regs - be_put_ignore_regs(birg, new_cls, NULL);
393 set_using_visited(irg);
394 set_using_irn_link(irg);
395 inc_irg_visited(irg);
399 /* use toposort for liveness analysis */
400 end_block = get_irg_end_block(irg);
401 process_block(end_block);
403 assert(irn_visited(get_irg_start_block(irg)));
405 n_intervals = ARR_LEN(intervals);
406 qsort(intervals, n_intervals, sizeof(intervals[0]), cmp_interval);
410 clear_using_visited(irg);
411 clear_using_irn_link(irg);
413 DEL_ARR_F(intervals);
414 obstack_free(&obst, NULL);
416 /* Insert spill/reload nodes into the graph and fix usages */
417 be_insert_spills_reloads(spill_env);
419 be_delete_spill_env(spill_env);
423 void be_init_spilllinearscan(void)
425 static be_spiller_t spiller = {
429 be_register_spiller("linearscan", &spiller);
430 FIRM_DBG_REGISTER(dbg, "firm.be.spill.linearscan");
433 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spilllinearscan);