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

   1 /**
   2  * @file
   3  * @brief       Handles state switching. This is basically the belady spill
   4  *              algorithm optimized for the 1-register case.
   5  * @author      Matthias Braun
   6  * @date        26.03.2007
   7  * @version     $Id$
   8  * Copyright:   (c) Universitaet Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11 #ifdef HAVE_CONFIG_H
  12 #include "config.h"
  13 #endif
  14
  15 #include "bestate.h"
  16
  17 #include "obst.h"
  18 #include "irgraph_t.h"
  19 #include "irnode_t.h"
  20 #include "irgwalk.h"
  21 #include "irloop.h"
  22 #include "iredges_t.h"
  23 #include "ircons_t.h"
  24 #include "irgmod.h"
  25
  26 #include "bearch_t.h"
  27 #include "beuses_t.h"
  28 #include "besched_t.h"
  29 #include "belive_t.h"
  30 #include "bemodule.h"
  31 #include "benode_t.h"
  32 #include "bessaconstr.h"
  33
  34 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  35
  36 typedef struct spill_info_t {
  37         struct spill_info_t *next;
  38         ir_node *value;
  39         ir_node *spill;
  40         ir_node **reloads;
  41 } spill_info_t;
  42
  43 typedef struct minibelady_env_t {
  44         struct obstack         obst;
  45         const arch_env_t      *arch_env;
  46         const arch_register_t *reg;
  47         const be_lv_t         *lv;
  48         void                  *func_env;
  49         create_reload_func     create_reload;
  50         create_spill_func      create_spill;
  51         spill_info_t          *spills;
  52
  53         be_uses_t             *uses;           /**< env for the next-use magic */
  54 } minibelady_env_t;
  55
  56 typedef struct block_info_t {
  57         ir_node *start_state;
  58         ir_node *end_state;
  59 } block_info_t;
  60
  61 static INLINE
  62 block_info_t *new_block_info(struct obstack *obst, ir_node *block)
  63 {
  64         block_info_t *res = obstack_alloc(obst, sizeof(*res));
  65         memset(res, 0, sizeof(res[0]));
  66
  67         set_irn_link(block, res);
  68         mark_irn_visited(block);
  69
  70         return res;
  71 }
  72
  73 static INLINE
  74 block_info_t *get_block_info(ir_node *block)
  75 {
  76         assert(irn_visited(block));
  77         return (block_info_t*) get_irn_link(block);
  78 }
  79
  80 static INLINE
  81 spill_info_t *create_spill_info(minibelady_env_t *env, ir_node *state)
  82 {
  83         spill_info_t *spill_info = obstack_alloc(&env->obst, sizeof(spill_info[0]));
  84         memset(spill_info, 0, sizeof(spill_info[0]));
  85         spill_info->value = state;
  86         spill_info->reloads = NEW_ARR_F(ir_node*, 0);
  87
  88         set_irn_link(state, spill_info);
  89         mark_irn_visited(state);
  90
  91         spill_info->next = env->spills;
  92         env->spills = spill_info;
  93
  94         return spill_info;
  95 }
  96
  97 static
  98 spill_info_t *create_spill(minibelady_env_t *env, ir_node *state, int force)
  99 {
 100         spill_info_t *spill_info;
 101         ir_node *next;
 102         ir_node *after;
 103
 104         if(irn_visited(state)) {
 105                 spill_info = (spill_info_t*) get_irn_link(state);
 106                 if(spill_info->spill != NULL || !force)
 107                         return spill_info;
 108         } else {
 109                 spill_info = create_spill_info(env, state);
 110         }
 111
 112         if(sched_is_scheduled(state)) {
 113                 next = state;
 114                 do {
 115                         after = next;
 116                         next = sched_next(after);
 117                 } while(is_Proj(next) || is_Phi(next) || be_is_Keep(next));
 118         } else {
 119                 after = state;
 120         }
 121         spill_info->spill = env->create_spill(env->func_env, state, force, after);
 122
 123         return spill_info;
 124 }
 125
 126 static
 127 void create_reload(minibelady_env_t *env, ir_node *state, ir_node *before,
 128                    ir_node *last_state)
 129 {
 130         spill_info_t *spill_info = create_spill(env, state, 0);
 131         ir_node *spill = spill_info->spill;
 132         ir_node *reload;
 133
 134         reload = env->create_reload(env->func_env, state, spill, before,
 135                                     last_state);
 136         ARR_APP1(ir_node*, spill_info->reloads, reload);
 137 }
 138
 139 static
 140 void spill_phi(minibelady_env_t *env, ir_node *phi)
 141 {
 142         ir_graph *irg = get_irn_irg(phi);
 143         ir_node *block = get_nodes_block(phi);
 144         int i, arity = get_irn_arity(phi);
 145         ir_node **in = alloca(arity * sizeof(in[0]));
 146         ir_node *spill_to_kill = NULL;
 147         spill_info_t *spill_info;
 148
 149         /* does a spill exist for the phis value? */
 150         if(irn_visited(phi)) {
 151                 spill_info = (spill_info_t*) get_irn_link(phi);
 152                 spill_to_kill = spill_info->spill;
 153         } else {
 154                 spill_info = create_spill_info(env, phi);
 155         }
 156
 157         /* create a new phi-M with bad preds */
 158         for(i = 0; i < arity; ++i) {
 159                 in[i] = new_r_Bad(irg);
 160         }
 161
 162         DBG((dbg, LEVEL_2, "\tcreate Phi-M for %+F\n", phi));
 163
 164         /* create a Phi-M */
 165         spill_info->spill = new_r_Phi(irg, block, arity, in, mode_M);
 166
 167         if(spill_to_kill != NULL) {
 168                 exchange(spill_to_kill, spill_info->spill);
 169                 sched_remove(spill_to_kill);
 170         }
 171
 172         /* create spills for the phi values */
 173         for(i = 0; i < arity; ++i) {
 174                 ir_node *in = get_irn_n(phi, i);
 175                 spill_info_t *pred_spill = create_spill(env, in, 1);
 176                 set_irn_n(spill_info->spill, i, pred_spill->spill);
 177         }
 178 }
 179
 180 static
 181 void belady(minibelady_env_t *env, ir_node *block);
 182
 183 /**
 184  * Collects all values live-in at block @p block and all phi results in this
 185  * block.
 186  * Then it adds the best values (at most n_regs) to the blocks start_workset.
 187  * The phis among the remaining values get spilled: Introduce psudo-copies of
 188  * their args to break interference and make it possible to spill them to the
 189  * same spill slot.
 190  */
 191 static
 192 block_info_t *compute_block_start_state(minibelady_env_t *env, ir_node *block)
 193 {
 194         block_info_t  *block_info;
 195         be_next_use_t  next_use;
 196         ir_loop       *loop;
 197         ir_node       *best_starter, *first;
 198         ir_node       *node;
 199         int            n_cfgpreds;
 200         unsigned       best_time;
 201         int            outer_loop_allowed;
 202         int            i;
 203
 204         /* Create the block info for this block. */
 205         block_info = new_block_info(&env->obst, block);
 206         n_cfgpreds = get_Block_n_cfgpreds(block);
 207
 208         /* no cfgpred -> no value active */
 209         if(n_cfgpreds == 0) {
 210                 block_info->start_state = NULL;
 211                 return block_info;
 212         }
 213
 214         /* for 1 pred only: simply take the the end-state of the pred */
 215         if(n_cfgpreds == 1) {
 216                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 217                 block_info_t *pred_info;
 218
 219                 /* process pred block */
 220                 belady(env, pred_block);
 221
 222                 pred_info = get_block_info(pred_block);
 223
 224                 DBG((dbg, LEVEL_2, "Taking end state from %+F: %+F\n", pred_block, pred_info->end_state));
 225                 block_info->start_state = pred_info->end_state;
 226                 return block_info;
 227         }
 228
 229         /* Collect all values living at start of block */
 230         DBG((dbg, LEVEL_2, "Living at start of %+F:\n", block));
 231         first = sched_first(block);
 232         loop = get_irn_loop(block);
 233         best_starter = NULL;
 234         best_time = USES_INFINITY;
 235         outer_loop_allowed = 1;
 236
 237         /* check all Phis first */
 238         sched_foreach(block, node) {
 239                 if (!is_Phi(node))
 240                         break;
 241                 if (arch_get_irn_register(env->arch_env, node) != env->reg)
 242                         continue;
 243
 244                 DBG((dbg, LEVEL_2, "\t...checking %+F\n", node));
 245                 next_use = be_get_next_use(env->uses, first, 0, node, 0);
 246
 247                 if(USES_IS_INFINITE(next_use.time)) {
 248                         DBG((dbg, LEVEL_2, "\tnot taken (dead)\n"));
 249                         continue;
 250                 }
 251
 252                 if(next_use.outermost_loop >= get_loop_depth(loop)) {
 253                         if(outer_loop_allowed || next_use.time < best_time) {
 254                                 DBG((dbg, LEVEL_2, "\ttaken (%u, loop %d)\n", next_use.time,
 255                                      next_use.outermost_loop));
 256
 257                                 if(best_starter != NULL) {
 258                                         /* spill the phi as it is not used */
 259                                         spill_phi(env, best_starter);
 260                                 }
 261                                 best_starter = node;
 262                                 best_time = next_use.time;
 263                                 outer_loop_allowed = 0;
 264                         }
 265                 } else {
 266                         if(outer_loop_allowed && next_use.time < best_time) {
 267                                 DBG((dbg, LEVEL_2, "\ttaken (%u, loop %d)\n", next_use.time,
 268                                      next_use.outermost_loop));
 269                                 if(best_starter != NULL) {
 270                                         /* spill the phi as it is not used */
 271                                         spill_phi(env, best_starter);
 272                                 }
 273                                 best_starter = node;
 274                                 best_time = next_use.time;
 275                         }
 276                 }
 277
 278                 if(best_starter != node) {
 279                         /* spill the phi as it is not used */
 280                         spill_phi(env, best_starter);
 281                 }
 282         }
 283
 284         /* check all Live-Ins */
 285         be_lv_foreach(env->lv, block, be_lv_state_in, i) {
 286                 node = be_lv_get_irn(env->lv, block, i);
 287
 288                 if (arch_get_irn_register(env->arch_env, node) != env->reg)
 289                         continue;
 290
 291                 DBG((dbg, LEVEL_2, "\t...checking %+F\n", node));
 292                 next_use = be_get_next_use(env->uses, first, 0, node, 0);
 293
 294                 if(USES_IS_INFINITE(next_use.time)) {
 295                         DBG((dbg, LEVEL_2, "\tnot taken (dead)\n"));
 296                         continue;
 297                 }
 298
 299                 if(next_use.outermost_loop >= get_loop_depth(loop)) {
 300                         if(outer_loop_allowed || next_use.time < best_time) {
 301                                 DBG((dbg, LEVEL_2, "\ttaken (%u, loop %d)\n", next_use.time,
 302                                      next_use.outermost_loop));
 303
 304                                 if(best_starter != NULL && is_Phi(best_starter)) {
 305                                         /* spill the phi as it is not used */
 306                                         spill_phi(env, best_starter);
 307                                 }
 308                                 best_starter = node;
 309                                 best_time = next_use.time;
 310                                 outer_loop_allowed = 0;
 311                         }
 312                 } else {
 313                         if(outer_loop_allowed && next_use.time < best_time) {
 314                                 DBG((dbg, LEVEL_2, "\ttaken (%u, loop %d)\n", next_use.time,
 315                                      next_use.outermost_loop));
 316                                 if(best_starter != NULL && is_Phi(best_starter)) {
 317                                         /* spill the phi as it is not used */
 318                                         spill_phi(env, best_starter);
 319                                 }
 320                                 best_starter = node;
 321                                 best_time = next_use.time;
 322                         }
 323                 }
 324         }
 325
 326         block_info->start_state = best_starter;
 327
 328         return block_info;
 329 }
 330
 331 /**
 332  * For the given block @p block, decide for each values
 333  * whether it is used from a register or is reloaded
 334  * before the use.
 335  */
 336 static
 337 void belady(minibelady_env_t *env, ir_node *block)
 338 {
 339         ir_node *current_state;
 340         ir_node *node;
 341         block_info_t *block_info;
 342
 343         /* Don't do a block twice */
 344         if(irn_visited(block))
 345                 return;
 346
 347         /* compute value to start with */
 348         block_info = compute_block_start_state(env, block);
 349
 350         /* get the starting workset for this block */
 351         DBG((dbg, LEVEL_3, "\n"));
 352         DBG((dbg, LEVEL_3, "Decide for %+F\n", block));
 353
 354         current_state = block_info->start_state;
 355         DBG((dbg, LEVEL_3, "Start value: %+F\n", current_state));
 356
 357         /* process the block from start to end */
 358         DBG((dbg, LEVEL_3, "Processing...\n"));
 359
 360         sched_foreach(block, node) {
 361                 int i, arity;
 362                 ir_node *need_val = NULL;
 363
 364                 /* projs are handled with the tuple value.
 365                  * Phis are no real instr (see insert_starters()) */
 366                 if (is_Proj(node) || is_Phi(node)) {
 367                         continue;
 368                 }
 369
 370                 /* check which state is desired for the node */
 371                 arity = get_irn_arity(node);
 372                 for(i = 0; i < arity; ++i) {
 373                         ir_node *in = get_irn_n(node, i);
 374                         const arch_register_t *reg =
 375                                 arch_get_irn_register(env->arch_env, in);
 376                         if(reg == env->reg) {
 377                                 assert(need_val == NULL);
 378                                 need_val = in;
 379                                 DBG((dbg, LEVEL_3, "\t... need state %+F\n", need_val));
 380                         }
 381                 }
 382                 /* create a reload to match state if necessary */
 383                 if(need_val != NULL && need_val != current_state) {
 384                         DBG((dbg, LEVEL_3, "\t... reloading %+F\n", need_val));
 385                         create_reload(env, need_val, node, current_state);
 386                         current_state = need_val;
 387                 }
 388
 389                 DBG((dbg, LEVEL_3, "  ...%+F\n", node));
 390
 391                 /* record state changes by the node */
 392                 if (get_irn_mode(node) == mode_T) {
 393                         ir_node *proj;
 394                         for(proj = sched_next(node); is_Proj(proj);
 395                             proj = sched_next(proj)) {
 396                                 const arch_register_t *reg =
 397                                         arch_get_irn_register(env->arch_env, proj);
 398                                 if(reg == env->reg) {
 399                                         current_state = proj;
 400                                         DBG((dbg, LEVEL_3, "\t... current_state <- %+F\n", current_state));
 401                                 }
 402                         }
 403                 } else {
 404                         const arch_register_t *reg =
 405                                 arch_get_irn_register(env->arch_env, node);
 406                         if(reg == env->reg) {
 407                                 current_state = node;
 408                                 DBG((dbg, LEVEL_3, "\t... current_state <- %+F\n", current_state));
 409                         }
 410                 }
 411         }
 412
 413         /* Remember end-workset for this block */
 414         block_info->end_state = current_state;
 415         DBG((dbg, LEVEL_3, "End value for %+F: %+F\n", block, current_state));
 416 }
 417
 418 static
 419 void belady_walker(ir_node *block, void *data)
 420 {
 421         belady((minibelady_env_t*) data, block);
 422 }
 423
 424 static
 425 ir_node *get_end_of_block_insertion_point(ir_node *block)
 426 {
 427         ir_node *last = sched_last(block);
 428
 429         /* skip projs and keepanies behind the jump... */
 430         while(is_Proj(last) || be_is_Keep(last)) {
 431                 last = sched_prev(last);
 432         }
 433
 434         if(!is_cfop(last)) {
 435                 last = sched_next(last);
 436                 // last node must be a cfop, only exception is the start block
 437                 assert(last     == get_irg_start_block(get_irn_irg(block)));
 438         }
 439
 440         return last;
 441 }
 442
 443 /**
 444  * We must adapt the live-outs to the live-ins at each block-border.
 445  */
 446 static
 447 void fix_block_borders(ir_node *block, void *data) {
 448         minibelady_env_t *env = data;
 449         ir_graph *irg = get_irn_irg(block);
 450         ir_node *startblock = get_irg_start_block(irg);
 451         int i;
 452         int arity;
 453         block_info_t *block_info;
 454
 455         if(block == startblock)
 456                 return;
 457
 458         DBG((dbg, LEVEL_3, "\n"));
 459         DBG((dbg, LEVEL_3, "Fixing %+F\n", block));
 460
 461         block_info = get_block_info(block);
 462
 463         /* process all pred blocks */
 464         arity = get_irn_arity(block);
 465         for (i = 0; i < arity; ++i) {
 466                 ir_node *pred = get_Block_cfgpred_block(block, i);
 467                 block_info_t *pred_info = get_block_info(pred);
 468
 469                 DBG((dbg, LEVEL_3, "  Pred %+F\n", pred));
 470
 471                 if(pred_info->end_state != block_info->start_state &&
 472                         block_info->start_state != NULL) {
 473                         ir_node *need_state = block_info->start_state;
 474                         ir_node *insert_point =
 475                                 get_end_of_block_insertion_point(pred);
 476
 477                         create_reload(env, need_state, insert_point, pred_info->end_state);
 478                 }
 479         }
 480 }
 481
 482 void be_assure_state(be_irg_t *birg, const arch_register_t *reg, void *func_env,
 483                      create_spill_func create_spill,
 484                      create_reload_func create_reload) {
 485         minibelady_env_t env;
 486         ir_graph *irg = be_get_birg_irg(birg);
 487         spill_info_t *info;
 488         be_lv_t *lv = be_get_birg_liveness(birg);
 489
 490         be_assure_liveness(birg);
 491         be_assure_dom_front(birg);
 492         /* construct control flow loop tree */
 493         if(! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) {
 494                 construct_cf_backedges(irg);
 495         }
 496
 497         obstack_init(&env.obst);
 498         env.arch_env      = be_get_birg_arch_env(birg);
 499         env.reg           = reg;
 500         env.func_env      = func_env;
 501         env.create_spill  = create_spill;
 502         env.create_reload = create_reload;
 503         env.lv            = be_get_birg_liveness(birg);
 504         env.uses          = be_begin_uses(irg, env.lv);
 505         env.spills        = NULL;
 506
 507         set_using_visited(irg);
 508         set_using_irn_link(irg);
 509         inc_irg_visited(irg);
 510
 511         /* process blocks */
 512         irg_block_walk_graph(irg, NULL, belady_walker, &env);
 513
 514         /* fix block end_states that don't match the next blocks start_state */
 515         irg_block_walk_graph(irg, fix_block_borders, NULL, &env);
 516
 517         clear_using_visited(irg);
 518         clear_using_irn_link(irg);
 519
 520         /* reconstruct ssa-form */
 521         info = env.spills;
 522         while(info != NULL) {
 523                 be_ssa_construction_env_t senv;
 524                 int i, len;
 525                 ir_node **phis;
 526
 527                 be_ssa_construction_init(&senv, birg);
 528                 if(sched_is_scheduled(info->value))
 529                         be_ssa_construction_add_copy(&senv, info->value);
 530                 be_ssa_construction_add_copies(&senv,
 531                                                info->reloads, ARR_LEN(info->reloads));
 532                 be_ssa_construction_fix_users(&senv, info->value);
 533
 534                 if(lv != NULL) {
 535                         be_ssa_construction_update_liveness_phis(&senv, lv);
 536
 537                         be_liveness_update(lv, info->value);
 538                         len = ARR_LEN(info->reloads);
 539                         for(i = 0; i < len; ++i) {
 540                                 ir_node *reload = info->reloads[i];
 541                                 be_liveness_update(lv, reload);
 542                         }
 543                 }
 544
 545                 phis = be_ssa_construction_get_new_phis(&senv);
 546
 547                 /* set register requirements for phis */
 548                 len = ARR_LEN(phis);
 549                 for(i = 0; i < len; ++i) {
 550                         ir_node *phi = phis[i];
 551                         be_set_phi_flags(env.arch_env, phi, arch_irn_flags_ignore);
 552                         arch_set_irn_register(env.arch_env, phi, env.reg);
 553                 }
 554                 be_ssa_construction_destroy(&senv);
 555
 556                 info = info->next;
 557         }
 558
 559         /* some nodes might be dead now. */
 560         be_remove_dead_nodes_from_schedule(irg);
 561
 562         be_end_uses(env.uses);
 563         obstack_free(&env.obst, NULL);
 564 }
 565
 566 void be_init_state(void)
 567 {
 568         FIRM_DBG_REGISTER(dbg, "firm.be.state");
 569 }
 570
 571 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_state);