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
 324                 if(env->ignore_uses != NULL     &&
 325                    ir_nodeset_contains(env->ignore_uses, use))
 326                         continue;
 327
 328                 if(is_Phi(use)) {
 329                         ir_node *block = get_nodes_block(use);
 330                         ir_node *predblock = get_Block_cfgpred_block(block, pos);
 331                         at = sched_last(predblock);
 332                 }
 333
 334                 ir_node *def = search_def(env, at);
 335
 336                 if(def == NULL) {
 337                         panic("no definition found for %+F at position %d\n", use, pos);
 338                 }
 339
 340                 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 341                 set_irn_n(use, pos, def);
 342         }
 343 }
 344
 345 void be_ssa_construction_fix_users_array(be_ssa_construction_env_t *env,
 346                                          ir_node **nodes, size_t nodes_len)
 347 {
 348         size_t i;
 349
 350         for(i = 0; i < nodes_len; ++i) {
 351                 ir_node *node = nodes[i];
 352                 be_ssa_construction_fix_users(env, node);
 353         }
 354 }
 355
 356 void be_ssa_construction_update_liveness_phis(be_ssa_construction_env_t *env,
 357                                               be_lv_t *lv)
 358 {
 359         int i, n;
 360
 361         n = ARR_LEN(env->new_phis);
 362         for(i = 0; i < n; ++i) {
 363                 ir_node *phi = env->new_phis[i];
 364                 be_liveness_introduce(lv, phi);
 365         }
 366 }
 367
 368 #if 0
 369 ir_node **be_ssa_construction(const be_dom_front_info_t *domfronts, be_lv_t *lv,
 370                               ir_node *value, int copies_len, ir_node **copies,
 371                               const ir_nodeset_t *ignore_uses, int need_new_phis)
 372 {
 373         ir_graph *irg = get_irn_irg(value);
 374         const ir_edge_t *edge, *next;
 375         int i;
 376         ir_node *block;
 377         waitq *worklist;
 378         be_ssa_construction_env_t env;
 379
 380         /* We need to collect the phi functions to compute their liveness. */
 381         if(lv != NULL || need_new_phis) {
 382                 env.new_phis = NEW_ARR_F(ir_node*, 0);
 383         } else {
 384                 env.new_phis = NULL;
 385         }
 386         env.mode = get_irn_mode(value);
 387
 388         set_using_visited(irg);
 389         set_using_block_visited(irg);
 390         set_using_irn_link(irg);
 391
 392         /* we use the visited flag to indicate blocks in the dominance frontier
 393          * and blocks that already have the relevant value at the end calculated */
 394         inc_irg_visited(irg);
 395         /* We use the block visited flag to indicate blocks in the dominance
 396          * froniter of some values (and this potentially needing phis) */
 397         inc_irg_block_visited(irg);
 398
 399         DBG((dbg, LEVEL_1, "Introducing following copies for: %+F\n", value));
 400         /* compute iterated dominance frontiers and create lists in the block link
 401          * fields that sort usages by dominance. Blocks in the dominance frontier
 402          * are marked by links back to the block. */
 403         worklist = new_waitq();
 404
 405         block = get_nodes_block(value);
 406         /* we sometimes replace virtual values by real ones, in this case we do
 407            not want to insert them into the def list (they're not scheduled
 408            and can't be used anyway) */
 409         if(sched_is_scheduled(value)) {
 410                 introduce_def_at_block(block, value);
 411         }
 412         waitq_put(worklist, block);
 413
 414         for(i = 0; i < copies_len; ++i) {
 415                 ir_node *copy = copies[i];
 416                 block = get_nodes_block(copy);
 417
 418                 if(!irn_visited(block)) {
 419                         waitq_put(worklist, block);
 420                 }
 421                 introduce_def_at_block(block, copy);
 422                 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", copy, block));
 423         }
 424
 425         mark_iterated_dominance_frontiers(domfronts, worklist);
 426         del_waitq(worklist);
 427
 428         DBG((dbg, LEVEL_2, "New Definitions:\n"));
 429         /*
 430          * Search the valid def for each use and set it.
 431          */
 432         foreach_out_edge_safe(value, edge, next) {
 433                 ir_node *use = get_edge_src_irn(edge);
 434                 ir_node *at  = use;
 435                 int pos      = get_edge_src_pos(edge);
 436
 437                 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
 438                         continue;
 439
 440                 if(is_Phi(use)) {
 441                         ir_node *block = get_nodes_block(use);
 442                         ir_node *predblock = get_Block_cfgpred_block(block, pos);
 443                         at = sched_last(predblock);
 444                 }
 445
 446                 ir_node *def = search_def(&env, at);
 447
 448                 if(def == NULL) {
 449                         panic("no definition found for %+F at position %d\n", use, pos);
 450                 }
 451
 452                 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 453                 set_irn_n(use, pos, def);
 454         }
 455
 456         /* Recompute the liveness of the original nodes, the copies and the
 457          * inserted phis. */
 458         if(lv != NULL) {
 459                 int n;
 460
 461                 be_liveness_update(lv, value);
 462                 for(i = 0; i < copies_len; ++i) {
 463                         ir_node *copy = copies[i];
 464                         be_liveness_update(lv, copy);
 465                 }
 466
 467                 n = ARR_LEN(env.new_phis);
 468                 for(i = 0; i < n; ++i) {
 469                         ir_node *phi = env.new_phis[i];
 470                         be_liveness_introduce(lv, phi);
 471                 }
 472         }
 473
 474         clear_using_visited(irg);
 475         clear_using_block_visited(irg);
 476         clear_using_irn_link(irg);
 477
 478         if(!need_new_phis && env.new_phis != NULL) {
 479                 DEL_ARR_F(env.new_phis);
 480                 return NULL;
 481         }
 482         return env.new_phis;
 483 }
 484 #endif
 485
 486 void be_init_ssaconstr(void)
 487 {
 488         FIRM_DBG_REGISTER(dbg, "firm.be.ssaconstr");
 489 }
 490
 491 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_ssaconstr);