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

   1 #ifdef HAVE_CONFIG_H
   2 #include "config.h"
   3 #endif
   4
   5 #include <stdlib.h>
   6
   7 #ifdef HAVE_MALLOC_H
   8  #include <malloc.h>
   9 #endif
  10 #ifdef HAVE_ALLOCA_H
  11  #include <alloca.h>
  12 #endif
  13
  14 #include "hashptr.h"
  15 #include "pdeq.h"
  16 #include "pset.h"
  17 #include "pmap.h"
  18 #include "util.h"
  19 #include "debug.h"
  20
  21 #include "irflag_t.h"
  22 #include "ircons_t.h"
  23 #include "irnode_t.h"
  24 #include "ircons_t.h"
  25 #include "irmode_t.h"
  26 #include "irdom_t.h"
  27 #include "iredges_t.h"
  28 #include "irgopt.h"
  29 #include "irprintf_t.h"
  30 #include "irgwalk.h"
  31
  32 #include "be_t.h"
  33 #include "bechordal_t.h"
  34 #include "bearch.h"
  35 #include "besched_t.h"
  36 #include "belive_t.h"
  37 #include "benode_t.h"
  38 #include "beutil.h"
  39 #include "beinsn_t.h"
  40
  41 #include "beirgmod.h"
  42
  43 #define DBG_MODULE "firm.be.irgmod"
  44 #define DBG_LEVEL SET_LEVEL_0
  45
  46 /*
  47   ____                  _
  48  |  _ \  ___  _ __ ___ (_)_ __   __ _ _ __   ___ ___
  49  | | | |/ _ \| '_ ` _ \| | '_ \ / _` | '_ \ / __/ _ \
  50  | |_| | (_) | | | | | | | | | | (_| | | | | (_|  __/
  51  |____/ \___/|_| |_| |_|_|_| |_|\__,_|_| |_|\___\___|
  52  |  ___| __ ___  _ __ | |_(_) ___ _ __ ___
  53  | |_ | '__/ _ \| '_ \| __| |/ _ \ '__/ __|
  54  |  _|| | | (_) | | | | |_| |  __/ |  \__ \
  55  |_|  |_|  \___/|_| |_|\__|_|\___|_|  |___/
  56
  57 */
  58
  59
  60 struct _dom_front_info_t {
  61   pmap *df_map;
  62 };
  63
  64 /**
  65  * A wrapper for get_Block_idom.
  66  * This function returns the block itself, if the block is the start
  67  * block. Returning NULL would make any != comparison true which
  68  * suggests, that the start block is dominated by some other node.
  69  * @param bl The block.
  70  * @return The immediate dominator of the block.
  71  */
  72 static INLINE ir_node *get_idom(ir_node *bl)
  73 {
  74   ir_node *idom = get_Block_idom(bl);
  75   return idom == NULL ? bl : idom;
  76 }
  77
  78 static void compute_df(ir_node *n, pmap *df_map)
  79 {
  80   ir_node *c;
  81   const ir_edge_t *edge;
  82   pset *df = pset_new_ptr_default();
  83
  84   /* Add local dominance frontiers */
  85   foreach_block_succ(n, edge) {
  86     ir_node *y = edge->src;
  87
  88     if(get_idom(y) != n)
  89       pset_insert_ptr(df, y);
  90   }
  91
  92   /*
  93    * Go recursively down the dominance tree and add all blocks
  94    * int the dominance frontiers of the children, which are not
  95    * dominated by the given block.
  96    */
  97   for(c = get_Block_dominated_first(n); c; c = get_Block_dominated_next(c)) {
  98     pset *df_c;
  99     ir_node *w;
 100
 101     compute_df(c, df_map);
 102     df_c = pmap_get(df_map, c);
 103
 104     for(w = pset_first(df_c); w; w = pset_next(df_c)) {
 105       if(get_idom(w) != n)
 106         pset_insert_ptr(df, w);
 107     }
 108   }
 109
 110   pmap_insert(df_map, n, df);
 111
 112 }
 113
 114 dom_front_info_t *be_compute_dominance_frontiers(ir_graph *irg)
 115 {
 116   dom_front_info_t *info = xmalloc(sizeof(*info));
 117
 118   edges_assure(irg);
 119   info->df_map = pmap_create();
 120   compute_doms(irg);
 121   compute_df(get_irg_start_block(irg), info->df_map);
 122
 123   return info;
 124 }
 125
 126 void be_free_dominance_frontiers(dom_front_info_t *info)
 127 {
 128   pmap_entry *ent;
 129
 130   for(ent = pmap_first(info->df_map); ent; ent = pmap_next(info->df_map))
 131     del_pset(ent->value);
 132
 133   pmap_destroy(info->df_map);
 134   free(info);
 135 }
 136
 137 pset *be_get_dominance_frontier(dom_front_info_t *info, ir_node *block)
 138 {
 139   return pmap_get(info->df_map, block);
 140 }
 141
 142 static void determine_phi_blocks(pset *copies, pset *copy_blocks, pset *phi_blocks, dom_front_info_t *df_info)
 143 {
 144         ir_node *bl;
 145         pdeq *worklist = new_pdeq();
 146         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 147
 148         /*
 149          * Fill the worklist queue and the rest of the orig blocks array.
 150          */
 151         for(bl = pset_first(copy_blocks); bl; bl = pset_next(copy_blocks)) {
 152                 pdeq_putr(worklist, bl);
 153         }
 154
 155         while (!pdeq_empty(worklist)) {
 156                 ir_node *bl = pdeq_getl(worklist);
 157                 pset *df    = be_get_dominance_frontier(df_info, bl);
 158
 159                 ir_node *y;
 160
 161                 DBG((dbg, LEVEL_3, "dom front of %+F\n", bl));
 162                 DEBUG_ONLY(
 163                         for (y = pset_first(df); y; y = pset_next(df))
 164                                 DBG((dbg, LEVEL_3, "\t%+F\n", y))
 165                 );
 166
 167                 for(y = pset_first(df); y; y = pset_next(df)) {
 168                         if(!pset_find_ptr(phi_blocks, y)) {
 169                                 pset_insert_ptr(phi_blocks, y);
 170
 171                                 /*
 172                                  * Clear the link field of a possible phi block, since
 173                                  * the possibly created phi will be stored there. See,
 174                                  * search_def()
 175                                  */
 176                                 set_irn_link(y, NULL);
 177
 178                                 if(!pset_find_ptr(copy_blocks, y))
 179                                         pdeq_putr(worklist, y);
 180                         }
 181                 }
 182         }
 183
 184         del_pdeq(worklist);
 185 }
 186
 187 /*
 188   ____ ____    _
 189  / ___/ ___|  / \
 190  \___ \___ \ / _ \
 191   ___) |__) / ___ \
 192  |____/____/_/   \_\
 193    ____                _                   _   _
 194   / ___|___  _ __  ___| |_ _ __ _   _  ___| |_(_) ___  _ __
 195  | |   / _ \| '_ \/ __| __| '__| | | |/ __| __| |/ _ \| '_ \
 196  | |__| (_) | | | \__ \ |_| |  | |_| | (__| |_| | (_) | | | |
 197   \____\___/|_| |_|___/\__|_|   \__,_|\___|\__|_|\___/|_| |_|
 198
 199 */
 200
 201 /**
 202  * Find the copy of the given original node whose value is 'active'
 203  * at a usage.
 204  *
 205  * The usage is given as a node and a position. Initially, the given operand
 206  * points to a node for which copies were introduced. We have to find
 207  * the valid copy for this usage. This is done by traversing the
 208  * dominance tree upwards. If the usage is a phi function, we start
 209  * traversing from the predecessor block which corresponds to the phi
 210  * usage.
 211  *
 212  * @param usage       The node which uses the original node.
 213  * @param pos         The position of the argument which corresponds to the original node.
 214  * @param copies      A set containing all node which are copies from the original node.
 215  * @param copy_blocks A set containing all basic block in which copies of the original node are located.
 216  * @param phis        A set where all created phis are recorded.
 217  * @param phi_blocks  A set of all blocks where Phis shall be inserted (iterated dominance frontier).
 218  * @param mode        The mode for the Phi if one has to be created.
 219  * @return            The valid copy for usage.
 220  */
 221 static ir_node *search_def(ir_node *usage, int pos, pset *copies, pset *copy_blocks, pset *phis, pset *phi_blocks, ir_mode *mode)
 222 {
 223         ir_node *curr_bl;
 224         ir_node *start_irn;
 225         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 226
 227         curr_bl = get_nodes_block(usage);
 228
 229         DBG((dbg, LEVEL_1, "Searching valid def for use %+F at pos %d\n", usage, pos));
 230         /*
 231          * If the usage is in a phi node, search the copy in the
 232          * predecessor denoted by pos.
 233          */
 234         if(is_Phi(usage)) {
 235                 curr_bl = get_Block_cfgpred_block(curr_bl, pos);
 236                 start_irn = sched_last(curr_bl);
 237         } else {
 238                 start_irn = sched_prev(usage);
 239         }
 240
 241         /*
 242          * Traverse the dominance tree upwards from the
 243          * predecessor block of the usage.
 244          */
 245         while(curr_bl != NULL) {
 246                 ir_node *phim;
 247
 248             /*
 249                  * If this block contains a copy, search the block
 250                  * instruction by instruction. If nothing is found
 251                  * search for a not scheduled PhiM.
 252                  */
 253                 if(pset_find_ptr(copy_blocks, curr_bl)) {
 254                         ir_node *irn;
 255
 256                         /* Look at each instruction from last to first. */
 257                         sched_foreach_reverse_from(start_irn, irn) {
 258
 259                                 /* Take the first copy we find. */
 260                                 if(pset_find_ptr(copies, irn))
 261                                         return irn;
 262                         }
 263
 264                         for(phim = pset_first(copies); phim; phim = pset_next(copies)) {
 265                                 if(!is_Phi(phim) || !(get_irn_mode(phim) == mode_M))
 266                                         continue;
 267
 268                                 if(get_nodes_block(phim) == curr_bl) {
 269                                         pset_break(copies);
 270                                         return phim;
 271                                 }
 272                         }
 273                 }
 274
 275                 if(pset_find_ptr(phi_blocks, curr_bl)) {
 276                         ir_node *phi = get_irn_link(curr_bl);
 277
 278                         if(phi == NULL) {
 279                                 int i, n_preds = get_irn_arity(curr_bl);
 280                                 ir_graph *irg = get_irn_irg(curr_bl);
 281                                 ir_node **ins = alloca(n_preds * sizeof(ins[0]));
 282
 283                                 for(i = 0; i < n_preds; ++i)
 284                                         ins[i] = new_r_Bad(irg);
 285
 286                                 phi = new_r_Phi(irg, curr_bl, n_preds, ins, mode);
 287                                 DBG((dbg, LEVEL_2, "\tcreating phi %+F in %+F\n", phi, curr_bl));
 288
 289                                 set_irn_link(curr_bl, phi);
 290                                 if(mode != mode_M)
 291                                         sched_add_after(curr_bl, phi);
 292
 293                                 for(i = 0; i < n_preds; ++i) {
 294                                         ir_node *arg = search_def(phi, i, copies, copy_blocks, phis, phi_blocks, mode);
 295                                         if(arg == NULL) {
 296                                                 ir_node *irn;
 297
 298                                                 ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", phi, i);
 299                                                 for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
 300                                                         ir_fprintf(stderr, "%+F ", irn);
 301                                                 }
 302                                                 ir_fprintf(stderr, "\n\n");
 303                                                 assert(arg && "no definition found");
 304                                         }
 305                                         DBG((dbg, LEVEL_2, "\t\t%+F(%d) -> %+F\n", phi, i, arg));
 306                                         set_irn_n(phi, i, arg);
 307                                 }
 308
 309                                 if(phis != NULL)
 310                                         pset_insert_ptr(phis, phi);
 311                         }
 312
 313                         return phi;
 314                 }
 315
 316                 /* If were not done yet, look in the immediate dominator */
 317                 curr_bl = get_Block_idom(curr_bl);
 318                 if(curr_bl)
 319                         start_irn = sched_last(curr_bl);
 320         }
 321
 322         return NULL;
 323 }
 324
 325 static void fix_usages(pset *copies, pset *copy_blocks, pset *phi_blocks, pset *phis, pset *ignore_uses)
 326 {
 327         int n_outs = 0;
 328         struct obstack obst;
 329         ir_node *irn;
 330         int i;
 331         struct out {
 332                 ir_node *irn;
 333                 int pos;
 334         } *outs;
 335
 336         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 337
 338         obstack_init(&obst);
 339
 340         /*
 341          * Put all outs into an array.
 342          * This is necessary, since the outs would be modified while
 343          * iterating on them what could bring the outs module in trouble.
 344          */
 345         for (irn = pset_first(copies); irn; irn = pset_next(copies)) {
 346                 const ir_edge_t *edge;
 347                 foreach_out_edge(irn, edge) {
 348                         if (!pset_find_ptr(ignore_uses, get_edge_src_irn(edge))) {
 349                                 struct out tmp;
 350                                 tmp.irn = get_edge_src_irn(edge);
 351                                 tmp.pos = get_edge_src_pos(edge);
 352                                 obstack_grow(&obst, &tmp, sizeof(tmp));
 353                                 n_outs++;
 354                         }
 355                 }
 356         }
 357         outs = obstack_finish(&obst);
 358
 359         /*
 360          * Search the valid def for each out and set it.
 361          */
 362         for(i = 0; i < n_outs; ++i) {
 363                 ir_node *irn  = outs[i].irn;
 364                 int pos       = outs[i].pos;
 365                 ir_mode *mode = get_irn_mode(get_irn_n(irn, pos));
 366
 367                 ir_node *def;
 368
 369                 def = search_def(irn, pos, copies, copy_blocks, phis, phi_blocks, mode);
 370                 DBG((dbg, LEVEL_2, "\t%+F(%d) -> %+F\n", irn, pos, def));
 371
 372                 if(def == NULL) {
 373                         ir_fprintf(stderr, "no definition found for %+F at position %d\nCopies: ", irn, pos);
 374                         for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
 375                                 ir_fprintf(stderr, "%+F ", irn);
 376                         }
 377                         ir_fprintf(stderr, "\n\n");
 378                         assert(def && "no definition found");
 379                 }
 380                 set_irn_n(irn, pos, def);
 381         }
 382
 383         obstack_free(&obst, NULL);
 384 }
 385
 386 #if 0
 387 /**
 388  * Remove phis which are not necessary.
 389  * During place_phi_functions() phi functions are put on the dominance
 390  * frontiers blindly. However some of them will never be used (these
 391  * have at least one predecessor which is NULL, see search_def() for
 392  * this case). Since place_phi_functions() enters them into the
 393  * schedule, we have to remove them from there.
 394  *
 395  * @param copies The set of all copies made (including the phi functions).
 396  */
 397 static void remove_odd_phis(pset *copies, pset *unused_copies)
 398 {
 399         ir_node *irn;
 400
 401         for(irn = pset_first(copies); irn; irn = pset_next(copies)) {
 402                 if(is_Phi(irn)) {
 403                         int i, n;
 404                         int illegal = 0;
 405
 406                         assert(sched_is_scheduled(irn) && "phi must be scheduled");
 407                         for(i = 0, n = get_irn_arity(irn); i < n && !illegal; ++i)
 408                                 illegal = get_irn_n(irn, i) == NULL;
 409
 410                         if(illegal) {
 411                                 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
 412                                         set_irn_n(irn, i, new_Bad());
 413                                 sched_remove(irn);
 414                         }
 415                 }
 416         }
 417
 418         for(irn = pset_first(unused_copies); irn; irn = pset_next(unused_copies)) {
 419                 for(i = 0, n = get_irn_arity(irn); i < n; ++i)
 420                         set_irn_n(irn, i, new_Bad());
 421                 sched_remove(irn);
 422         }
 423 }
 424 #endif
 425
 426 void be_ssa_constr_phis_ignore(dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *phis, pset *ignore_uses)
 427 {
 428         pset *irns = pset_new_ptr(n);
 429         int i;
 430
 431         for(i = 0; i < n; ++i)
 432                 pset_insert_ptr(irns, nodes[i]);
 433         be_ssa_constr_set_phis_ignore(info, lv, irns, phis, ignore_uses);
 434         del_pset(irns);
 435 }
 436
 437 void be_ssa_constr_ignore(dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[], pset *ignore_uses)
 438 {
 439         be_ssa_constr_phis_ignore(info, lv, n, nodes, NULL, ignore_uses);
 440 }
 441
 442 void be_ssa_constr(dom_front_info_t *info, be_lv_t *lv, int n, ir_node *nodes[])
 443 {
 444         pset *empty_set = be_empty_set();
 445         be_ssa_constr_ignore(info, lv, n, nodes, empty_set);
 446 }
 447
 448 void be_ssa_constr_set_phis_ignore(dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis, pset *ignore_uses)
 449 {
 450         int n                  = pset_count(nodes);
 451         pset *blocks           = pset_new_ptr(n);
 452         pset *phi_blocks       = pset_new_ptr(n);
 453         int save_optimize      = get_optimize();
 454         int save_normalize     = get_opt_normalize();
 455         int phis_set_created   = 0;
 456         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, DBG_MODULE);
 457
 458         ir_node *irn;
 459
 460         /* We need to collect the phi functions to compute their liveness. */
 461         if(lv && !phis) {
 462                 phis_set_created = 1;
 463                 phis = pset_new_ptr_default();
 464         }
 465
 466         DBG((dbg, LEVEL_1, "Introducing following copies for:\n"));
 467
 468         /* Fill the sets. */
 469         for(irn = pset_first(nodes); irn; irn = pset_next(nodes)) {
 470                 ir_node *bl = get_nodes_block(irn);
 471                 pset_insert_ptr(blocks, bl);
 472                 DBG((dbg, LEVEL_1, "\t%+F in %+F\n", irn, bl));
 473         }
 474
 475         /*
 476          * Disable optimization so that the phi functions do not
 477          * disappear.
 478          */
 479         set_optimize(0);
 480         set_opt_normalize(0);
 481
 482         /*
 483          * Place the phi functions and reroute the usages.
 484          */
 485         determine_phi_blocks(nodes, blocks, phi_blocks, df);
 486         fix_usages(nodes, blocks, phi_blocks, phis, ignore_uses);
 487
 488         /* reset the optimizations */
 489         set_optimize(save_optimize);
 490         set_opt_normalize(save_normalize);
 491
 492         del_pset(phi_blocks);
 493         del_pset(blocks);
 494
 495         /* Recompute the liveness (if wanted) of the original nodes, the copies and the inserted phis. */
 496         if(lv) {
 497 #if 1
 498                 foreach_pset(nodes, irn)
 499                         be_liveness_update(lv, irn);
 500
 501                 foreach_pset(phis, irn)
 502                         be_liveness_introduce(lv, irn);
 503 #else
 504                 be_liveness_recompute(lv);
 505 #endif
 506         }
 507
 508         /* Free the phi set of we created it. */
 509         if(phis_set_created)
 510                 del_pset(phis);
 511
 512 }
 513
 514 void be_ssa_constr_set_phis(dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *phis)
 515 {
 516         pset *empty_set = be_empty_set();
 517         be_ssa_constr_set_phis_ignore(df, lv, nodes, phis, empty_set);
 518 }
 519
 520 void be_ssa_constr_set_ignore(dom_front_info_t *df, be_lv_t *lv, pset *nodes, pset *ignore_uses)
 521 {
 522         be_ssa_constr_set_phis_ignore(df, lv, nodes, NULL, ignore_uses);
 523 }
 524
 525 void be_ssa_constr_set(dom_front_info_t *info, be_lv_t *lv, pset *nodes)
 526 {
 527         pset *empty_set = be_empty_set();
 528         be_ssa_constr_set_ignore(info, lv, nodes, empty_set);
 529 }
 530
 531 /*
 532   ___                     _     ____
 533  |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___ _ __ _ __ ___
 534   | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
 535   | || | | \__ \  __/ |  | |_  |  __/  __/ |  | | | | | |
 536  |___|_| |_|___/\___|_|   \__| |_|   \___|_|  |_| |_| |_|
 537
 538 */
 539
 540 ir_node *insert_Perm_after(const arch_env_t *arch_env,
 541                                                    be_lv_t *lv,
 542                                                    const arch_register_class_t *cls,
 543                                                    dom_front_info_t *dom_front,
 544                                                    ir_node *pos)
 545 {
 546         ir_node *bl     = is_Block(pos) ? pos : get_nodes_block(pos);
 547         ir_graph *irg   = get_irn_irg(bl);
 548         pset *live      = pset_new_ptr_default();
 549         FIRM_DBG_REGISTER(firm_dbg_module_t *dbg, "be.node");
 550
 551         ir_node *curr, *irn, *perm, **nodes;
 552         int i, n;
 553
 554         DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));
 555
 556         be_liveness_nodes_live_at(lv, arch_env, cls, pos, live);
 557
 558         n = pset_count(live);
 559
 560         if(n == 0) {
 561                 del_pset(live);
 562                 return NULL;
 563         }
 564
 565         nodes = xmalloc(n * sizeof(nodes[0]));
 566
 567         DBG((dbg, LEVEL_1, "live:\n"));
 568         for(irn = pset_first(live), i = 0; irn; irn = pset_next(live), i++) {
 569                 DBG((dbg, LEVEL_1, "\t%+F\n", irn));
 570                 nodes[i] = irn;
 571         }
 572         del_pset(live);
 573
 574         perm = be_new_Perm(cls, irg, bl, n, nodes);
 575         sched_add_after(pos, perm);
 576         free(nodes);
 577
 578         curr = perm;
 579         for(i = 0; i < n; ++i) {
 580                 ir_node *copies[2];
 581                 ir_node *perm_op = get_irn_n(perm, i);
 582                 const arch_register_t *reg = arch_get_irn_register(arch_env, perm_op);
 583
 584                 ir_mode *mode = get_irn_mode(perm_op);
 585                 ir_node *proj = new_r_Proj(irg, bl, perm, mode, i);
 586                 arch_set_irn_register(arch_env, proj, reg);
 587
 588                 sched_add_after(curr, proj);
 589                 curr = proj;
 590
 591                 copies[0] = perm_op;
 592                 copies[1] = proj;
 593
 594                 be_ssa_constr(dom_front, lv, 2, copies);
 595         }
 596
 597         return perm;
 598 }
 599
 600 struct _elr_closure_t {
 601         struct obstack obst;
 602         const be_chordal_env_t *cenv;
 603 };
 604
 605 static void elr_split_walker(ir_node *bl, void *data)
 606 {
 607         struct _elr_closure_t *c     = data;
 608         const be_chordal_env_t *cenv = c->cenv;
 609         const arch_env_t *aenv       = cenv->birg->main_env->arch_env;
 610         be_insn_t *insn;
 611         be_insn_env_t ie;
 612
 613         be_insn_env_init(&ie, cenv->birg, cenv->cls, &c->obst);
 614
 615         for(insn = be_scan_insn(&ie, sched_first(bl)); !is_Block(insn->irn); insn = be_scan_insn(&ie, insn->next_insn)) {
 616                 ir_node *pred = sched_prev(insn->irn);
 617                 if(!is_Block(pred) && !is_Phi(insn->irn))
 618                         insert_Perm_after(aenv, cenv->lv, cenv->cls, cenv->dom_front, insn->irn);
 619         }
 620 }
 621
 622 void extreme_liverange_splitting(struct _be_chordal_env_t *cenv)
 623 {
 624         struct _elr_closure_t c;
 625
 626         c.cenv = cenv;
 627         obstack_init(&c.obst);
 628         be_liveness_recompute(cenv->lv);
 629         irg_block_walk_graph(cenv->irg, elr_split_walker, NULL, &c);
 630         be_liveness_recompute(cenv->lv);
 631         obstack_free(&c.obst, NULL);
 632 }
 633
 634 static void remove_empty_block(ir_node *block, void *data) {
 635         ir_graph *irg;
 636         const ir_edge_t *edge, *next;
 637         ir_node *node;
 638         ir_node *jump = NULL;
 639
 640         assert(is_Block(block));
 641
 642         if(get_Block_n_cfgpreds(block) != 1)
 643                 return;
 644
 645         sched_foreach(block, node) {
 646                 if(!is_Jmp(node))
 647                         return;
 648                 if(jump != NULL) {
 649                         // we should never have 2 jumps in a block
 650                         assert(0);
 651                         return;
 652                 }
 653                 jump = node;
 654         }
 655         if(jump == NULL)
 656                 return;
 657
 658         node = get_Block_cfgpred(block, 0);
 659         foreach_out_edge_safe(jump, edge, next) {
 660                 ir_node *block = get_edge_src_irn(edge);
 661                 int pos = get_edge_src_pos(edge);
 662
 663                 set_irn_n(block, pos, node);
 664         }
 665
 666         set_Block_cfgpred(block, 0, new_Bad());
 667         sched_remove(jump);
 668
 669         irg = get_irn_irg(block);
 670         set_irg_doms_inconsistent(irg);
 671         set_irg_extblk_inconsistent(irg);
 672 }
 673
 674 /**
 675  * removes basic blocks that just contain a jump instruction
 676  */
 677 void be_remove_empty_blocks(ir_graph *irg) {
 678         irg_block_walk_graph(irg, remove_empty_block, NULL, NULL);
 679 }