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.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 "beirgmod.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 *value)
  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 = value;
  86         spill_info->reloads = NEW_ARR_F(ir_node*, 0);
  87
  88         set_irn_link(value, spill_info);
  89         mark_irn_visited(value);
  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 *value, int force)
  99 {
 100         spill_info_t *spill_info;
 101
 102         if(irn_visited(value)) {
 103                 spill_info = (spill_info_t*) get_irn_link(value);
 104                 if(spill_info->spill != NULL || !force)
 105                         return spill_info;
 106         } else {
 107                 spill_info = create_spill_info(env, value);
 108         }
 109
 110         spill_info->spill = env->create_spill(env->func_env, value, force);
 111
 112         return spill_info;
 113 }
 114
 115 static
 116 void create_reload(minibelady_env_t *env, ir_node *value, ir_node *before)
 117 {
 118         spill_info_t *spill_info = create_spill(env, value, 0);
 119         ir_node *spill = spill_info->spill;
 120         ir_node *reload;
 121
 122         reload = env->create_reload(env->func_env, value, spill, before);
 123         ARR_APP1(ir_node*, spill_info->reloads, reload);
 124 }
 125
 126 static
 127 void spill_phi(minibelady_env_t *env, ir_node *phi)
 128 {
 129         ir_graph *irg = get_irn_irg(phi);
 130         ir_node *block = get_nodes_block(phi);
 131         int i, arity = get_irn_arity(phi);
 132         ir_node **in = alloca(arity * sizeof(in[0]));
 133         ir_node *spill_to_kill = NULL;
 134         spill_info_t *spill_info;
 135
 136         /* does a spill exist for the phis value? */
 137         if(irn_visited(phi)) {
 138                 spill_info = (spill_info_t*) get_irn_link(phi);
 139                 spill_to_kill = spill_info->spill;
 140         } else {
 141                 spill_info = create_spill_info(env, phi);
 142         }
 143
 144         /* create a new phi-M with bad preds */
 145         for(i = 0; i < arity; ++i) {
 146                 in[i] = new_r_Bad(irg);
 147         }
 148
 149         DBG((dbg, LEVEL_2, "\tcreate Phi-M for %+F\n", phi));
 150
 151         /* create a Phi-M */
 152         spill_info->spill = new_r_Phi(irg, block, arity, in, mode_M);
 153
 154         if(spill_to_kill != NULL) {
 155                 exchange(spill_to_kill, spill_info->spill);
 156                 sched_remove(spill_to_kill);
 157         }
 158
 159         /* create spills for the phi values */
 160         for(i = 0; i < arity; ++i) {
 161                 ir_node *in = get_irn_n(phi, i);
 162                 spill_info_t *pred_spill = create_spill(env, in, 1);
 163                 set_irn_n(spill_info->spill, i, pred_spill->spill);
 164         }
 165 }
 166
 167 static
 168 void belady(minibelady_env_t *env, ir_node *block);
 169
 170 /**
 171  * Collects all values live-in at block @p block and all phi results in this
 172  * block.
 173  * Then it adds the best values (at most n_regs) to the blocks start_workset.
 174  * The phis among the remaining values get spilled: Introduce psudo-copies of
 175  * their args to break interference and make it possible to spill them to the
 176  * same spill slot.
 177  */
 178 static
 179 block_info_t *compute_block_start_state(minibelady_env_t *env, ir_node *block)
 180 {
 181         block_info_t  *block_info;
 182         be_next_use_t  next_use;
 183         ir_loop       *loop;
 184         ir_node       *best_starter, *first;
 185         ir_node       *node;
 186         int            n_cfgpreds;
 187         unsigned       best_time;
 188         int            outer_loop_allowed;
 189         int            i;
 190
 191         /* Create the block info for this block. */
 192         block_info = new_block_info(&env->obst, block);
 193         n_cfgpreds = get_Block_n_cfgpreds(block);
 194
 195         /* no cfgpred -> no value active */
 196         if(n_cfgpreds == 0) {
 197                 block_info->start_state = NULL;
 198                 return block_info;
 199         }
 200
 201         /* for 1 pred only: simply take the the end-state of the pred */
 202         if(n_cfgpreds == 1) {
 203                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 204                 block_info_t *pred_info;
 205
 206                 /* process pred block */
 207                 belady(env, pred_block);
 208
 209                 pred_info = get_block_info(pred_block);
 210
 211                 DBG((dbg, LEVEL_2, "Taking end state from %+F: %+F\n", pred_block, pred_info->end_state));
 212                 block_info->start_state = pred_info->end_state;
 213                 return block_info;
 214         }
 215
 216         /* Collect all values living at start of block */
 217         DBG((dbg, LEVEL_2, "Living at start of %+F:\n", block));
 218         first = sched_first(block);
 219         loop = get_irn_loop(block);
 220         best_starter = NULL;
 221         best_time = USES_INFINITY;
 222         outer_loop_allowed = 1;
 223
 224         /* check all Phis first */
 225         sched_foreach(block, node) {
 226                 if (!is_Phi(node))
 227                         break;
 228                 if (arch_get_irn_register(env->arch_env, node) != env->reg)
 229                         continue;
 230
 231                 DBG((dbg, LEVEL_2, "\t...checking %+F\n", node));
 232                 next_use = be_get_next_use(env->uses, first, 0, node, 0);
 233
 234                 if(USES_IS_INFINITE(next_use.time)) {
 235                         DBG((dbg, LEVEL_2, "\tnot taken (dead)\n"));
 236                         continue;
 237                 }
 238
 239                 if(next_use.outermost_loop >= get_loop_depth(loop)) {
 240                         if(outer_loop_allowed || next_use.time < best_time) {
 241                                 DBG((dbg, LEVEL_2, "\ttaken (%u, loop %d)\n", next_use.time,
 242                                      next_use.outermost_loop));
 243
 244                                 if(best_starter != NULL) {
 245                                         /* spill the phi as it is not used */
 246                                         spill_phi(env, best_starter);
 247                                 }
 248                                 best_starter = node;
 249                                 best_time = next_use.time;
 250                                 outer_loop_allowed = 0;
 251                         }
 252                 } else {
 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                                 if(best_starter != NULL) {
 257                                         /* spill the phi as it is not used */
 258                                         spill_phi(env, best_starter);
 259                                 }
 260                                 best_starter = node;
 261                                 best_time = next_use.time;
 262                         }
 263                 }
 264
 265                 if(best_starter != node) {
 266                         /* spill the phi as it is not used */
 267                         spill_phi(env, best_starter);
 268                 }
 269         }
 270
 271         /* check all Live-Ins */
 272         be_lv_foreach(env->lv, block, be_lv_state_in, i) {
 273                 node = be_lv_get_irn(env->lv, block, i);
 274
 275                 if (arch_get_irn_register(env->arch_env, node) != env->reg)
 276                         continue;
 277
 278                 DBG((dbg, LEVEL_2, "\t...checking %+F\n", node));
 279                 next_use = be_get_next_use(env->uses, first, 0, node, 0);
 280
 281                 if(USES_IS_INFINITE(next_use.time)) {
 282                         DBG((dbg, LEVEL_2, "\tnot taken (dead)\n"));
 283                         continue;
 284                 }
 285
 286                 if(next_use.outermost_loop >= get_loop_depth(loop)) {
 287                         if(outer_loop_allowed || next_use.time < best_time) {
 288                                 DBG((dbg, LEVEL_2, "\ttaken (%u, loop %d)\n", next_use.time,
 289                                      next_use.outermost_loop));
 290
 291                                 if(best_starter != NULL && is_Phi(best_starter)) {
 292                                         /* spill the phi as it is not used */
 293                                         spill_phi(env, best_starter);
 294                                 }
 295                                 best_starter = node;
 296                                 best_time = next_use.time;
 297                                 outer_loop_allowed = 0;
 298                         }
 299                 } else {
 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                                 if(best_starter != NULL && is_Phi(best_starter)) {
 304                                         /* spill the phi as it is not used */
 305                                         spill_phi(env, best_starter);
 306                                 }
 307                                 best_starter = node;
 308                                 best_time = next_use.time;
 309                         }
 310                 }
 311         }
 312
 313         /* TODO: spill phis */
 314
 315         block_info->start_state = best_starter;
 316
 317         return block_info;
 318 }
 319
 320 /**
 321  * For the given block @p block, decide for each values
 322  * whether it is used from a register or is reloaded
 323  * before the use.
 324  */
 325 static
 326 void belady(minibelady_env_t *env, ir_node *block)
 327 {
 328         ir_node *current_state;
 329         ir_node *node;
 330         block_info_t *block_info;
 331
 332         /* Don't do a block twice */
 333         if(irn_visited(block))
 334                 return;
 335
 336         /* compute value to start with */
 337         block_info = compute_block_start_state(env, block);
 338
 339         /* get the starting workset for this block */
 340         DBG((dbg, LEVEL_3, "\n"));
 341         DBG((dbg, LEVEL_3, "Decide for %+F\n", block));
 342
 343         current_state = block_info->start_state;
 344         DBG((dbg, LEVEL_3, "Start value: %+F\n", current_state));
 345
 346         /* process the block from start to end */
 347         DBG((dbg, LEVEL_3, "Processing...\n"));
 348
 349         sched_foreach(block, node) {
 350                 int i, arity;
 351                 ir_node *need_val = NULL;
 352
 353                 /* projs are handled with the tuple value.
 354                  * Phis are no real instr (see insert_starters()) */
 355                 if (is_Proj(node) || is_Phi(node)) {
 356                         continue;
 357                 }
 358
 359                 /* check which state is desired for the node */
 360                 arity = get_irn_arity(node);
 361                 for(i = 0; i < arity; ++i) {
 362                         ir_node *in = get_irn_n(node, i);
 363                         const arch_register_t *reg =
 364                                 arch_get_irn_register(env->arch_env, in);
 365                         if(reg == env->reg) {
 366                                 assert(need_val == NULL);
 367                                 need_val = in;
 368                                 DBG((dbg, LEVEL_3, "\t... need state %+F\n", need_val));
 369                         }
 370                 }
 371                 /* create a reload to match state if necessary */
 372                 if(need_val != NULL && need_val != current_state) {
 373                         create_reload(env, need_val, node);
 374                 }
 375
 376                 DBG((dbg, LEVEL_3, "  ...%+F\n", node));
 377
 378                 /* record state changes by the node */
 379                 if (get_irn_mode(node) == mode_T) {
 380                         ir_node *proj;
 381                         for(proj = sched_next(node); is_Proj(proj);
 382                             proj = sched_next(proj)) {
 383                                 const arch_register_t *reg =
 384                                         arch_get_irn_register(env->arch_env, proj);
 385                                 if(reg == env->reg) {
 386                                         current_state = proj;
 387                                         DBG((dbg, LEVEL_3, "\t... current_state <- %+F\n", current_state));
 388                                 }
 389                         }
 390                 } else {
 391                         const arch_register_t *reg =
 392                                 arch_get_irn_register(env->arch_env, node);
 393                         if(reg == env->reg) {
 394                                 current_state = node;
 395                                 DBG((dbg, LEVEL_3, "\t... current_state <- %+F\n", current_state));
 396                         }
 397                 }
 398         }
 399
 400         /* Remember end-workset for this block */
 401         block_info->end_state = current_state;
 402         DBG((dbg, LEVEL_3, "End value for %+F: %+F\n", block, current_state));
 403 }
 404
 405 static
 406 void belady_walker(ir_node *block, void *data)
 407 {
 408         belady((minibelady_env_t*) data, block);
 409 }
 410
 411 static
 412 ir_node *get_end_of_block_insertion_point(ir_node *block)
 413 {
 414         ir_node *last = sched_last(block);
 415
 416         /* skip projs and keepanies behind the jump... */
 417         while(is_Proj(last) || be_is_Keep(last)) {
 418                 last = sched_prev(last);
 419         }
 420
 421         if(!is_cfop(last)) {
 422                 last = sched_next(last);
 423                 // last node must be a cfop, only exception is the start block
 424                 assert(last     == get_irg_start_block(get_irn_irg(block)));
 425         }
 426
 427         return last;
 428 }
 429
 430 /**
 431  * We must adapt the live-outs to the live-ins at each block-border.
 432  */
 433 static
 434 void fix_block_borders(ir_node *block, void *data) {
 435         minibelady_env_t *env = data;
 436         ir_graph *irg = get_irn_irg(block);
 437         ir_node *startblock = get_irg_start_block(irg);
 438         int i;
 439         int arity;
 440         block_info_t *block_info;
 441
 442         if(block == startblock)
 443                 return;
 444
 445         DBG((dbg, LEVEL_3, "\n"));
 446         DBG((dbg, LEVEL_3, "Fixing %+F\n", block));
 447
 448         block_info = get_block_info(block);
 449
 450         /* process all pred blocks */
 451         arity = get_irn_arity(block);
 452         for (i = 0; i < arity; ++i) {
 453                 ir_node *pred = get_Block_cfgpred_block(block, i);
 454                 block_info_t *pred_info = get_block_info(pred);
 455
 456                 DBG((dbg, LEVEL_3, "  Pred %+F\n", pred));
 457
 458                 if(pred_info->end_state != block_info->start_state &&
 459                         block_info->start_state != NULL) {
 460                         ir_node *need_state = block_info->start_state;
 461                         ir_node *insert_point =
 462                                 get_end_of_block_insertion_point(pred);
 463
 464                         create_reload(env, need_state, insert_point);
 465                 }
 466         }
 467 }
 468
 469 void be_assure_state(be_irg_t *birg, const arch_register_t *reg, void *func_env,
 470                      create_spill_func create_spill,
 471                      create_reload_func create_reload) {
 472         minibelady_env_t env;
 473         ir_graph *irg = be_get_birg_irg(birg);
 474         spill_info_t *info;
 475
 476         be_assure_liveness(birg);
 477         be_assure_dom_front(birg);
 478         /* construct control flow loop tree */
 479         if(! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) {
 480                 construct_cf_backedges(irg);
 481         }
 482
 483         obstack_init(&env.obst);
 484         env.arch_env      = birg->main_env->arch_env;
 485         env.reg           = reg;
 486         env.func_env      = func_env;
 487         env.create_spill  = create_spill;
 488         env.create_reload = create_reload;
 489         env.lv            = be_get_birg_liveness(birg);
 490         env.uses          = be_begin_uses(irg, env.lv);
 491         env.spills        = NULL;
 492
 493         set_using_visited(irg);
 494         set_using_irn_link(irg);
 495         inc_irg_visited(irg);
 496
 497         /* process blocks */
 498         irg_block_walk_graph(irg, NULL, belady_walker, &env);
 499
 500         /* fix block end_states that don't match the next blocks start_state */
 501         irg_block_walk_graph(irg, fix_block_borders, NULL, &env);
 502
 503         clear_using_visited(irg);
 504         clear_using_irn_link(irg);
 505
 506         /* reconstruct ssa-form */
 507         info = env.spills;
 508         while(info != NULL) {
 509                 int i, len;
 510                 ir_node **phis;
 511                 phis = be_ssa_construction(be_get_birg_dom_front(birg),
 512                                            be_get_birg_liveness(birg),
 513                                            info->value,
 514                                            ARR_LEN(info->reloads), info->reloads,
 515                                            NULL, 1);
 516
 517                 /* set register requirements for phis */
 518                 len = ARR_LEN(phis);
 519                 for(i = 0; i < len; ++i) {
 520                         ir_node *phi = phis[i];
 521                         be_set_phi_flags(env.arch_env, phi, arch_irn_flags_ignore);
 522                         arch_set_irn_register(env.arch_env, phi, env.reg);
 523                 }
 524                 DEL_ARR_F(phis);
 525
 526                 info = info->next;
 527         }
 528
 529         /* some nodes might be dead now. */
 530         be_remove_dead_nodes_from_schedule(irg);
 531
 532         be_end_uses(env.uses);
 533         obstack_free(&env.obst, NULL);
 534 }
 535
 536 void be_init_state(void)
 537 {
 538         FIRM_DBG_REGISTER(dbg, "firm.be.state");
 539 }
 540
 541 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_state);