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 ~ok
  29  *   - merge multiple start worksets of blocks ~ok
  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         ir_node          *reload_point;
  59         worklist_entry_t *next_reload;
  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 };
  67
  68 static const arch_env_t            *arch_env;
  69 static const arch_register_class_t *cls;
  70 static struct obstack               obst;
  71 static spill_env_t                 *senv;
  72 static size_t                       n_regs;
  73 static int                          tentative_mode;
  74 static ir_exec_freq                *exec_freq;
  75
  76 static worklist_t *new_worklist(void)
  77 {
  78         worklist_t *worklist = obstack_alloc(&obst, sizeof(worklist[0]));
  79
  80         INIT_LIST_HEAD(&worklist->live_values);
  81         worklist->n_live_values    = 0;
  82
  83         return worklist;
  84 }
  85
  86 static void mark_irn_not_visited(ir_node *node)
  87 {
  88         set_irn_visited(node, get_irg_visited(current_ir_graph) - 1);
  89 }
  90
  91 static void deactivate_worklist(const worklist_t *worklist)
  92 {
  93         struct list_head *entry;
  94
  95         list_for_each(entry, &worklist->live_values) {
  96                 worklist_entry_t *wl_entry
  97                         = list_entry(entry, worklist_entry_t, head);
  98                 assert(irn_visited(wl_entry->value));
  99                 mark_irn_not_visited(wl_entry->value);
 100                 set_irn_link(wl_entry->value, NULL);
 101         }
 102 }
 103
 104 /**
 105  * duplicate a worklist and directly activates it
 106  */
 107 static worklist_t *duplicate_activate_worklist(const worklist_t *worklist,
 108                 ir_node *block, ir_node *succ_block, int succ_pos)
 109 {
 110         ir_node          *reload_point  = NULL;
 111         size_t            n_live_values = 0;
 112         worklist_t       *new_worklist;
 113         struct list_head *entry;
 114
 115         if(succ_block != NULL && get_Block_n_cfgpreds(succ_block) > 1) {
 116                 reload_point = be_get_end_of_block_insertion_point(block);
 117         }
 118
 119         new_worklist = obstack_alloc(&obst, sizeof(new_worklist[0]));
 120         INIT_LIST_HEAD(&new_worklist->live_values);
 121
 122         list_for_each(entry, &worklist->live_values) {
 123                 worklist_entry_t *wl_entry  = list_entry(entry, worklist_entry_t, head);
 124                 ir_node          *value     = wl_entry->value;
 125                 worklist_entry_t *new_entry
 126                         = obstack_alloc(&obst, sizeof(new_entry[0]));
 127
 128                 if(is_Phi(value) && get_nodes_block(value) == succ_block) {
 129                         value = get_Phi_pred(value, succ_pos);
 130                 }
 131
 132                 new_entry->value = value;
 133                 if(reload_point != NULL) {
 134                         new_entry->reload_point = reload_point;
 135                 } else {
 136                         new_entry->reload_point = wl_entry->reload_point;
 137                 }
 138                 new_entry->next_reload = NULL;
 139
 140                 if(irn_not_visited(value)) {
 141                         list_add_tail(&new_entry->head, &new_worklist->live_values);
 142                         ++n_live_values;
 143
 144                         mark_irn_visited(value);
 145                         set_irn_link(value, new_entry);
 146                 } else {
 147                         /* the only way we might visit a value again, is when we get it as
 148                          * phi predecessor */
 149                         assert(is_Phi(wl_entry->value));
 150                 }
 151         }
 152         new_worklist->n_live_values = n_live_values;
 153
 154         return new_worklist;
 155 }
 156
 157 #ifdef DEBUG_libfirm
 158 static void print_worklist(const worklist_t *worklist, int level)
 159 {
 160         struct list_head *entry;
 161
 162         DB((dbg, level, "%d values: ", worklist->n_live_values));
 163         list_for_each(entry, &worklist->live_values) {
 164                 worklist_entry_t *wl_entry
 165                         = list_entry(entry, worklist_entry_t, head);
 166
 167                 DB((dbg, level, "%+F ", wl_entry->value));
 168         }
 169 }
 170 #endif
 171
 172 static void place_reload(worklist_entry_t *entry)
 173 {
 174         if(tentative_mode)
 175                 return;
 176
 177         /* walk list of reload points */
 178         do {
 179                 DB((dbg, LEVEL_1, "reload of %+F before %+F\n", entry->value,
 180                     entry->reload_point));
 181                 assert(entry->reload_point != NULL);
 182                 be_add_reload(senv, entry->value, entry->reload_point, cls, 1);
 183                 entry->reload_point = NULL;
 184
 185                 entry = entry->next_reload;
 186         } while(entry != NULL);
 187 }
 188
 189 /**
 190  * does stuff required for non-active worklists: spills all values not live
 191  * in the active worklist; links live values to the current worklist
 192  */
 193 static void process_non_active_worklist(const worklist_t *worklist,
 194                                         worklist_t *current_worklist)
 195 {
 196         struct list_head *entry;
 197
 198         list_for_each(entry, &worklist->live_values) {
 199                 worklist_entry_t *wl_entry = list_entry(entry, worklist_entry_t, head);
 200                 ir_node          *value    = wl_entry->value;
 201
 202                 if(!irn_visited(value)) {
 203                         /* if we still have room in the worklist, then we can simply take
 204                          * the value */
 205                         if(current_worklist->n_live_values < n_regs) {
 206                                 worklist_entry_t *new_entry
 207                                         = obstack_alloc(&obst, sizeof(new_entry[0]));
 208
 209                                 new_entry->value        = value;
 210                                 new_entry->reload_point = wl_entry->reload_point;
 211                                 new_entry->next_reload  = wl_entry->next_reload;
 212                                 set_irn_link(value, new_entry);
 213                                 mark_irn_visited(value);
 214                                 list_add(&new_entry->head, &current_worklist->live_values);
 215                                 ++current_worklist->n_live_values;
 216                         } else {
 217                                 /* value is not in current worklist, place reloads */
 218                                 place_reload(wl_entry);
 219                         }
 220                 } else {
 221                         /* value is in current worklist, link it with the reload point
 222                          * from this path */
 223                         worklist_entry_t *active_entry = get_irn_link(value);
 224                         wl_entry->next_reload          = active_entry->next_reload;
 225                         active_entry->next_reload      = wl_entry;
 226                 }
 227         }
 228 }
 229
 230 /**
 231  * makes sure the worklist contains not more than n_regs - room_needed entries
 232  */
 233 static void make_room(worklist_t *worklist, size_t room_needed)
 234 {
 235         int spills_needed = worklist->n_live_values + room_needed - n_regs;
 236         if(spills_needed > 0) {
 237                 int               i     = spills_needed;
 238                 struct list_head *entry = worklist->live_values.next;
 239                 for(i = spills_needed; i > 0; --i) {
 240                         struct list_head *next = entry->next;
 241                         worklist_entry_t *wl_entry
 242                                 = list_entry(entry, worklist_entry_t, head);
 243                         assert(irn_visited(wl_entry->value));
 244                         mark_irn_not_visited(wl_entry->value);
 245                         place_reload(wl_entry);
 246                         list_del(entry);
 247
 248                         entry = next;
 249                 }
 250                 worklist->n_live_values -= spills_needed;
 251         }
 252 }
 253
 254 /**
 255  * a value was used, so bring it to the back of the worklist (which might
 256  * result in a spill of another value).
 257  */
 258 static void val_used(worklist_t *worklist, ir_node *value, ir_node *sched_point)
 259 {
 260         /* is the node in the worklist already? */
 261         worklist_entry_t *entry = get_irn_link(value);
 262         if(irn_visited(value)) {
 263                 assert(entry != NULL);
 264
 265                 assert(irn_visited(value));
 266                 list_del(&entry->head);
 267         } else {
 268                 if(entry == NULL) {
 269                         entry        = obstack_alloc(&obst, sizeof(entry[0]));
 270                         entry->value = value;
 271                         set_irn_link(value, entry);
 272                 }
 273
 274                 ++worklist->n_live_values;
 275                 mark_irn_visited(value);
 276         }
 277
 278         entry->reload_point = sched_point;
 279         entry->next_reload  = NULL;
 280         list_add_tail(&entry->head, &worklist->live_values);
 281 }
 282
 283 static void worklist_remove(worklist_t *worklist, ir_node *value)
 284 {
 285         worklist_entry_t *entry = get_irn_link(value);
 286         assert(entry != NULL);
 287         list_del(&entry->head);
 288         --worklist->n_live_values;
 289
 290         assert(irn_visited(value));
 291         mark_irn_not_visited(value);
 292 }
 293
 294 static void do_spilling(ir_node *block, worklist_t *worklist)
 295 {
 296         ir_node *node;
 297
 298         assert(worklist != NULL);
 299
 300         sched_foreach_reverse(block, node) {
 301                 int    i, arity;
 302                 size_t n_defs = 0;
 303
 304                 DB((dbg, LEVEL_2, "\t%+F... ", node));
 305
 306                 if(is_Phi(node)) {
 307                         ir_node *node2;
 308                         /* TODO: if we have some free registers, then we could decide to
 309                          * not spill some phis (but not for phis where at least 1 input is
 310                          * themselfes) */
 311
 312                         /* we have to spill all phis that are not live */
 313                         sched_foreach_reverse_from(node, node2) {
 314                                 assert(is_Phi(node2));
 315
 316                                 if(irn_visited(node2))
 317                                         continue;
 318                                 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, node2))
 319                                         continue;
 320
 321                                 if(!tentative_mode)
 322                                         be_spill_phi(senv, node2);
 323                         }
 324                         break;
 325                 }
 326
 327                 /* remove values defined by this instruction from the workset. Values
 328                  * defined but not in the workset need free registers */
 329                 if(get_irn_mode(node) == mode_T) {
 330                         const ir_edge_t *edge;
 331
 332                         foreach_out_edge(node, edge) {
 333                                 ir_node *proj = get_edge_src_irn(edge);
 334                                 if(!arch_irn_consider_in_reg_alloc(arch_env, cls, proj))
 335                                         continue;
 336                                 if(irn_visited(proj)) {
 337                                         worklist_remove(worklist, proj);
 338                                 } else {
 339                                         ++n_defs;
 340                                 }
 341                         }
 342                 } else if(arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
 343                         if(irn_visited(node)) {
 344                                 worklist_remove(worklist, node);
 345                         } else {
 346                                 n_defs = 1;
 347                         }
 348                 }
 349
 350                 /* make sure we have enough free registers for the spills */
 351                 make_room(worklist, n_defs);
 352
 353                 /* put all values by the instruction into the workset */
 354                 arity = get_irn_arity(node);
 355                 for(i = 0; i < arity; ++i) {
 356                         ir_node *use = get_irn_n(node, i);
 357
 358                         if(!arch_irn_consider_in_reg_alloc(arch_env, cls, use))
 359                                 continue;
 360
 361                         val_used(worklist, use, node);
 362                 }
 363
 364                 /* we might have too many values in the worklist now and need to spill
 365                  * some */
 366                 make_room(worklist, 0);
 367
 368 #ifdef DEBUG_libfirm
 369                 print_worklist(worklist, LEVEL_2);
 370                 DB((dbg, LEVEL_2, "\n"));
 371 #endif
 372         }
 373
 374 #ifdef DEBUG_libfirm
 375         DB((dbg, LEVEL_1, "worklist at begin of %+F:", block));
 376         print_worklist(worklist, LEVEL_1);
 377         DB((dbg, LEVEL_1, "\n"));
 378 #endif
 379 }
 380
 381 static void process_block(ir_node *block, void *env)
 382 {
 383         int              n_preds;
 384         const ir_edge_t *edge;
 385         worklist_t      *worklist        = NULL;
 386         double           best_execfreq   = -1;
 387         ir_node         *best_succ_block = NULL;
 388         int              best_pos        = -1;
 389
 390         (void) env;
 391         DB((dbg, LEVEL_1, "Processing %+F\n", block));
 392
 393         /* construct worklist */
 394         foreach_block_succ(block, edge) {
 395                 ir_node *succ_block = get_edge_src_irn(edge);
 396                 double   execfreq   = get_block_execfreq(exec_freq, succ_block);
 397
 398                 if(execfreq > best_execfreq) {
 399                         worklist_t *succ_worklist = get_irn_link(succ_block);
 400                         if(succ_worklist != NULL) {
 401                                 best_execfreq   = execfreq;
 402                                 worklist        = succ_worklist;
 403                                 best_succ_block = succ_block;
 404                                 best_pos        = get_edge_src_pos(edge);
 405                         }
 406                 }
 407         }
 408         if(worklist == NULL) {
 409                 /* at least 1 successor block must have been processed unless it was
 410                  * the end block */
 411                 assert(tentative_mode || block == get_irg_end_block(get_irn_irg(block)));
 412
 413                 worklist = new_worklist();
 414 #ifdef DEBUG_libfirm
 415                 DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
 416                 print_worklist(worklist, LEVEL_1);
 417                 DB((dbg, LEVEL_1, "\n"));
 418 #endif
 419         } else {
 420                 worklist = duplicate_activate_worklist(worklist, block, best_succ_block,
 421                                                        best_pos);
 422
 423                 /* now we could have live values in the succ worklists that are not
 424                  * live anymore in the worklist we picked. We need reloads for them. */
 425                 foreach_block_succ(block, edge) {
 426                         ir_node      *succ_block    = get_edge_src_irn(edge);
 427                         worklist_t   *succ_worklist = get_irn_link(succ_block);
 428
 429                         if(succ_block == best_succ_block)
 430                                 continue;
 431
 432                         process_non_active_worklist(succ_worklist, worklist);
 433                 }
 434
 435 #ifdef DEBUG_libfirm
 436                 DB((dbg, LEVEL_1, "worklist at end of %+F:", block));
 437                 print_worklist(worklist, LEVEL_1);
 438                 DB((dbg, LEVEL_1, "\n"));
 439 #endif
 440         }
 441
 442         do_spilling(block, worklist);
 443         deactivate_worklist(worklist);
 444
 445         set_irn_link(block, worklist);
 446
 447         /* we shouldn't have any live values left at the start block */
 448         n_preds = get_Block_n_cfgpreds(block);
 449         assert(n_preds != 0 || worklist->n_live_values == 0);
 450 }
 451
 452 static void be_spill_belady3(be_irg_t *birg, const arch_register_class_t *ncls)
 453 {
 454         ir_graph *irg = be_get_birg_irg(birg);
 455
 456         cls       = ncls;
 457         n_regs    = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
 458
 459         if(n_regs == 0)
 460                 return;
 461
 462         arch_env       = be_get_birg_arch_env(birg);
 463         exec_freq      = be_get_birg_exec_freq(birg);
 464
 465         be_clear_links(irg);
 466         set_using_irn_link(irg);
 467         set_using_irn_visited(irg);
 468         inc_irg_visited(irg);
 469
 470         obstack_init(&obst);
 471         senv = be_new_spill_env(birg);
 472
 473         /* do a post-order walk over the CFG to make sure we have a maximum number
 474          * of preds processed before entering a block */
 475         tentative_mode = 1;
 476         irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
 477
 478         tentative_mode = 1;
 479         irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
 480
 481         tentative_mode = 0;
 482         irg_block_edges_walk(get_irg_start_block(irg), NULL, process_block, NULL);
 483
 484         clear_using_irn_link(irg);
 485         clear_using_irn_visited(irg);
 486
 487         be_insert_spills_reloads(senv);
 488
 489         obstack_free(&obst, NULL);
 490
 491         /* clean up */
 492         be_delete_spill_env(senv);
 493 }
 494
 495 void be_init_spillbelady3(void)
 496 {
 497         static be_spiller_t belady3_spiller = {
 498                 be_spill_belady3
 499         };
 500
 501         be_register_spiller("belady3", &belady3_spiller);
 502         FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady3");
 503 }
 504
 505 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady3);