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

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