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

   1 /**
   2  * @file
   3  * @brief
   4  * This file contains the following IRG modifications for be routines:
   5  * - backend dominance information
   6  * - SSA construction for a set of nodes
   7  * - insertion of Perm nodes
   8  * - empty block elimination
   9  * - a simple dead node elimination (set inputs of unreachable nodes to BAD)
  10  *
  11  * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
  12  * @date        04.05.2005
  13  * @version     $Id$
  14  * Copyright:   (c) Universitaet Karlsruhe
  15  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  16  */
  17 #ifdef HAVE_CONFIG_H
  18 #include "config.h"
  19 #endif
  20
  21 #include <stdlib.h>
  22
  23 #ifdef HAVE_MALLOC_H
  24  #include <malloc.h>
  25 #endif
  26 #ifdef HAVE_ALLOCA_H
  27  #include <alloca.h>
  28 #endif
  29
  30 #include "hashptr.h"
  31 #include "pdeq.h"
  32 #include "pset.h"
  33 #include "pmap.h"
  34 #include "util.h"
  35 #include "debug.h"
  36 #include "error.h"
  37
  38 #include "irflag_t.h"
  39 #include "ircons_t.h"
  40 #include "irnode_t.h"
  41 #include "ircons_t.h"
  42 #include "irmode_t.h"
  43 #include "irdom_t.h"
  44 #include "iredges_t.h"
  45 #include "irgraph_t.h"
  46 #include "irgopt.h"
  47 #include "irprintf_t.h"
  48 #include "irgwalk.h"
  49
  50 #include "be_t.h"
  51 #include "bechordal_t.h"
  52 #include "bearch.h"
  53 #include "besched_t.h"
  54 #include "belive_t.h"
  55 #include "benode_t.h"
  56 #include "beutil.h"
  57 #include "beinsn_t.h"
  58
  59 #include "beirgmod.h"
  60
  61 DEBUG_ONLY(static firm_dbg_module_t *dbgssa = NULL;)
  62 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  63
  64 /*
  65   ____ ____    _
  66  / ___/ ___|  / \
  67  \___ \___ \ / _ \
  68   ___) |__) / ___ \
  69  |____/____/_/   \_\
  70    ____                _                   _   _
  71   / ___|___  _ __  ___| |_ _ __ _   _  ___| |_(_) ___  _ __
  72  | |   / _ \| '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \
  73  | |__| (_) | | | \__ \ |_| |  | |_| | (__| |_| | (_) | | | |
  74   \____\___/|_| |_|___/\__|_|   \__,_|\___|\__|_|\___/|_| |_|
  75
  76 */
  77
  78 /* The problem: Given a value and a set of "copies" that are known to represent
  79  * the same abstract value, rewire all usages of the original value to their
  80  * closest copy while introducing phis as necessary.
  81  *
  82  * Algorithm: Mark all blocks in the iterated dominance frontiers of the value
  83  * and it's copies. Link the copies ordered by dominance to the blocks.
  84  * The we search for each use all all definitions in the current block, if none
  85  * is found, then we search one in the immediate dominator. If we are in a block
  86  * of the dominance frontier, create a phi and search do the same search for the
  87  * phi arguments.
  88  */
  89
  90 /**
  91  * Calculates the iterated dominance frontier of a set of blocks. Marks the
  92  * blocks as visited. Sets the link fields of the blocks in the dominance
  93  * frontier to the block itself.
  94  */
  95 static
  96 void mark_iterated_dominance_frontiers(const be_dom_front_info_t *domfronts,
  97                                        waitq *worklist)
  98 {
  99         DBG((dbgssa, LEVEL_3, "Dominance Frontier:"));
 100         while(!pdeq_empty(worklist)) {
 101                 int i;
 102                 ir_node *block = waitq_get(worklist);
 103                 ir_node **domfront = be_get_dominance_frontier(domfronts, block);
 104                 int domfront_len = ARR_LEN(domfront);
 105
 106                 for (i = 0; i < domfront_len; ++i) {
 107                         ir_node *y = domfront[i];
 108                         if(Block_block_visited(y))
 109                                 continue;
 110
 111                         if(!irn_visited(y)) {
 112                                 set_irn_link(y, NULL);
 113                                 waitq_put(worklist, y);
 114                         }
 115                         DBG((dbgssa, LEVEL_3, " %+F", y));
 116                         mark_Block_block_visited(y);
 117                 }
 118         }
 119         DBG((dbgssa, LEVEL_3, "\n"));
 120 }
 121
 122 typedef struct ssa_constr_env_t {
 123         ir_node **new_phis;    /**< ARR_F of newly created phis or NULL */
 124         ir_mode *mode;         /**< mode of the value */
 125 } ssa_constr_env_t;
 126
 127 static
 128 ir_node *search_def_end_of_block(ssa_constr_env_t *env, ir_node *block);
 129
 130 static
 131 ir_node *create_phi(ssa_constr_env_t *env, ir_node *block, ir_node *link_with)
 132 {
 133         int i, n_preds = get_Block_n_cfgpreds(block);
 134         ir_graph *irg = get_irn_irg(block);
 135         ir_node *phi;
 136         ir_node **ins = alloca(n_preds * sizeof(ins[0]));
 137
 138         assert(n_preds > 1);
 139
 140         for(i = 0; i < n_preds; ++i) {
 141                 ins[i] = new_r_Unknown(irg, env->mode);
 142         }
 143         phi = new_r_Phi(irg, block, n_preds, ins, env->mode);
 144         if(env->new_phis != NULL) {
 145                 ARR_APP1(ir_node*, env->new_phis, phi);
 146         }
 147
 148         if(env->mode != mode_M) {
 149                 sched_add_after(block, phi);
 150         }
 151
 152         DBG((dbgssa, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, block));
 153         set_irn_link(link_with, phi);
 154         mark_irn_visited(block);
 155
 156         for(i = 0; i < n_preds; ++i) {
 157                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 158                 ir_node *pred_def   = search_def_end_of_block(env, pred_block);
 159
 160                 set_irn_n(phi, i, pred_def);
 161         }
 162
 163         return phi;
 164 }
 165
 166 static
 167 ir_node *get_def_at_idom(ssa_constr_env_t *env, ir_node *block)
 168 {
 169         ir_node *dom = get_Block_idom(block);
 170         ir_node *def = search_def_end_of_block(env, dom);
 171
 172         return def;
 173 }
 174
 175 static
 176 ir_node *search_def_end_of_block(ssa_constr_env_t *env, ir_node *block)
 177 {
 178         if(irn_visited(block)) {
 179                 assert(get_irn_link(block) != NULL);
 180                 return get_irn_link(block);
 181         } else if(Block_block_visited(block)) {
 182                 return create_phi(env, block, block);
 183         } else {
 184                 ir_node *def = get_def_at_idom(env, block);
 185 #if 1
 186                 mark_irn_visited(block);
 187                 set_irn_link(block, def);
 188 #endif
 189
 190                 return def;
 191         }
 192 }
 193
 194 static
 195 ir_node *search_def(ssa_constr_env_t *env, ir_node *at)
 196 {
 197         ir_node *block = get_nodes_block(at);
 198         ir_node *node;
 199         ir_node *def;
 200
 201         DBG((dbgssa, LEVEL_3, "\t...searching def at %+F\n", at));
 202
 203         /* no defs in the current block we can do the normal searching */
 204         if(!irn_visited(block) && !Block_block_visited(block)) {
 205                 DBG((dbgssa, LEVEL_3, "\t...continue at idom\n"));
 206                 return get_def_at_idom(env, block);
 207         }
 208
 209         /* there are defs in the current block, walk the linked list to find
 210            the one immediately dominating us
 211          */
 212         node = block;
 213         def  = get_irn_link(node);
 214         while(def != NULL) {
 215 #if 0
 216                 assert(get_nodes_block(def) == block);
 217                 if(!value_dominates_intrablock(at, def)) {
 218                         DBG((dbgssa, LEVEL_3, "\t...found dominating def %+F\n", def));
 219                         return def;
 220                 }
 221 #else
 222                 if(!value_dominates(at, def)) {
 223                         DBG((dbgssa, LEVEL_3, "\t...found dominating def %+F\n", def));
 224                         return def;
 225                 }
 226 #endif
 227                 node = def;
 228                 def  = get_irn_link(node);
 229         }
 230
 231         /* block in dominance frontier? create a phi then */
 232         if(Block_block_visited(block)) {
 233                 DBG((dbgssa, LEVEL_3, "\t...create phi at block %+F\n", block));
 234                 assert(!is_Phi(node));
 235                 return create_phi(env, block, node);
 236         }
 237
 238
 239         DBG((dbgssa, LEVEL_3, "\t...continue at idom (after checking block)\n"));
 240         return get_def_at_idom(env, block);
 241 }
 242
 243 /**
 244  * Adds a definition into the link field of the block. The definitions are
 245  * sorted by dominance. A non-visited block means no definition has been
 246  * inserted yet.
 247  */
 248 static
 249 void introduce_def_at_block(ir_node *block, ir_node *def)
 250 {
 251         if(irn_visited(block)) {
 252                 ir_node *node = block;
 253                 ir_node *current_def;
 254
 255                 while(1) {
 256                         current_def = get_irn_link(node);
 257                         if(current_def == def) {
 258                                 /* already in block */
 259                                 return;
 260                         }
 261                         if(current_def == NULL)
 262                                 break;
 263                         if(value_dominates(current_def, def))
 264                                 break;
 265                         node = current_def;
 266                 }
 267
 268                 set_irn_link(node, def);
 269                 set_irn_link(def, current_def);
 270         } else {
 271                 set_irn_link(block, def);
 272                 set_irn_link(def, NULL);
 273                 mark_irn_visited(block);
 274         }
 275 }
 276
 277 ir_node **be_ssa_construction(const be_dom_front_info_t *domfronts, be_lv_t *lv,
 278                          ir_node *value, int copies_len, ir_node **copies,
 279                          const ir_nodeset_t *ignore_uses, int need_new_phis)
 280 {
 281         ir_graph *irg = get_irn_irg(value);
 282         const ir_edge_t *edge, *next;
 283         int i;
 284         ir_node *block;
 285         waitq *worklist;
 286         ssa_constr_env_t env;
 287
 288         /* We need to collect the phi functions to compute their liveness. */
 289         if(lv != NULL || need_new_phis) {
 290                 env.new_phis = NEW_ARR_F(ir_node*, 0);
 291         } else {
 292                 env.new_phis = NULL;
 293         }
 294         env.mode = get_irn_mode(value);
 295
 296         set_using_visited(irg);
 297         set_using_block_visited(irg);
 298         set_using_irn_link(irg);
 299
 300         /* we use the visited flag to indicate blocks in the dominance frontier
 301          * and blocks that already have the relevant value at the end calculated */
 302         inc_irg_visited(irg);
 303         /* We use the block visited flag to indicate blocks in the dominance
 304          * froniter of some values (and this potentially needing phis) */
 305         inc_irg_block_visited(irg);
 306
 307         DBG((dbgssa, LEVEL_1, "Introducing following copies for: %+F\n", value));
 308         /* compute iterated dominance frontiers and create lists in the block link
 309          * fields that sort usages by dominance. Blocks in the dominance frontier
 310          * are marked by links back to the block. */
 311         worklist = new_waitq();
 312
 313         block = get_nodes_block(value);
 314         introduce_def_at_block(block, value);
 315         waitq_put(worklist, block);
 316
 317         for(i = 0; i < copies_len; ++i) {
 318                 ir_node *copy = copies[i];
 319                 block = get_nodes_block(copy);
 320
 321                 if(!irn_visited(block)) {
 322                         waitq_put(worklist, block);
 323                 }
 324                 introduce_def_at_block(block, copy);
 325                 DBG((dbgssa, LEVEL_1, "\t%+F in %+F\n", copy, block));
 326         }
 327
 328         mark_iterated_dominance_frontiers(domfronts, worklist);
 329         del_waitq(worklist);
 330
 331         DBG((dbgssa, LEVEL_2, "New Definitions:\n"));
 332         /*
 333          * Search the valid def for each use and set it.
 334          */
 335         foreach_out_edge_safe(value, edge, next) {
 336                 ir_node *use = get_edge_src_irn(edge);
 337                 ir_node *at  = use;
 338                 int pos      = get_edge_src_pos(edge);
 339
 340                 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
 341                         continue;
 342
 343                 if(is_Phi(use)) {
 344                         ir_node *block = get_nodes_block(use);
 345                         ir_node *predblock = get_Block_cfgpred_block(block, pos);
 346                         at = sched_last(predblock);
 347                 }
 348
 349                 ir_node *def = search_def(&env, at);
 350
 351                 if(def == NULL) {
 352                         panic("no definition found for %+F at position %d\n", use, pos);
 353                 }
 354
 355                 DBG((dbgssa, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 356                 set_irn_n(use, pos, def);
 357         }
 358
 359         /* Recompute the liveness of the original nodes, the copies and the
 360          * inserted phis. */
 361         if(lv != NULL) {
 362                 int n;
 363
 364                 be_liveness_update(lv, value);
 365                 for(i = 0; i < copies_len; ++i) {
 366                         ir_node *copy = copies[i];
 367                         be_liveness_update(lv, copy);
 368                 }
 369
 370                 n = ARR_LEN(env.new_phis);
 371                 for(i = 0; i < n; ++i) {
 372                         ir_node *phi = env.new_phis[i];
 373                         be_liveness_introduce(lv, phi);
 374                 }
 375         }
 376
 377         clear_using_visited(irg);
 378         clear_using_block_visited(irg);
 379         clear_using_irn_link(irg);
 380
 381         if(!need_new_phis && env.new_phis != NULL) {
 382                 DEL_ARR_F(env.new_phis);
 383                 return NULL;
 384         }
 385         return env.new_phis;
 386 }
 387
 388 void be_ssa_constr_set_ignore(const be_dom_front_info_t *domfronts, be_lv_t *lv,
 389                               pset *nodes, pset *ignores)
 390 {
 391         ir_graph *irg;
 392         const ir_edge_t *edge, *next;
 393         int i;
 394         ir_node *block;
 395         waitq *worklist;
 396         ir_node *value;
 397         ssa_constr_env_t env;
 398
 399         foreach_pset(nodes, value) {
 400                 pset_break(nodes);
 401                 break;
 402         }
 403         irg = get_irn_irg(value);
 404
 405         /* We need to collect the phi functions to compute their liveness. */
 406         if(lv != NULL) {
 407                 env.new_phis = NEW_ARR_F(ir_node*, 0);
 408         }
 409
 410         set_using_visited(irg);
 411         set_using_block_visited(irg);
 412         set_using_irn_link(irg);
 413
 414         /* we use the visited flag to indicate blocks in the dominance frontier
 415          * and blocks that already have the relevant value at the end calculated */
 416         inc_irg_visited(irg);
 417         /* We use the block visited flag to indicate blocks in the dominance
 418          * froniter of some values (and this potentially needing phis) */
 419         inc_irg_block_visited(irg);
 420
 421         DBG((dbgssa, LEVEL_1, "Introducing following copies for:\n"));
 422
 423         /* compute iterated dominance frontiers and create lists in the block link
 424          * fields that sort usages by dominance. Blocks in the dominance frontier
 425          * are marked by links back to the block. */
 426         worklist = new_waitq();
 427
 428         foreach_pset(nodes, value) {
 429                 block = get_nodes_block(value);
 430                 env.mode = get_irn_mode(value);
 431
 432                 if(!irn_visited(block)) {
 433                         waitq_put(worklist, block);
 434                 }
 435                 introduce_def_at_block(block, value);
 436                 DBG((dbgssa, LEVEL_1, "\t%+F in %+F\n", value, block));
 437         }
 438
 439         mark_iterated_dominance_frontiers(domfronts, worklist);
 440         del_waitq(worklist);
 441
 442         /*
 443          * Search the valid def for each use and set it.
 444          */
 445         foreach_pset(nodes, value) {
 446                 foreach_out_edge_safe(value, edge, next) {
 447                         ir_node *use = get_edge_src_irn(edge);
 448                         ir_node *at  = use;
 449                         int pos      = get_edge_src_pos(edge);
 450
 451                         if(ignores != NULL && pset_find_ptr(ignores, use))
 452                                 continue;
 453
 454                         if(is_Phi(use)) {
 455                                 ir_node *block = get_nodes_block(use);
 456                                 ir_node *predblock = get_Block_cfgpred_block(block, pos);
 457                                 at = sched_last(predblock);
 458                         }
 459
 460                         ir_node *def = search_def(&env, at);
 461
 462                         if(def == NULL) {
 463                                 panic("no definition found for %+F input %d\n", use, pos);
 464                         }
 465
 466                         DBG((dbgssa, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 467                         set_irn_n(use, pos, def);
 468                 }
 469         }
 470
 471         /* Recompute the liveness of the original nodes, the copies and the
 472          * inserted phis. */
 473         if(lv != NULL) {
 474                 int n;
 475
 476                 foreach_pset(nodes, value) {
 477                         be_liveness_update(lv, value);
 478                 }
 479
 480                 n = ARR_LEN(env.new_phis);
 481                 for(i = 0; i < n; ++i) {
 482                         ir_node *phi = env.new_phis[i];
 483                         be_liveness_introduce(lv, phi);
 484                 }
 485                 DEL_ARR_F(env.new_phis);
 486         }
 487
 488         clear_using_visited(irg);
 489         clear_using_block_visited(irg);
 490         clear_using_irn_link(irg);
 491 }
 492
 493 /*
 494   ___                     _     ____
 495  |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___ _ __ _ __ ___
 496   | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
 497   | || | | \__ \  __/ |  | |_  |  __/  __/ |  | | | | | |
 498  |___|_| |_|___/\___|_|   \__| |_|   \___|_|  |_| |_| |_|
 499
 500 */
 501
 502 ir_node *insert_Perm_after(const arch_env_t *arch_env,
 503                                                    be_lv_t *lv,
 504                                                    const arch_register_class_t *cls,
 505                                                    be_dom_front_info_t *dom_front,
 506                                                    ir_node *pos)
 507 {
 508         ir_node *bl     = is_Block(pos) ? pos : get_nodes_block(pos);
 509         ir_graph *irg   = get_irn_irg(bl);
 510         pset *live      = pset_new_ptr_default();
 511
 512         ir_node *curr, *irn, *perm, **nodes;
 513         int i, n;
 514
 515         DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
 516
 517         be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
 518
 519         n = pset_count(live);
 520
 521         if(n == 0) {
 522                 del_pset(live);
 523                 return NULL;
 524         }
 525
 526         nodes = xmalloc(n * sizeof(nodes[0]));
 527
 528         DBG((dbg, LEVEL_1, "live:\n"));
 529         for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
 530                 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
 531                 nodes[i] = irn;
 532         }
 533         del_pset(live);
 534
 535         perm = be_new_Perm(cls, irg, bl, n, nodes);
 536         sched_add_after(pos, perm);
 537         free(nodes);
 538
 539         curr = perm;
 540         for (i = 0; i < n; ++i) {
 541                 ir_node *copies[1];
 542                 ir_node *perm_op = get_irn_n(perm, i);
 543                 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
 544
 545                 ir_mode *mode = get_irn_mode(perm_op);
 546                 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
 547                 arch_set_irn_register(arch_env, proj, reg);
 548
 549                 sched_add_after(curr, proj);
 550                 curr = proj;
 551
 552                 copies[0] = proj;
 553
 554                 be_ssa_construction(dom_front, lv, perm_op, 1, copies, NULL, 0);
 555         }
 556
 557         return perm;
 558 }
 559
 560 /**
 561  * Post-block-walker: Find blocks containing only one jump and
 562  * remove them.
 563  */
 564 static void remove_empty_block(ir_node *block, void *data) {
 565         const ir_edge_t *edge, *next;
 566         ir_node *node;
 567         int *changed = data;
 568         ir_node *jump = NULL;
 569
 570         assert(is_Block(block));
 571
 572         if (get_Block_n_cfgpreds(block) != 1)
 573                 return;
 574
 575         sched_foreach(block, node) {
 576                 if (! is_Jmp(node))
 577                         return;
 578                 if (jump != NULL) {
 579                         /* we should never have 2 jumps in a block */
 580                         panic("We should never have 2 jumps in a block");
 581                 }
 582                 jump = node;
 583         }
 584
 585         if (jump == NULL)
 586                 return;
 587
 588         node = get_Block_cfgpred(block, 0);
 589         foreach_out_edge_safe(jump, edge, next) {
 590                 ir_node *block = get_edge_src_irn(edge);
 591                 int     pos    = get_edge_src_pos(edge);
 592
 593                 set_irn_n(block, pos, node);
 594         }
 595
 596         set_Block_cfgpred(block, 0, new_Bad());
 597         be_kill_node(jump);
 598         *changed = 1;
 599 }
 600
 601 /* removes basic blocks that just contain a jump instruction */
 602 int be_remove_empty_blocks(ir_graph *irg) {
 603         int changed = 0;
 604
 605         irg_block_walk_graph(irg, remove_empty_block, NULL, &changed);
 606         if (changed) {
 607                 /* invalidate analysis info */
 608                 set_irg_doms_inconsistent(irg);
 609                 set_irg_extblk_inconsistent(irg);
 610                 set_irg_outs_inconsistent(irg);
 611         }
 612         return changed;
 613 }
 614
 615 void be_init_irgmod(void)
 616 {
 617         FIRM_DBG_REGISTER(dbgssa, "firm.be.ssaconstr");
 618         FIRM_DBG_REGISTER(dbg, "firm.be.irgmod");
 619 }
 620
 621 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_irgmod);