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