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                 ir_node *def;
 339                 int pos      = get_edge_src_pos(edge);
 340
 341                 if(ignore_uses != NULL && ir_nodeset_contains(ignore_uses, use))
 342                         continue;
 343
 344                 if(is_Phi(use)) {
 345                         ir_node *block = get_nodes_block(use);
 346                         ir_node *predblock = get_Block_cfgpred_block(block, pos);
 347                         at = sched_last(predblock);
 348                 }
 349
 350                 def = search_def(&env, at);
 351
 352                 if(def == NULL) {
 353                         panic("no definition found for %+F at position %d\n", use, pos);
 354                 }
 355
 356                 DBG((dbgssa, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 357                 set_irn_n(use, pos, def);
 358         }
 359
 360         /* Recompute the liveness of the original nodes, the copies and the
 361          * inserted phis. */
 362         if(lv != NULL) {
 363                 int n;
 364
 365                 be_liveness_update(lv, value);
 366                 for(i = 0; i < copies_len; ++i) {
 367                         ir_node *copy = copies[i];
 368                         be_liveness_update(lv, copy);
 369                 }
 370
 371                 n = ARR_LEN(env.new_phis);
 372                 for(i = 0; i < n; ++i) {
 373                         ir_node *phi = env.new_phis[i];
 374                         be_liveness_introduce(lv, phi);
 375                 }
 376         }
 377
 378         clear_using_visited(irg);
 379         clear_using_block_visited(irg);
 380         clear_using_irn_link(irg);
 381
 382         if(!need_new_phis && env.new_phis != NULL) {
 383                 DEL_ARR_F(env.new_phis);
 384                 return NULL;
 385         }
 386         return env.new_phis;
 387 }
 388
 389 void be_ssa_constr_set_ignore(const be_dom_front_info_t *domfronts, be_lv_t *lv,
 390                               pset *nodes, pset *ignores)
 391 {
 392         ir_graph *irg;
 393         const ir_edge_t *edge, *next;
 394         int i;
 395         ir_node *block;
 396         waitq *worklist;
 397         ir_node *value;
 398         ssa_constr_env_t env;
 399
 400         foreach_pset(nodes, value) {
 401                 pset_break(nodes);
 402                 break;
 403         }
 404         irg = get_irn_irg(value);
 405
 406         /* We need to collect the phi functions to compute their liveness. */
 407         if(lv != NULL) {
 408                 env.new_phis = NEW_ARR_F(ir_node*, 0);
 409         }
 410
 411         set_using_visited(irg);
 412         set_using_block_visited(irg);
 413         set_using_irn_link(irg);
 414
 415         /* we use the visited flag to indicate blocks in the dominance frontier
 416          * and blocks that already have the relevant value at the end calculated */
 417         inc_irg_visited(irg);
 418         /* We use the block visited flag to indicate blocks in the dominance
 419          * froniter of some values (and this potentially needing phis) */
 420         inc_irg_block_visited(irg);
 421
 422         DBG((dbgssa, LEVEL_1, "Introducing following copies for:\n"));
 423
 424         /* compute iterated dominance frontiers and create lists in the block link
 425          * fields that sort usages by dominance. Blocks in the dominance frontier
 426          * are marked by links back to the block. */
 427         worklist = new_waitq();
 428
 429         foreach_pset(nodes, value) {
 430                 block = get_nodes_block(value);
 431                 env.mode = get_irn_mode(value);
 432
 433                 if(!irn_visited(block)) {
 434                         waitq_put(worklist, block);
 435                 }
 436                 introduce_def_at_block(block, value);
 437                 DBG((dbgssa, LEVEL_1, "\t%+F in %+F\n", value, block));
 438         }
 439
 440         mark_iterated_dominance_frontiers(domfronts, worklist);
 441         del_waitq(worklist);
 442
 443         /*
 444          * Search the valid def for each use and set it.
 445          */
 446         foreach_pset(nodes, value) {
 447                 foreach_out_edge_safe(value, edge, next) {
 448                         ir_node *use = get_edge_src_irn(edge);
 449                         ir_node *at  = use;
 450                         ir_node *def;
 451                         int pos      = get_edge_src_pos(edge);
 452
 453                         if(ignores != NULL && pset_find_ptr(ignores, use))
 454                                 continue;
 455
 456                         if(is_Phi(use)) {
 457                                 ir_node *block = get_nodes_block(use);
 458                                 ir_node *predblock = get_Block_cfgpred_block(block, pos);
 459                                 at = sched_last(predblock);
 460                         }
 461
 462                         def = search_def(&env, at);
 463
 464                         if(def == NULL) {
 465                                 panic("no definition found for %+F input %d\n", use, pos);
 466                         }
 467
 468                         DBG((dbgssa, LEVEL_2, "\t%+F(%d) -> %+F\n", use, pos, def));
 469                         set_irn_n(use, pos, def);
 470                 }
 471         }
 472
 473         /* Recompute the liveness of the original nodes, the copies and the
 474          * inserted phis. */
 475         if(lv != NULL) {
 476                 int n;
 477
 478                 foreach_pset(nodes, value) {
 479                         be_liveness_update(lv, value);
 480                 }
 481
 482                 n = ARR_LEN(env.new_phis);
 483                 for(i = 0; i < n; ++i) {
 484                         ir_node *phi = env.new_phis[i];
 485                         be_liveness_introduce(lv, phi);
 486                 }
 487                 DEL_ARR_F(env.new_phis);
 488         }
 489
 490         clear_using_visited(irg);
 491         clear_using_block_visited(irg);
 492         clear_using_irn_link(irg);
 493 }
 494
 495 /*
 496   ___                     _     ____
 497  |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___ _ __ _ __ ___
 498   | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
 499   | || | | \__ \  __/ |  | |_  |  __/  __/ |  | | | | | |
 500  |___|_| |_|___/\___|_|   \__| |_|   \___|_|  |_| |_| |_|
 501
 502 */
 503
 504 ir_node *insert_Perm_after(const arch_env_t *arch_env,
 505                                                    be_lv_t *lv,
 506                                                    const arch_register_class_t *cls,
 507                                                    be_dom_front_info_t *dom_front,
 508                                                    ir_node *pos)
 509 {
 510         ir_node *bl     = is_Block(pos) ? pos : get_nodes_block(pos);
 511         ir_graph *irg   = get_irn_irg(bl);
 512         pset *live      = pset_new_ptr_default();
 513
 514         ir_node *curr, *irn, *perm, **nodes;
 515         int i, n;
 516
 517         DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
 518
 519         be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
 520
 521         n = pset_count(live);
 522
 523         if(n == 0) {
 524                 del_pset(live);
 525                 return NULL;
 526         }
 527
 528         nodes = xmalloc(n * sizeof(nodes[0]));
 529
 530         DBG((dbg, LEVEL_1, "live:\n"));
 531         for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
 532                 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
 533                 nodes[i] = irn;
 534         }
 535         del_pset(live);
 536
 537         perm = be_new_Perm(cls, irg, bl, n, nodes);
 538         sched_add_after(pos, perm);
 539         free(nodes);
 540
 541         curr = perm;
 542         for (i = 0; i < n; ++i) {
 543                 ir_node *copies[1];
 544                 ir_node *perm_op = get_irn_n(perm, i);
 545                 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
 546
 547                 ir_mode *mode = get_irn_mode(perm_op);
 548                 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
 549                 arch_set_irn_register(arch_env, proj, reg);
 550
 551                 sched_add_after(curr, proj);
 552                 curr = proj;
 553
 554                 copies[0] = proj;
 555
 556                 be_ssa_construction(dom_front, lv, perm_op, 1, copies, NULL, 0);
 557         }
 558
 559         return perm;
 560 }
 561
 562 /**
 563  * Post-block-walker: Find blocks containing only one jump and
 564  * remove them.
 565  */
 566 static void remove_empty_block(ir_node *block, void *data) {
 567         const ir_edge_t *edge, *next;
 568         ir_node *node;
 569         int *changed = data;
 570         ir_node *jump = NULL;
 571
 572         assert(is_Block(block));
 573
 574         if (get_Block_n_cfgpreds(block) != 1)
 575                 return;
 576
 577         sched_foreach(block, node) {
 578                 if (! is_Jmp(node))
 579                         return;
 580                 if (jump != NULL) {
 581                         /* we should never have 2 jumps in a block */
 582                         panic("We should never have 2 jumps in a block");
 583                 }
 584                 jump = node;
 585         }
 586
 587         if (jump == NULL)
 588                 return;
 589
 590         node = get_Block_cfgpred(block, 0);
 591         foreach_out_edge_safe(jump, edge, next) {
 592                 ir_node *block = get_edge_src_irn(edge);
 593                 int     pos    = get_edge_src_pos(edge);
 594
 595                 set_irn_n(block, pos, node);
 596         }
 597
 598         set_Block_cfgpred(block, 0, new_Bad());
 599         be_kill_node(jump);
 600         *changed = 1;
 601 }
 602
 603 /* removes basic blocks that just contain a jump instruction */
 604 int be_remove_empty_blocks(ir_graph *irg) {
 605         int changed = 0;
 606
 607         irg_block_walk_graph(irg, remove_empty_block, NULL, &changed);
 608         if (changed) {
 609                 /* invalidate analysis info */
 610                 set_irg_doms_inconsistent(irg);
 611                 set_irg_extblk_inconsistent(irg);
 612                 set_irg_outs_inconsistent(irg);
 613         }
 614         return changed;
 615 }
 616
 617 void be_init_irgmod(void)
 618 {
 619         FIRM_DBG_REGISTER(dbgssa, "firm.be.ssaconstr");
 620         FIRM_DBG_REGISTER(dbg, "firm.be.irgmod");
 621 }
 622
 623 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_irgmod);