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

   1 /**
   2  * @file
   3  * @brief SSA construction for a set of nodes
   4  * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
   5  * @date        04.05.2005
   6  * @version     $Id$
   7  * Copyright:   (c) Universitaet Karlsruhe
   8  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   9  *
  10  * The problem: Given a value and a set of "copies" that are known to
  11  * represent the same abstract value, rewire all usages of the original value
  12  * to their closest copy while introducing phis as necessary.
  13  *
  14  * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
  15  * and it's copies. Link the copies ordered by dominance to the blocks.  The
  16  * we search for each use all all definitions in the current block, if none is
  17  * found, then we search one in the immediate dominator. If we are in a block
  18  * of the dominance frontier, create a phi and search do the same search for
  19  * the phi arguments.
  20  */
  21 #ifdef HAVE_CONFIG_H
  22 #include "config.h"
  23 #endif
  24
  25 #include "bessaconstr.h"
  26 #include "bemodule.h"
  27 #include "besched_t.h"
  28 #include "bera.h"
  29 #include "beirg_t.h"
  30
  31 #include "debug.h"
  32 #include "error.h"
  33 #include "pdeq.h"
  34 #include "array.h"
  35 #include "irdom.h"
  36
  37 #include "ircons.h"
  38 #include "iredges_t.h"
  39
  40 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  41
  42 /**
  43  * Calculates the iterated dominance frontier of a set of blocks. Marks the
  44  * blocks as visited. Sets the link fields of the blocks in the dominance
  45  * frontier to the block itself.
  46  */
  47 static
  48 void mark_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
  49                                        waitq *worklist)
  50 {
  51         DBG((dbg, LEVEL_3, "Dominance Frontier:"));
  52         while(!pdeq_empty(worklist)) {
  53                 int i;
  54                 ir_node *block = waitq_get(worklist);
  55                 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
  56                 int domfront_len = ARR_LEN(domfront);
  57
  58                 for (i = 0; i < domfront_len; ++i) {
  59                         ir_node *y = domfront[i];
  60                         if(Block_block_visited(y))
  61                                 continue;
  62
  63                         if(!irn_visited(y)) {
  64                                 set_irn_link(y, NULL);
  65                                 waitq_put(worklist, y);
  66                         }
  67                         DBG((dbg, LEVEL_3, " %+F", y));
  68                         mark_Block_block_visited(y);
  69                 }
  70         }
  71         DBG((dbg, LEVEL_3, "\n"));
  72 }
  73
  74 static
  75 ir_node *search_def_end_of_block(be_ssa_construction_env_t *env,
  76                                  ir_node *block);
  77
  78 static
  79 ir_node *create_phi(be_ssa_construction_env_t *env, ir_node *block,
  80                     ir_node *link_with)
  81 {
  82         int i, n_preds = get_Block_n_cfgpreds(block);
  83         ir_graph *irg = get_irn_irg(block);
  84         ir_node *phi;
  85         ir_node **ins = alloca(n_preds * sizeof(ins[0]));
  86
  87         assert(n_preds > 1);
  88
  89         for(i = 0; i < n_preds; ++i) {
  90                 ins[i] = new_r_Unknown(irg, env->mode);
  91         }
  92         phi = new_r_Phi(irg, block, n_preds, ins, env->mode);
  93         if(env->new_phis != NULL) {
  94                 ARR_APP1(ir_node*, env->new_phis, phi);
  95         }
  96
  97         if(env->mode != mode_M) {
  98                 sched_add_after(block, phi);
  99         }
 100
 101         DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
 102         set_irn_link(link_with, phi);
 103         mark_irn_visited(block);
 104
 105         for(i = 0; i < n_preds; ++i) {
 106                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 107                 ir_node *pred_def   = search_def_end_of_block(env, pred_block);
 108
 109                 set_irn_n(phi, i, pred_def);
 110         }
 111
 112         return phi;
 113 }
 114
 115 static
 116 ir_node *get_def_at_idom(be_ssa_construction_env_t *env, ir_node *block)
 117 {
 118         ir_node *dom = get_Block_idom(block);
 119         ir_node *def = search_def_end_of_block(env, dom);
 120
 121         return def;
 122 }
 123
 124 static
 125 ir_node *search_def_end_of_block(be_ssa_construction_env_t *env, ir_node *block)
 126 {
 127         if(irn_visited(block)) {
 128                 assert(get_irn_link(block) != NULL);
 129                 return get_irn_link(block);
 130         } else if(Block_block_visited(block)) {
 131                 return create_phi(env, block, block);
 132         } else {
 133                 ir_node *def = get_def_at_idom(env, block);
 134                 mark_irn_visited(block);
 135                 set_irn_link(block, def);
 136
 137                 return def;
 138         }
 139 }
 140
 141 static
 142 ir_node *search_def(be_ssa_construction_env_t *env, ir_node *at)
 143 {
 144         ir_node *block = get_nodes_block(at);
 145         ir_node *node;
 146         ir_node *def;
 147
 148         DBG((dbg, LEVEL_3, "\t...searching def at %+F\n", at));
 149
 150         /* no defs in the current block we can do the normal searching */
 151         if(!irn_visited(block) && !Block_block_visited(block)) {
 152                 DBG((dbg, LEVEL_3, "\t...continue at idom\n"));
 153                 return get_def_at_idom(env, block);
 154         }
 155
 156         /* there are defs in the current block, walk the linked list to find
 157            the one immediately dominating us
 158          */
 159         node = block;
 160         def  = get_irn_link(node);
 161         while(def != NULL) {
 162                 if(!value_dominates(at, def)) {
 163                         DBG((dbg, LEVEL_3, "\t...found dominating def %+F\n", def));
 164                         return def;
 165                 }
 166
 167                 node = def;
 168                 def  = get_irn_link(node);
 169         }
 170
 171         /* block in dominance frontier? create a phi then */
 172         if(Block_block_visited(block)) {
 173                 DBG((dbg, LEVEL_3, "\t...create phi at block %+F\n", block));
 174                 assert(!is_Phi(node));
 175                 return create_phi(env, block, node);
 176         }
 177
 178
 179         DBG((dbg, LEVEL_3, "\t...continue at idom (after checking block)\n"));
 180         return get_def_at_idom(env, block);
 181 }
 182
 183 /**
 184  * Adds a definition into the link field of the block. The definitions are
 185  * sorted by dominance. A non-visited block means no definition has been
 186  * inserted yet.
 187  */
 188 static
 189 void introduce_def_at_block(ir_node *block, ir_node *def)
 190 {
 191         if(irn_visited(block)) {
 192                 ir_node *node = block;
 193                 ir_node *current_def;
 194
 195                 while(1) {
 196                         current_def = get_irn_link(node);
 197                         if(current_def == def) {
 198                                 /* already in block */
 199                                 return;
 200                         }
 201                         if(current_def == NULL)
 202                                 break;
 203                         if(value_dominates(current_def, def))
 204                                 break;
 205                         node = current_def;
 206                 }
 207
 208                 set_irn_link(node, def);
 209                 set_irn_link(def, current_def);
 210         } else {
 211                 set_irn_link(block, def);
 212                 set_irn_link(def, NULL);
 213                 mark_irn_visited(block);
 214         }
 215 }
 216
 217 void be_ssa_construction_init(be_ssa_construction_env_t *env, be_irg_t *birg)
 218 {
 219         ir_graph *irg = be_get_birg_irg(birg);
 220         memset(env, 0, sizeof(env[0]));
 221
 222         be_assure_dom_front(birg);
 223
 224         env->irg       = irg;
 225         env->domfronts = be_get_birg_dom_front(birg);
 226         env->new_phis  = NEW_ARR_F(ir_node*, 0);
 227         env->worklist  = new_waitq();
 228
 229         set_using_visited(irg);
 230         set_using_block_visited(irg);
 231         set_using_irn_link(irg);
 232
 233         /* we use the visited flag to indicate blocks in the dominance frontier
 234          * and blocks that already have the relevant value at the end calculated */
 235         inc_irg_visited(irg);
 236         /* We use the block visited flag to indicate blocks in the dominance
 237          * froniter of some values (and this potentially needing phis) */
 238         inc_irg_block_visited(irg);
 239 }
 240
 241 void be_ssa_construction_destroy(be_ssa_construction_env_t *env)
 242 {
 243         del_waitq(env->worklist);
 244         DEL_ARR_F(env->new_phis);
 245
 246         clear_using_visited(env->irg);
 247         clear_using_block_visited(env->irg);
 248         clear_using_irn_link(env->irg);
 249 }
 250
 251 void be_ssa_construction_add_copy(be_ssa_construction_env_t *env,
 252                                   ir_node *copy)
 253 {
 254         ir_node *block;
 255
 256         assert(env->iterated_domfront_calculated == 0);
 257
 258         if(env->mode == NULL) {
 259                 env->mode = get_irn_mode(copy);
 260         } else {
 261                 assert(env->mode == get_irn_mode(copy));
 262         }
 263
 264         block = get_nodes_block(copy);
 265
 266         if(!irn_visited(block)) {
 267                 waitq_put(env->worklist, block);
 268         }
 269         introduce_def_at_block(block, copy);
 270 }
 271
 272 void be_ssa_construction_add_copies(be_ssa_construction_env_t *env,
 273                                     ir_node **copies, size_t copies_len)
 274 {
 275         size_t i;
 276
 277         assert(env->iterated_domfront_calculated == 0);
 278
 279         if(env->mode == NULL) {
 280                 env->mode = get_irn_mode(copies[0]);
 281         }
 282
 283         for(i = 0; i < copies_len; ++i) {
 284                 ir_node *copy = copies[i];
 285                 ir_node *block = get_nodes_block(copy);
 286
 287                 assert(env->mode == get_irn_mode(copy));
 288                 if(!irn_visited(block)) {
 289                         waitq_put(env->worklist, block);
 290                 }
 291                 introduce_def_at_block(block, copy);
 292         }
 293 }
 294
 295 void be_ssa_construction_set_ignore_uses(be_ssa_construction_env_t *env,
 296                                          const ir_nodeset_t *ignore_uses)
 297 {
 298         env->ignore_uses = ignore_uses;
 299 }
 300
 301 ir_node **be_ssa_construction_get_new_phis(be_ssa_construction_env_t *env)
 302 {
 303         return env->new_phis;
 304 }
 305
 306 void be_ssa_construction_fix_users(be_ssa_construction_env_t *env,
 307                                    ir_node *value)
 308 {
 309         const ir_edge_t *edge, *next;
 310
 311         if(!env->iterated_domfront_calculated) {
 312                 mark_iterated_dominance_frontiers(env->domfronts, env->worklist);
 313                 env->iterated_domfront_calculated = 1;
 314         }
 315
 316         /*
 317          * Search the valid def for each use and set it.
 318          */
 319         foreach_out_edge_safe(value, edge, next) {
 320                 ir_node *use = get_edge_src_irn(edge);
 321                 ir_node *at  = use;
 322                 int pos      = get_edge_src_pos(edge);
 323                 ir_node *def;
 324
 325                 if(env->ignore_uses != NULL     &&
 326                    ir_nodeset_contains(env->ignore_uses, use))
 327                         continue;
 328
 329                 if(is_Phi(use)) {
 330                         ir_node *block = get_nodes_block(use);
 331                         ir_node *predblock = get_Block_cfgpred_block(block, pos);
 332                         at = sched_last(predblock);
 333                 }
 334
 335                 def = search_def(env, at);
 336
 337                 if(def == NULL) {
 338                         panic("no definition found for %+F at position %d\n", use, pos);
 339                 }
 340
 341                 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 342                 set_irn_n(use, pos, def);
 343         }
 344 }
 345
 346 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
 347                                          ir_node **nodes, size_t nodes_len)
 348 {
 349         size_t i;
 350
 351         for(i = 0; i < nodes_len; ++i) {
 352                 ir_node *node = nodes[i];
 353                 be_ssa_construction_fix_users(env, node);
 354         }
 355 }
 356
 357 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
 358                                               be_lv_t *lv)
 359 {
 360         int i, n;
 361
 362         n = ARR_LEN(env->new_phis);
 363         for(i = 0; i < n; ++i) {
 364                 ir_node *phi = env->new_phis[i];
 365                 be_liveness_introduce(lv, phi);
 366         }
 367 }
 368
 369 #if 0
 370 ir_node **be_ssa_construction(const be_dom_front_info_t *domfronts, be_lv_t *lv,
 371                               ir_node *value, int copies_len, ir_node **copies,
 372                               const ir_nodeset_t *ignore_uses, int need_new_phis)
 373 {
 374         ir_graph *irg = get_irn_irg(value);
 375         const ir_edge_t *edge, *next;
 376         int i;
 377         ir_node *block;
 378         waitq *worklist;
 379         be_ssa_construction_env_t env;
 380
 381         /* We need to collect the phi functions to compute their liveness. */
 382         if(lv != NULL || need_new_phis) {
 383                 env.new_phis = NEW_ARR_F(ir_node*, 0);
 384         } else {
 385                 env.new_phis = NULL;
 386         }
 387         env.mode = get_irn_mode(value);
 388
 389         set_using_visited(irg);
 390         set_using_block_visited(irg);
 391         set_using_irn_link(irg);
 392
 393         /* we use the visited flag to indicate blocks in the dominance frontier
 394          * and blocks that already have the relevant value at the end calculated */
 395         inc_irg_visited(irg);
 396         /* We use the block visited flag to indicate blocks in the dominance
 397          * froniter of some values (and this potentially needing phis) */
 398         inc_irg_block_visited(irg);
 399
 400         DBG((dbg, LEVEL_1, "Introducing following copies for: %+F\n", value));
 401         /* compute iterated dominance frontiers and create lists in the block link
 402          * fields that sort usages by dominance. Blocks in the dominance frontier
 403          * are marked by links back to the block. */
 404         worklist = new_waitq();
 405
 406         block = get_nodes_block(value);
 407         /* we sometimes replace virtual values by real ones, in this case we do
 408            not want to insert them into the def list (they're not scheduled
 409            and can't be used anyway) */
 410         if(sched_is_scheduled(value)) {
 411                 introduce_def_at_block(block, value);
 412         }
 413         waitq_put(worklist, block);
 414
 415         for(i = 0; i < copies_len; ++i) {
 416                 ir_node *copy = copies[i];
 417                 block = get_nodes_block(copy);
 418
 419                 if(!irn_visited(block)) {
 420                         waitq_put(worklist, block);
 421                 }
 422                 introduce_def_at_block(block, copy);
 423                 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", copy, block));
 424         }
 425
 426         mark_iterated_dominance_frontiers(domfronts, worklist);
 427         del_waitq(worklist);
 428
 429         DBG((dbg, LEVEL_2, "New Definitions:\n"));
 430         /*
 431          * Search the valid def for each use and set it.
 432          */
 433         foreach_out_edge_safe(value, edge, next) {
 434                 ir_node *use = get_edge_src_irn(edge);
 435                 ir_node *at  = use;
 436                 int pos      = get_edge_src_pos(edge);
 437
 438                 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
 439                         continue;
 440
 441                 if(is_Phi(use)) {
 442                         ir_node *block = get_nodes_block(use);
 443                         ir_node *predblock = get_Block_cfgpred_block(block, pos);
 444                         at = sched_last(predblock);
 445                 }
 446
 447                 ir_node *def = search_def(&env, at);
 448
 449                 if(def == NULL) {
 450                         panic("no definition found for %+F at position %d\n", use, pos);
 451                 }
 452
 453                 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 454                 set_irn_n(use, pos, def);
 455         }
 456
 457         /* Recompute the liveness of the original nodes, the copies and the
 458          * inserted phis. */
 459         if(lv != NULL) {
 460                 int n;
 461
 462                 be_liveness_update(lv, value);
 463                 for(i = 0; i < copies_len; ++i) {
 464                         ir_node *copy = copies[i];
 465                         be_liveness_update(lv, copy);
 466                 }
 467
 468                 n = ARR_LEN(env.new_phis);
 469                 for(i = 0; i < n; ++i) {
 470                         ir_node *phi = env.new_phis[i];
 471                         be_liveness_introduce(lv, phi);
 472                 }
 473         }
 474
 475         clear_using_visited(irg);
 476         clear_using_block_visited(irg);
 477         clear_using_irn_link(irg);
 478
 479         if(!need_new_phis && env.new_phis != NULL) {
 480                 DEL_ARR_F(env.new_phis);
 481                 return NULL;
 482         }
 483         return env.new_phis;
 484 }
 485 #endif
 486
 487 void be_init_ssaconstr(void)
 488 {
 489         FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr");
 490 }
 491
 492 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr);