nsz Git - libfirm/blob - ir/be/bespilllinearscan.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Linear Scan Spill algorithm
  23  * @author      Matthias Braun
  24  * @date        20.09.2005
  25  * @version     $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include "irnode_t.h"
  32 #include "irprintf.h"
  33 #include "iredges_t.h"
  34
  35 #include "bemodule.h"
  36 #include "besched_t.h"
  37 #include "bespilloptions.h"
  38 #include "bespill.h"
  39 #include "benode_t.h"
  40 #include "be_t.h"
  41 #include "belive_t.h"
  42
  43 /* a place in the program */
  44 typedef struct place_t {
  45         unsigned  block_nr;
  46         int       timestep;
  47 } place_t;
  48
  49 typedef struct interval_t {
  50         ir_node *value;
  51         double   spill_costs;
  52         place_t  begin;
  53         place_t  end;
  54 } interval_t;
  55
  56 static interval_t **intervals;
  57
  58 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  59
  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;
  66
  67 static double get_spill_costs(ir_node *node)
  68 {
  69         const ir_edge_t *edge;
  70         ir_node         *spill_place = skip_Proj(node);
  71         double           costs       = be_get_spill_costs(spill_env, node,
  72                                                           spill_place);
  73         foreach_out_edge(node, edge) {
  74                 ir_node *use = get_edge_src_irn(edge);
  75
  76                 /* keeps should be directly below the node */
  77                 if(be_is_Keep(use)) {
  78                         continue;
  79                 }
  80
  81                 if(is_Phi(use)) {
  82                         int      in         = get_edge_src_pos(edge);
  83                         ir_node *block      = get_nodes_block(use);
  84
  85                         costs += be_get_reload_costs_on_edge(spill_env, node, block, in);
  86                 } else {
  87                         costs += be_get_reload_costs(spill_env, node, use);
  88                 }
  89         }
  90
  91         return costs;
  92 }
  93
  94 /**
  95  * spills a node by placing a reload before each usage
  96  */
  97 static void spill_node(ir_node *node)
  98 {
  99         const ir_edge_t *edge;
 100
 101         DBG((dbg, LEVEL_3, "\tspilling %+F\n", node));
 102
 103         foreach_out_edge(node, edge) {
 104                 ir_node *use = get_edge_src_irn(edge);
 105                 if(is_Anchor(use))
 106                         continue;
 107                 if(be_is_Keep(use))
 108                         continue;
 109
 110                 if(is_Phi(use)) {
 111                         int      in         = get_edge_src_pos(edge);
 112                         ir_node *block      = get_nodes_block(use);
 113
 114                         be_add_reload_on_edge(spill_env, node, block, in, cls, 1);
 115                 } else {
 116                         be_add_reload(spill_env, node, use, cls, 1);
 117                 }
 118         }
 119 }
 120
 121
 122 static int place_less(const place_t *place1, const place_t *place2)
 123 {
 124         if(place1->block_nr < place2->block_nr)
 125                 return 1;
 126         if(place1->block_nr > place2->block_nr)
 127                 return 0;
 128
 129         return place1->timestep < place2->timestep;
 130 }
 131
 132 static int place_equal(const place_t *place1, const place_t *place2)
 133 {
 134         return place1->block_nr == place2->block_nr
 135                 && place1->timestep == place2->timestep;
 136 }
 137
 138 static void extend_interval(ir_node *value, const place_t *place)
 139 {
 140         interval_t *interval;
 141
 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;
 148
 149                 ARR_APP1(interval_t*, intervals, interval);
 150
 151                 set_irn_link(value, interval);
 152                 mark_irn_visited(value);
 153         } else {
 154                 interval = get_irn_link(value);
 155
 156                 if(place_less(place, &interval->begin)) {
 157                         interval->begin = *place;
 158                 }
 159                 if(place_less(&interval->end, place)) {
 160                         interval->end = *place;
 161                 }
 162         }
 163 }
 164
 165 /**
 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
 168  * backedges).
 169  */
 170 static void calculate_liveness_intervals(ir_node *block, unsigned block_nr)
 171 {
 172         ir_node *node;
 173         int      i, arity;
 174         place_t  place;
 175
 176         set_irn_link(block, INT_TO_PTR(block_nr));
 177
 178         place.block_nr = block_nr;
 179         place.timestep = 0;
 180
 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))
 184                         continue;
 185
 186                 extend_interval(node, &place);
 187         }
 188
 189         sched_foreach_reverse(block, node) {
 190
 191                 if(is_Phi(node))
 192                         break;
 193
 194                 place.timestep = sched_get_time_step(node);
 195
 196                 if(get_irn_mode(node) == mode_T) {
 197                         const ir_edge_t *edge;
 198
 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);
 203                                 }
 204                         }
 205                 } else if(arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
 206                         extend_interval(node, &place);
 207                 }
 208
 209                 arity = get_irn_arity(node);
 210                 for(i = 0; i < arity; ++i) {
 211                         ir_node *op = get_irn_n(node, i);
 212
 213                         if(arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 214                                 extend_interval(op, &place);
 215                         }
 216                 }
 217         }
 218
 219         place.timestep++;
 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))
 223                         continue;
 224
 225                 extend_interval(node, &place);
 226         }
 227
 228         ir_printf("processing block %+F(%u)\n", block, block_nr);
 229 }
 230
 231 static unsigned next_block_nr;
 232
 233 /**
 234  * process blocks in a toplogical order (we ignore backedges and create a
 235  * topological order from the remaining edges)
 236  */
 237 static void process_block(ir_node *block)
 238 {
 239         unsigned block_nr;
 240         int      n_preds;
 241         int      i;
 242
 243         if(irn_visited(block))
 244                 return;
 245         mark_irn_visited(block);
 246
 247         n_preds = get_Block_n_cfgpreds(block);
 248         for(i = 0; i < n_preds; ++i) {
 249                 ir_node *pred_block;
 250
 251                 if(is_backedge(block, i))
 252                         continue;
 253
 254                 pred_block = get_Block_cfgpred_block(block, i);
 255                 process_block(pred_block);
 256         }
 257
 258         block_nr = next_block_nr;
 259         next_block_nr++;
 260         calculate_liveness_intervals(block, block_nr);
 261 }
 262
 263 static void print_interval(const interval_t *interval)
 264 {
 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);
 268 }
 269
 270 static int compare_spill_costs(const void *d1, const void *d2)
 271 {
 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)
 275                 return -1;
 276         return 1;
 277 }
 278
 279 static void do_spilling(void)
 280 {
 281         interval_t **live_intervals;
 282         unsigned   n_live_intervals;
 283         interval_t **intervals_to_allocate;
 284         unsigned   n_intervals_to_allocate;
 285         int        i, len;
 286         unsigned   a;
 287
 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]));
 291
 292         len = ARR_LEN(intervals);
 293         for (i = 0; i < len; ) {
 294                 const place_t place = intervals[i]->begin;
 295                 int           spills_needed;
 296
 297                 n_intervals_to_allocate = 0;
 298                 do {
 299                         interval_t *interval = intervals[i];
 300
 301                         print_interval(interval);
 302
 303                         intervals_to_allocate[n_intervals_to_allocate] = intervals[i];
 304                         ++n_intervals_to_allocate;
 305                         ++i;
 306                 } while (i < len && place_equal(&intervals[i]->begin, &place));
 307
 308                 spills_needed = n_live_intervals + n_intervals_to_allocate - n_regs;
 309
 310                 /* first expire intervals whose endpoint is above our current place */
 311                 if (spills_needed > 0) {
 312                         unsigned a;
 313
 314                         for (a = 0; a < n_live_intervals; ) {
 315                                 interval_t *live_interval = live_intervals[a];
 316                                 if(place_less(&place, &live_interval->end)) {
 317                                         ++a;
 318                                 } else {
 319                                         fprintf(stderr, "expired: ");
 320                                         print_interval(live_interval);
 321                                         live_intervals[a] = live_intervals[n_live_intervals-1];
 322                                         --n_live_intervals;
 323                                 }
 324                         }
 325
 326                         spills_needed = n_live_intervals + n_intervals_to_allocate - n_regs;
 327                 }
 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);
 332
 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);
 340                                 }
 341                         }
 342
 343                         qsort(live_intervals, n_live_intervals, sizeof(live_intervals[0]),
 344                               compare_spill_costs);
 345
 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;
 350
 351                                 ir_fprintf(stderr, "spilling %+F (%f)\n", value, live_interval->spill_costs);
 352                                 spill_node(value);
 353                         }
 354                         n_live_intervals -= spills_needed;
 355                 }
 356
 357                 assert(n_regs - n_live_intervals >= n_intervals_to_allocate);
 358
 359                 for (a = 0; a < n_intervals_to_allocate; ++a) {
 360                         live_intervals[n_live_intervals] = intervals_to_allocate[a];
 361                         ++n_live_intervals;
 362                 }
 363                 assert(n_live_intervals <= n_regs);
 364         }
 365 }
 366
 367 static int cmp_interval(const void *d1, const void *d2)
 368 {
 369         const interval_t *interval1 = *((const interval_t**) d1);
 370         const interval_t *interval2 = *((const interval_t**) d2);
 371
 372         return !place_less(&interval1->begin, &interval2->begin);
 373 }
 374
 375 static void be_spill_linearscan(be_irg_t *birg,
 376                                 const arch_register_class_t *new_cls)
 377 {
 378         size_t    n_intervals;
 379         ir_node  *end_block;
 380         ir_graph *irg = be_get_birg_irg(birg);
 381
 382         be_liveness_assure_sets(be_assure_liveness(birg));
 383
 384         arch_env  = be_get_birg_arch_env(birg);
 385         cls       = new_cls;
 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);
 390
 391         obstack_init(&obst);
 392
 393         set_using_irn_visited(irg);
 394         set_using_irn_link(irg);
 395         inc_irg_visited(irg);
 396
 397         next_block_nr = 0;
 398
 399         /* use toposort for liveness analysis */
 400         end_block = get_irg_end_block(irg);
 401         process_block(end_block);
 402
 403         assert(irn_visited(get_irg_start_block(irg)));
 404
 405         n_intervals = ARR_LEN(intervals);
 406         qsort(intervals, n_intervals, sizeof(intervals[0]), cmp_interval);
 407
 408         do_spilling();
 409
 410         clear_using_irn_visited(irg);
 411         clear_using_irn_link(irg);
 412
 413         DEL_ARR_F(intervals);
 414         obstack_free(&obst, NULL);
 415
 416         /* Insert spill/reload nodes into the graph and fix usages */
 417         be_insert_spills_reloads(spill_env);
 418
 419         be_delete_spill_env(spill_env);
 420         spill_env = NULL;
 421 }
 422
 423 void be_init_spilllinearscan(void)
 424 {
 425         static be_spiller_t spiller = {
 426                 be_spill_linearscan
 427         };
 428
 429         be_register_spiller("linearscan", &spiller);
 430         FIRM_DBG_REGISTER(dbg, "firm.be.spill.linearscan");
 431 }
 432
 433 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spilllinearscan);