nsz Git - libfirm/blob - ir/be/bespillbelady3.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       MIN-algorithm with some twists (aka belady spiller v3)
  23  * @author      Matthias Braun
  24  * @date        15.01.2008
  25  * @version     $Id$
  26  *
  27  * TODO:
  28  *   - handle phis correctly, decide wether we should spill them
  29  *   - merge multiple start worksets of blocks
  30  *   - how to and when to do the tentative phase...
  31  */
  32 #ifdef HAVE_CONFIG_H
  33 #include "config.h"
  34 #endif
  35
  36 #include "debug.h"
  37 #include "list.h"
  38 #include "pdeq.h"
  39
  40 #include "irnode_t.h"
  41 #include "irprintf.h"
  42 #include "iredges_t.h"
  43 #include "execfreq.h"
  44
  45 #include "bemodule.h"
  46 #include "bespill.h"
  47 #include "beutil.h"
  48 #include "bespilloptions.h"
  49 #include "besched_t.h"
  50 #include "be_t.h"
  51
  52 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  53
  54 typedef struct worklist_entry_t worklist_entry_t;
  55 struct worklist_entry_t {
  56         struct list_head  head;
  57         ir_node          *value;
  58         unsigned          timestep;
  59         ir_node          *reload_point;
  60 };
  61
  62 typedef struct worklist_t worklist_t;
  63 struct worklist_t {
  64         struct list_head  live_values;
  65         size_t            n_live_values;
  66         unsigned          current_timestep;
  67 };
  68
  69 static const arch_env_t            *arch_env;
  70 static const arch_register_class_t *cls;
  71 static struct obstack               obst;
  72 static spill_env_t                 *senv;
  73 static size_t                       n_regs;
  74 static int                          tentative_mode;
  75 static ir_exec_freq                *exec_freq;
  76
  77 static void init_worklist(worklist_t *worklist, unsigned timestep)
  78 {
  79         INIT_LIST_HEAD(&worklist->live_values);
  80         worklist->n_live_values    = 0;
  81         worklist->current_timestep = timestep;
  82 }
  83
  84 static void mark_irn_not_visited(ir_node *node)
  85 {
  86         set_irn_visited(node, get_irg_visited(current_ir_graph) - 1);
  87 }
  88
  89 static void deactivate_worklist(const worklist_t *worklist)
  90 {
  91         struct list_head *entry;
  92
  93         list_for_each(entry, &worklist->live_values) {
  94                 worklist_entry_t *wl_entry
  95                         = list_entry(entry, worklist_entry_t, head);
  96                 assert(irn_visited(wl_entry->value));
  97                 mark_irn_not_visited(wl_entry->value);
  98                 set_irn_link(wl_entry->value, NULL);
  99         }
 100 }
 101
 102 static void activate_worklist(const worklist_t *worklist)
 103 {
 104         struct list_head *entry;
 105
 106         list_for_each(entry, &worklist->live_values) {
 107                 worklist_entry_t *wl_entry
 108                         = list_entry(entry, worklist_entry_t, head);
 109                 ir_node          *value = wl_entry->value;
 110
 111                 assert(irn_not_visited(value));
 112                 mark_irn_visited(value);
 113                 set_irn_link(value, wl_entry);
 114         }
 115 }
 116
 117 static worklist_t *duplicate_worklist(const worklist_t *worklist,
 118                                       ir_node *block,
 119                                       ir_node *succ_block, int succ_pos)
 120 {
 121         ir_node          *reload_point = NULL;
 122         struct list_head *entry;
 123         worklist_t       *new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0]));
 124
 125         INIT_LIST_HEAD(&new_worklist->live_values);
 126
 127         if(succ_block != NULL && get_Block_n_cfgpreds(succ_block) > 1) {
 128                 reload_point = be_get_end_of_block_insertion_point(block);
 129         }
 130
 131         new_worklist->current_timestep = worklist->current_timestep;
 132         new_worklist->n_live_values    = worklist->n_live_values;
 133
 134         list_for_each(entry, &worklist->live_values) {
 135                 worklist_entry_t *wl_entry
 136                         = list_entry(entry, worklist_entry_t, head);
 137                 worklist_entry_t *new_entry
 138                         = obstack_alloc(&obst, sizeof(new_entry[0]));
 139                 ir_node          *value = wl_entry->value;
 140
 141                 if(is_Phi(value) && get_nodes_block(value) == succ_block) {
 142                         value = get_Phi_pred(value, succ_pos);
 143                 }
 144
 145                 new_entry->value        = value;
 146                 new_entry->timestep     = wl_entry->timestep;
 147                 if(reload_point != NULL) {
 148                         new_entry->reload_point = reload_point;
 149                 } else {
 150                         new_entry->reload_point = wl_entry->reload_point;
 151                 }
 152
 153                 list_add_tail(&new_entry->head, &new_worklist->live_values);
 154         }
 155
 156         return new_worklist;
 157 }
 158
 159 #ifdef DEBUG_libfirm
 160 static void print_worklist(const worklist_t *worklist, int level)
 161 {
 162         struct list_head *entry;
 163
 164         DB((dbg, level, "%d values (TS %u): ", worklist->n_live_values,
 165             worklist->current_timestep));
 166         list_for_each(entry, &worklist->live_values) {
 167                 worklist_entry_t *wl_entry
 168                         = list_entry(entry, worklist_entry_t, head);
 169
 170                 //DB((dbg, level, "%+F(%+F) ", wl_entry->value,
 171                 //    wl_entry->reload_point));
 172                 DB((dbg, level, "%+F ", wl_entry->value));
 173         }
 174 }
 175 #endif
 176
 177 static void place_reload(worklist_entry_t *entry)
 178 {
 179         if(tentative_mode)
 180                 return;
 181         DB((dbg, LEVEL_1, "reload of %+F before %+F", entry->value,
 182             entry->reload_point));
 183         be_add_reload(senv, entry->value, entry->reload_point, cls, 1);
 184 }
 185
 186 static void spill_non_live_nodes(const worklist_t *worklist)
 187 {
 188         struct list_head *entry;
 189
 190         list_for_each(entry, &worklist->live_values) {
 191                 worklist_entry_t *wl_entry
 192                         = list_entry(entry, worklist_entry_t, head);
 193                 ir_node          *value = wl_entry->value;
 194
 195                 if(irn_visited(value))
 196                         continue;
 197
 198                 place_reload(wl_entry);
 199         }
 200 }
 201
 202 /**
 203  * makes sure the worklist contains not more than n_regs - room_needed entries
 204  */
 205 static void make_room(worklist_t *worklist, size_t room_needed)
 206 {
 207         int spills_needed = worklist->n_live_values + room_needed - n_regs;
 208         if(spills_needed > 0) {
 209                 int               i     = spills_needed;
 210                 struct list_head *entry = worklist->live_values.next;
 211                 for(i = spills_needed; i > 0; --i) {
 212                         struct list_head *next = entry->next;
 213                         worklist_entry_t *wl_entry
 214                                 = list_entry(entry, worklist_entry_t, head);
 215                         assert(irn_visited(wl_entry->value));
 216                         mark_irn_not_visited(wl_entry->value);
 217                         place_reload(wl_entry);
 218                         list_del(entry);
 219
 220                         entry = next;
 221                 }
 222                 worklist->n_live_values -= spills_needed;
 223         }
 224 }
 225
 226 /**
 227  * a value was used, so bring it to the back of the worklist (which might
 228  * result in a spill of another value).
 229  */
 230 static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point)
 231 {
 232         /* is the node in the worklist already? */
 233         worklist_entry_t *entry = get_irn_link(value);
 234         if(irn_visited(value)) {
 235                 assert(entry != NULL);
 236
 237                 assert(irn_visited(value));
 238                 list_del(&entry->head);
 239         } else {
 240                 if(entry == NULL) {
 241                         entry        = obstack_alloc(&obst, sizeof(entry[0]));
 242                         entry->value = value;
 243                         set_irn_link(value, entry);
 244                 }
 245
 246                 ++worklist->n_live_values;
 247                 mark_irn_visited(value);
 248         }
 249
 250         entry->timestep     = worklist->current_timestep;
 251         entry->reload_point = sched_point;
 252         list_add_tail(&entry->head, &worklist->live_values);
 253 }
 254
 255 static void worklist_remove(worklist_t *worklist, ir_node *value)
 256 {
 257         worklist_entry_t *entry = get_irn_link(value);
 258         assert(entry != NULL);
 259         list_del(&entry->head);
 260         --worklist->n_live_values;
 261
 262         assert(irn_visited(value));
 263         mark_irn_not_visited(value);
 264 }
 265
 266 static void do_spilling(ir_node *block, worklist_t *worklist)
 267 {
 268         ir_node *node;
 269
 270         assert(worklist != NULL);
 271
 272 #ifdef DEBUG_libfirm
 273         DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
 274         print_worklist(worklist, LEVEL_1);
 275         DB((dbg, LEVEL_1, "\n"));
 276 #endif
 277
 278         sched_foreach_reverse(block, node) {
 279                 int    i, arity;
 280                 size_t n_defs = 0;
 281
 282                 DB((dbg, LEVEL_2, "\t%+F... ", node));
 283
 284                 if(is_Phi(node)) {
 285                         ir_node *node2;
 286                         /* TODO: if we have some free registers, then we could decide to
 287                          * not spill some phis (but not for phis where at least 1 input is
 288                          * themselfes) */
 289
 290                         /* we have to spill all phis that are not live */
 291                         sched_foreach_reverse_from(node, node2) {
 292                                 assert(is_Phi(node2));
 293
 294                                 if(irn_visited(node2))
 295                                         continue;
 296                                 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node2))
 297                                         continue;
 298
 299                                 be_spill_phi(senv, node2);
 300                         }
 301                         break;
 302                 }
 303
 304                 /* remove values defined by this instruction from the workset. Values
 305                  * defined but not in the workset need free registers */
 306                 if(get_irn_mode(node) == mode_T) {
 307                         const ir_edge_t *edge;
 308
 309                         foreach_out_edge(node, edge) {
 310                                 ir_node *proj = get_edge_src_irn(edge);
 311                                 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, proj))
 312                                         continue;
 313                                 if(irn_visited(proj)) {
 314                                         worklist_remove(worklist, proj);
 315                                 } else {
 316                                         ++n_defs;
 317                                 }
 318                         }
 319                 } else if(arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
 320                         if(irn_visited(node)) {
 321                                 worklist_remove(worklist, node);
 322                         } else {
 323                                 n_defs = 1;
 324                         }
 325                 }
 326
 327                 /* make sure we have enough free registers for the spills */
 328                 make_room(worklist, n_defs);
 329
 330                 /* put all values by the instruction into the workset */
 331                 arity = get_irn_arity(node);
 332                 for(i = 0; i < arity; ++i) {
 333                         ir_node *use = get_irn_n(node, i);
 334
 335                         if(!arch_irn_consider_in_reg_alloc(arch_env, cls, use))
 336                                 continue;
 337
 338                         val_used(worklist, use, node);
 339                 }
 340
 341                 /* we might have too many values in the worklist now and need to spill
 342                  * some */
 343                 make_room(worklist, 0);
 344
 345                 ++worklist->current_timestep;
 346
 347 #ifdef DEBUG_libfirm
 348                 print_worklist(worklist, LEVEL_2);
 349                 DB((dbg, LEVEL_2, "\n"));
 350 #endif
 351         }
 352
 353 #ifdef DEBUG_libfirm
 354         DB((dbg, LEVEL_1, "worklist at begin of %+F:", block));
 355         print_worklist(worklist, LEVEL_1);
 356         DB((dbg, LEVEL_1, "\n"));
 357 #endif
 358 }
 359
 360 static void process_block(ir_node *block, void *env)
 361 {
 362         int              n_preds;
 363         const ir_edge_t *edge;
 364         worklist_t      *worklist        = NULL;
 365         double           best_execfreq   = -1;
 366         ir_node         *best_succ_block = NULL;
 367         int              best_pos        = -1;
 368
 369         (void) env;
 370         DB((dbg, LEVEL_1, "Processing %+F\n", block));
 371
 372         /* construct worklist */
 373         foreach_block_succ(block, edge) {
 374                 ir_node *succ_block = get_edge_src_irn(edge);
 375                 double   execfreq   = get_block_execfreq(exec_freq, succ_block);
 376
 377                 if(execfreq > best_execfreq) {
 378                         worklist_t *succ_worklist = get_irn_link(succ_block);
 379                         if(succ_worklist != NULL) {
 380                                 best_execfreq   = execfreq;
 381                                 worklist        = succ_worklist;
 382                                 best_succ_block = succ_block;
 383                                 best_pos        = get_edge_src_pos(edge);
 384                         }
 385                 }
 386         }
 387         if(worklist == NULL) {
 388                 /* only the end-block has 0 successors */
 389                 assert(block == get_irg_end_block(get_irn_irg(block)));
 390
 391                 worklist = obstack_alloc(&obst, sizeof(worklist[0]));
 392                 init_worklist(worklist, 0);
 393         } else {
 394                 worklist = duplicate_worklist(worklist, block, best_succ_block,
 395                                               best_pos);
 396                 activate_worklist(worklist);
 397
 398                 /* now we could have live values in the succ worklists that are not
 399                  * live anymore in the worklist we picked. We need reloads for them.
 400                  */
 401                 if(!tentative_mode) {
 402                         foreach_block_succ(block, edge) {
 403                                 ir_node      *succ_block    = get_edge_src_irn(edge);
 404                                 worklist_t   *succ_worklist = get_irn_link(succ_block);
 405
 406                                 spill_non_live_nodes(succ_worklist);
 407                         }
 408                 }
 409         }
 410
 411         do_spilling(block, worklist);
 412         deactivate_worklist(worklist);
 413
 414         set_irn_link(block, worklist);
 415
 416         /* we shouldn't have any live values left at the start block */
 417         n_preds = get_Block_n_cfgpreds(block);
 418         assert(n_preds != 0 || worklist->n_live_values == 0);
 419 }
 420
 421 static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls)
 422 {
 423         ir_graph *irg = be_get_birg_irg(birg);
 424
 425         cls       = ncls;
 426         n_regs    = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
 427
 428         if(n_regs == 0)
 429                 return;
 430
 431         arch_env       = be_get_birg_arch_env(birg);
 432         exec_freq      = be_get_birg_exec_freq(birg);
 433         tentative_mode = 0;
 434
 435         be_clear_links(irg);
 436         set_using_irn_link(irg);
 437         set_using_irn_visited(irg);
 438         inc_irg_visited(irg);
 439
 440         obstack_init(&obst);
 441         senv = be_new_spill_env(birg);
 442
 443         /* do a post-order walk over the CFG to make sure we have a maximum number
 444          * of preds processed before entering a block */
 445         irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
 446
 447         clear_using_irn_link(irg);
 448         clear_using_irn_visited(irg);
 449
 450         be_insert_spills_reloads(senv);
 451
 452         obstack_free(&obst, NULL);
 453
 454         /* clean up */
 455         be_delete_spill_env(senv);
 456 }
 457
 458 void be_init_spillbelady3(void)
 459 {
 460         static be_spiller_t belady3_spiller = {
 461                 be_spill_belady3
 462         };
 463
 464         be_register_spiller("belady3", &belady3_spiller);
 465         FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady3");
 466 }
 467
 468 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady3);