nsz Git - libfirm/blob - ir/ana/irdom.c

   1 /*
   2  * Copyright (C) 1995-2008 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     Construct and access dominator / post dominator tree.
  23  * @author    Goetz Lindenmaier, Michael Beck, Rubino Geiss
  24  * @date      2.2002
  25  */
  26 #include "config.h"
  27
  28 #include <string.h>
  29
  30 #include "irouts.h"
  31
  32 #include "xmalloc.h"
  33 #include "irgwalk.h"
  34 #include "irdom_t.h"
  35 #include "irgraph_t.h"
  36 #include "irnode_t.h"
  37 #include "ircons_t.h"
  38 #include "array_t.h"
  39 #include "iredges.h"
  40
  41
  42 #define get_dom_info(bl)  (&(bl)->attr.block.dom)
  43 #define get_pdom_info(bl) (&(bl)->attr.block.pdom)
  44
  45 ir_node *get_Block_idom(const ir_node *bl)
  46 {
  47         assert(is_Block(bl));
  48         if (get_Block_dom_depth(bl) == -1) {
  49                 /* This block is not reachable from Start */
  50                 ir_graph *irg = get_irn_irg(bl);
  51                 return new_r_Bad(irg, mode_BB);
  52         }
  53         return get_dom_info(bl)->idom;
  54 }
  55
  56 void set_Block_idom(ir_node *bl, ir_node *n)
  57 {
  58         ir_dom_info *bli = get_dom_info(bl);
  59
  60         assert(is_Block(bl));
  61
  62         /* Set the immediate dominator of bl to n */
  63         bli->idom = n;
  64
  65         /*
  66          * If we don't set the root of the dominator tree
  67          * Append bl to the dominates queue of n.
  68          */
  69         if (n != NULL) {
  70                 ir_dom_info *ni = get_dom_info(n);
  71
  72                 bli->next = ni->first;
  73                 ni->first = bl;
  74         }
  75 }
  76
  77 ir_node *get_Block_ipostdom(const ir_node *bl)
  78 {
  79         assert(is_Block(bl));
  80         if (get_Block_postdom_depth(bl) == -1) {
  81                 /* This block is not reachable from Start */
  82                 ir_graph *irg = get_irn_irg(bl);
  83                 return new_r_Bad(irg, mode_BB);
  84         }
  85         return get_pdom_info(bl)->idom;
  86 }
  87
  88 void set_Block_ipostdom(ir_node *bl, ir_node *n)
  89 {
  90         ir_dom_info *bli = get_pdom_info(bl);
  91
  92         assert(is_Block(bl));
  93
  94         /* Set the immediate post dominator of bl to n */
  95         bli->idom = n;
  96
  97         /*
  98          * If we don't set the root of the post dominator tree
  99          * Append bl to the post dominates queue of n.
 100          */
 101         if (n != NULL) {
 102                 ir_dom_info *ni = get_pdom_info(n);
 103
 104                 bli->next = ni->first;
 105                 ni->first = bl;
 106         }
 107 }
 108
 109 int get_Block_dom_pre_num(const ir_node *bl)
 110 {
 111         assert(is_Block(bl));
 112         return get_dom_info(bl)->pre_num;
 113 }
 114
 115 void set_Block_dom_pre_num(ir_node *bl, int num)
 116 {
 117         assert(is_Block(bl));
 118         get_dom_info(bl)->pre_num = num;
 119 }
 120
 121 int get_Block_dom_depth(const ir_node *bl)
 122 {
 123         assert(is_Block(bl));
 124         return get_dom_info(bl)->dom_depth;
 125 }
 126
 127 void set_Block_dom_depth(ir_node *bl, int depth)
 128 {
 129         assert(is_Block(bl));
 130         get_dom_info(bl)->dom_depth = depth;
 131 }
 132
 133
 134 int get_Block_postdom_pre_num(const ir_node *bl)
 135 {
 136         assert(is_Block(bl));
 137         return get_pdom_info(bl)->pre_num;
 138 }
 139
 140 void set_Block_postdom_pre_num(ir_node *bl, int num)
 141 {
 142         assert(is_Block(bl));
 143         get_pdom_info(bl)->pre_num = num;
 144 }
 145
 146 int get_Block_postdom_depth(const ir_node *bl)
 147 {
 148         assert(is_Block(bl));
 149         return get_pdom_info(bl)->dom_depth;
 150 }
 151
 152 void set_Block_postdom_depth(ir_node *bl, int depth)
 153 {
 154         assert(is_Block(bl));
 155         get_pdom_info(bl)->dom_depth = depth;
 156 }
 157
 158 unsigned get_Block_dom_tree_pre_num(const ir_node *bl)
 159 {
 160         assert(is_Block(bl));
 161         return get_dom_info(bl)->tree_pre_num;
 162 }
 163
 164 unsigned get_Block_dom_max_subtree_pre_num(const ir_node *bl)
 165 {
 166         assert(is_Block(bl));
 167         return get_dom_info(bl)->max_subtree_pre_num;
 168 }
 169
 170 unsigned get_Block_pdom_tree_pre_num(const ir_node *bl)
 171 {
 172         assert(is_Block(bl));
 173         return get_pdom_info(bl)->tree_pre_num;
 174 }
 175
 176 unsigned get_Block_pdom_max_subtree_pre_num(const ir_node *bl)
 177 {
 178         assert(is_Block(bl));
 179         return get_pdom_info(bl)->max_subtree_pre_num;
 180 }
 181
 182 int block_dominates(const ir_node *a, const ir_node *b)
 183 {
 184         const ir_dom_info *ai, *bi;
 185
 186         if (is_Block(a) && is_Block(b)) {
 187                 ai = get_dom_info(a);
 188                 bi = get_dom_info(b);
 189                 return bi->tree_pre_num - ai->tree_pre_num
 190                         <= ai->max_subtree_pre_num - ai->tree_pre_num;
 191         }
 192
 193         return 0;
 194 }
 195
 196 int block_strictly_dominates(const ir_node *a, const ir_node *b)
 197 {
 198         return (a != b) && block_dominates(a, b);
 199 }
 200
 201 ir_node *node_smallest_common_dominator(ir_node *a, ir_node *b)
 202 {
 203         ir_node *bl_a   = is_Block(a) ? a : get_nodes_block(a);
 204         ir_node *bl_b   = is_Block(b) ? b : get_nodes_block(b);
 205         ir_node *dom_bl = NULL;
 206
 207         /* Check if block of a dominates block of b */
 208         if (block_dominates(bl_a, bl_b))
 209                 dom_bl = bl_a;
 210         /* Check if block of b dominates block of a */
 211         else if (block_dominates(bl_b, bl_a))
 212                 dom_bl = bl_b;
 213         else {
 214                 /* walk up dominator tree and search for first block dominating a and b */
 215                 while (! dom_bl) {
 216                         bl_a = get_Block_idom(bl_a);
 217
 218                         assert(! is_Bad(bl_a) && "block is dead?");
 219
 220                         if (block_dominates(bl_a, bl_b))
 221                                 dom_bl = bl_a;
 222                 }
 223         }
 224
 225         return dom_bl;
 226 }
 227
 228 ir_node *node_users_smallest_common_dominator(ir_node *irn, int handle_phi)
 229 {
 230         int n, j, i = 0, success;
 231         ir_node **user_blocks, *dom_bl;
 232         const ir_edge_t *edge;
 233
 234         assert(! is_Block(irn) && "WRONG USAGE of node_users_smallest_common_dominator");
 235         assert(edges_activated(get_irn_irg(irn)) && "need edges activated");
 236
 237         n = get_irn_n_edges(irn);
 238
 239         /* get array to hold all block of the node users */
 240         NEW_ARR_A(ir_node *, user_blocks, n);
 241         foreach_out_edge(irn, edge) {
 242                 ir_node *src = get_edge_src_irn(edge);
 243
 244                 if (is_Phi(src) && handle_phi) {
 245                         /* get the corresponding cfg predecessor block if phi handling requested */
 246                         j  = get_edge_src_pos(edge);
 247                         assert(j >= 0 && "kaputt");
 248                         user_blocks[i++] = get_Block_cfgpred_block(get_nodes_block(src), j);
 249                 }
 250                 else
 251                         user_blocks[i++] = is_Block(src) ? src : get_nodes_block(src);
 252         }
 253
 254         assert(i == n && "get_irn_n_edges probably broken");
 255
 256         /* in case of only one user: return the block of the user */
 257         if (n == 1)
 258                 return user_blocks[0];
 259
 260         i = 0;
 261         /* search the smallest block dominating all user blocks */
 262         do {
 263                 dom_bl  = node_smallest_common_dominator(user_blocks[i], user_blocks[i + 1]);
 264                 success = 1;
 265
 266                 /* check if this block dominates all remaining blocks as well */
 267                 for (j = i + 2; j < n; j++) {
 268                         if (! block_dominates(dom_bl, user_blocks[j]))
 269                                 success = 0;
 270                 }
 271
 272                 if (success)
 273                         break;
 274
 275                 /* inherit the dominator block of the first (i + 1) users */
 276                 user_blocks[++i] = dom_bl;
 277         } while (i < n - 1);
 278
 279         assert(success && "no block found dominating all users");
 280
 281         return dom_bl;
 282 }
 283
 284 /* Get the first node in the list of nodes dominated by a given block. */
 285 ir_node *get_Block_dominated_first(const ir_node *bl)
 286 {
 287         assert(is_Block(bl));
 288         return get_dom_info(bl)->first;
 289 }
 290
 291 ir_node *get_Block_dominated_next(const ir_node *bl)
 292 {
 293         assert(is_Block(bl));
 294         return get_dom_info(bl)->next;
 295 }
 296
 297 int block_postdominates(const ir_node *a, const ir_node *b)
 298 {
 299         const ir_dom_info *ai, *bi;
 300
 301         if (is_Block(a) && is_Block(b)) {
 302                 ai = get_pdom_info(a);
 303                 bi = get_pdom_info(b);
 304                 return bi->tree_pre_num - ai->tree_pre_num
 305                         <= ai->max_subtree_pre_num - ai->tree_pre_num;
 306         }
 307
 308         return 0;
 309 }
 310
 311 int block_strictly_postdominates(const ir_node *a, const ir_node *b)
 312 {
 313         return (a != b) && block_postdominates(a, b);
 314 }
 315
 316 ir_node *get_Block_postdominated_first(const ir_node *bl)
 317 {
 318         assert(is_Block(bl));
 319         return get_pdom_info(bl)->first;
 320 }
 321
 322 ir_node *get_Block_postdominated_next(const ir_node *bl)
 323 {
 324         assert(is_Block(bl));
 325         return get_pdom_info(bl)->next;
 326 }
 327
 328 void dom_tree_walk(ir_node *bl, irg_walk_func *pre,
 329                 irg_walk_func *post, void *env)
 330 {
 331         ir_node *p;
 332
 333         if (pre)
 334                 pre(bl, env);
 335
 336         dominates_for_each(bl, p) {
 337                 dom_tree_walk(p, pre, post, env);
 338         }
 339
 340         if (post)
 341                 post(bl, env);
 342 }
 343
 344 void postdom_tree_walk(ir_node *bl, irg_walk_func *pre,
 345                 irg_walk_func *post, void *env)
 346 {
 347         ir_node *p;
 348
 349         if (pre)
 350                 pre(bl, env);
 351
 352         postdominates_for_each(bl, p) {
 353                 postdom_tree_walk(p, pre, post, env);
 354         }
 355
 356         if (post)
 357                 post(bl, env);
 358 }
 359
 360 void dom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 361                 irg_walk_func *post, void *env)
 362 {
 363         /* The root of the dominator tree should be the Start block. */
 364         ir_node *root = get_irg_start_block(irg);
 365
 366         assert(is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE)
 367                         && "The dominators of the irg must be consistent");
 368         assert(root && "The start block of the graph is NULL?");
 369         assert(get_dom_info(root)->idom == NULL
 370                         && "The start node in the graph must be the root of the dominator tree");
 371         dom_tree_walk(root, pre, post, env);
 372 }
 373
 374 void postdom_tree_walk_irg(ir_graph *irg, irg_walk_func *pre,
 375                 irg_walk_func *post, void *env)
 376 {
 377         /* The root of the post dominator tree should be the End block. */
 378         ir_node *root = get_irg_end_block(irg);
 379
 380         assert(is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE)
 381                         && "The dominators of the irg must be consistent");
 382         assert(root && "The end block of the graph is NULL?");
 383         assert(get_pdom_info(root)->idom == NULL
 384                         && "The End block node in the graph must be the root of the post dominator tree");
 385         postdom_tree_walk(root, pre, post, env);
 386 }
 387
 388
 389 static void assign_tree_dom_pre_order(ir_node *bl, void *data)
 390 {
 391         unsigned *num = (unsigned*) data;
 392         ir_dom_info *bi = get_dom_info(bl);
 393
 394         bi->tree_pre_num = (*num)++;
 395 }
 396
 397 static void assign_tree_dom_pre_order_max(ir_node *bl, void *data)
 398 {
 399         ir_dom_info *bi = get_dom_info(bl);
 400         ir_node *p;
 401         unsigned max = 0;
 402         unsigned children = 0;
 403         (void) data;
 404
 405         for (p = bi->first; p; p = get_dom_info(p)->next) {
 406                 unsigned max_p = get_dom_info(p)->max_subtree_pre_num;
 407                 max = max > max_p ? max : max_p;
 408                 children++;
 409         }
 410
 411         bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
 412         assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
 413 }
 414
 415 static void assign_tree_postdom_pre_order(ir_node *bl, void *data)
 416 {
 417         unsigned *num = (unsigned*) data;
 418         ir_dom_info *bi = get_pdom_info(bl);
 419
 420         bi->tree_pre_num = (*num)++;
 421 }
 422
 423 static void assign_tree_postdom_pre_order_max(ir_node *bl, void *data)
 424 {
 425         ir_dom_info *bi = get_pdom_info(bl);
 426         ir_node *p;
 427         unsigned max = 0;
 428         unsigned children = 0;
 429         (void) data;
 430
 431         for (p = bi->first; p; p = get_pdom_info(p)->next) {
 432                 unsigned max_p = get_pdom_info(p)->max_subtree_pre_num;
 433                 max = max > max_p ? max : max_p;
 434                 children++;
 435         }
 436
 437         bi->max_subtree_pre_num = children > 0 ? max : bi->tree_pre_num;
 438         assert(bi->max_subtree_pre_num >= bi->tree_pre_num);
 439 }
 440
 441 /**
 442  * count the number of blocks and clears the post dominance info
 443  */
 444 static void count_and_init_blocks_pdom(ir_node *bl, void *env)
 445 {
 446         int *n_blocks = (int *) env;
 447
 448         (*n_blocks) ++;
 449
 450         memset(get_pdom_info(bl), 0, sizeof(ir_dom_info));
 451         set_Block_ipostdom(bl, NULL);
 452         set_Block_postdom_pre_num(bl, -1);
 453         set_Block_postdom_depth(bl, -1);
 454 }
 455
 456 /** temporary type used while constructing the dominator / post dominator tree. */
 457 typedef struct tmp_dom_info {
 458         ir_node *block;               /**< backlink */
 459
 460         struct tmp_dom_info *semi;    /**< semidominator */
 461         struct tmp_dom_info *parent;
 462         struct tmp_dom_info *label;   /**< used for LINK and EVAL */
 463         struct tmp_dom_info *ancestor;/**< used for LINK and EVAL */
 464         struct tmp_dom_info *dom;     /**< After step 3, if the semidominator of w is
 465                                            its immediate dominator, then w->dom is the
 466                                            immediate dominator of w.  Otherwise w->dom
 467                                            is a vertex v whose number is smaller than
 468                                            w and whose immediate dominator is also w's
 469                                            immediate dominator. After step 4, w->dom
 470                                            is the immediate dominator of w.  */
 471         struct tmp_dom_info *bucket;  /**< set of vertices with same semidominator */
 472 } tmp_dom_info;
 473
 474 /** Struct to pass info through walker. */
 475 typedef struct {
 476         tmp_dom_info *d;
 477         int used;
 478 } dom_env;
 479
 480
 481 /**
 482  * Walks Blocks along the out data structure.  If recursion started with
 483  * Start block misses control dead blocks.
 484  */
 485 static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent,
 486                               tmp_dom_info *tdi_list, int *used, int n_blocks)
 487 {
 488         tmp_dom_info *tdi;
 489         int i;
 490
 491         assert(is_Block(bl));
 492         if (Block_block_visited(bl))
 493           return;
 494         mark_Block_block_visited(bl);
 495         set_Block_dom_pre_num(bl, *used);
 496
 497         assert(*used < n_blocks);
 498         tdi = &tdi_list[*used];
 499         ++(*used);
 500
 501         tdi->semi     = tdi;
 502         tdi->label    = tdi;
 503         tdi->ancestor = NULL;
 504         tdi->bucket   = NULL;
 505         tdi->parent   = parent;
 506         tdi->block    = bl;
 507
 508         /* Iterate */
 509         for (i = get_Block_n_cfg_outs_ka(bl) - 1; i >= 0; --i) {
 510                 ir_node *pred = get_Block_cfg_out_ka(bl, i);
 511                 /* can happen for half-optimized dead code (I've seen this in student
 512                    projects */
 513                 if (!is_Block(pred))
 514                         continue;
 515
 516                 init_tmp_dom_info(pred, tdi, tdi_list, used, n_blocks);
 517         }
 518 }
 519
 520 /**
 521  * Walks Blocks along the control flow.  If recursion started with
 522  * End block misses blocks in endless loops.
 523  */
 524 static void init_tmp_pdom_info(ir_node *bl, tmp_dom_info *parent,
 525                                tmp_dom_info *tdi_list, int* used, int n_blocks)
 526 {
 527         tmp_dom_info *tdi;
 528         int i;
 529
 530         assert(is_Block(bl));
 531         if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
 532           return;
 533         mark_Block_block_visited(bl);
 534         set_Block_postdom_pre_num(bl, *used);
 535
 536         assert(*used < n_blocks);
 537         tdi = &tdi_list[*used];
 538         ++(*used);
 539
 540         tdi->semi = tdi;
 541         tdi->label = tdi;
 542         tdi->ancestor = NULL;
 543         tdi->bucket = NULL;
 544         tdi->parent = parent;
 545         tdi->block = bl;
 546
 547         /* Iterate */
 548         for (i = get_Block_n_cfgpreds(bl) - 1; i >= 0; --i) {
 549                 ir_node *pred = get_Block_cfgpred_block(bl, i);
 550                 if (is_Bad(pred))
 551                         continue;
 552                 assert(is_Block(pred));
 553                 init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
 554         }
 555
 556         /* Handle keep-alives. Note that the preprocessing
 557            in init_construction() had already killed all
 558            phantom keep-alive edges. All remaining block keep-alives
 559            are really edges to endless loops.
 560          */
 561         if (bl == get_irg_end_block(current_ir_graph)) {
 562                 ir_node *end = get_irg_end(current_ir_graph);
 563
 564                 for (i = get_irn_arity(end) - 1; i >= 0; --i) {
 565                         ir_node *pred = get_irn_n(end, i);
 566
 567                         if (is_Block(pred))
 568                                 init_tmp_pdom_info(pred, tdi, tdi_list, used, n_blocks);
 569                 }
 570         }
 571 }
 572
 573 static void dom_compress(tmp_dom_info *v)
 574 {
 575         assert (v->ancestor);
 576         if (v->ancestor->ancestor) {
 577                 dom_compress (v->ancestor);
 578                 if (v->ancestor->label->semi < v->label->semi) {
 579                         v->label = v->ancestor->label;
 580                 }
 581                 v->ancestor = v->ancestor->ancestor;
 582         }
 583 }
 584
 585 /**
 586  * if V is a root, return v, else return the vertex u, not being the
 587  * root, with minimum u->semi on the path from v to its root.
 588  */
 589 inline static tmp_dom_info *dom_eval(tmp_dom_info *v)
 590 {
 591         if (!v->ancestor) return v;
 592         dom_compress (v);
 593         return v->label;
 594 }
 595
 596 /** make V W's ancestor */
 597 inline static void dom_link(tmp_dom_info *v, tmp_dom_info *w)
 598 {
 599         w->ancestor = v;
 600 }
 601
 602 /**
 603  * Walker: count the number of blocks and clears the dominance info
 604  */
 605 static void count_and_init_blocks_dom(ir_node *bl, void *env)
 606 {
 607         int *n_blocks = (int *) env;
 608
 609         (*n_blocks) ++;
 610
 611         memset(get_dom_info(bl), 0, sizeof(ir_dom_info));
 612         set_Block_idom(bl, NULL);
 613         set_Block_dom_pre_num(bl, -1);
 614         set_Block_dom_depth(bl, -1);
 615 }
 616
 617 void compute_doms(ir_graph *irg)
 618 {
 619         ir_graph *rem = current_ir_graph;
 620         int n_blocks, used, i, j;
 621         tmp_dom_info *tdi_list;   /* Ein Golf? */
 622
 623         current_ir_graph = irg;
 624
 625         /* Update graph state */
 626         assert(get_irg_phase_state(irg) != phase_building);
 627
 628         /* Count the number of blocks in the graph. */
 629         n_blocks = 0;
 630         irg_block_walk_graph(irg, count_and_init_blocks_dom, NULL, &n_blocks);
 631
 632         /* Memory for temporary information. */
 633         tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
 634
 635         /* We need the out data structure. */
 636         assure_irg_outs(irg);
 637
 638         /* this with a standard walker as passing the parent to the sons isn't
 639            simple. */
 640         used = 0;
 641         inc_irg_block_visited(irg);
 642         init_tmp_dom_info(get_irg_start_block(irg), NULL, tdi_list, &used, n_blocks);
 643         /* If not all blocks are reachable from Start by out edges this assertion
 644            fails.
 645            assert(used == n_blocks && "Precondition for dom construction violated"); */
 646         assert(used <= n_blocks && "Precondition for dom construction violated");
 647         n_blocks = used;
 648
 649
 650         for (i = n_blocks-1; i > 0; i--) {  /* Don't iterate the root, it's done. */
 651                 tmp_dom_info *w     = &tdi_list[i];
 652                 ir_node      *block = w->block;
 653                 tmp_dom_info *v;
 654                 int           irn_arity;
 655
 656                 /* Step 2 */
 657                 irn_arity = get_irn_arity(block);
 658                 for (j = 0; j < irn_arity;  j++) {
 659                         ir_node *pred       = get_Block_cfgpred(block, j);
 660                         ir_node *pred_block = get_nodes_block(pred);
 661                         tmp_dom_info *u;
 662
 663                         if (is_Bad(pred) || (get_Block_dom_pre_num (pred_block) == -1))
 664                                 continue;    /* unreachable */
 665
 666                         u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred_block)]);
 667                         if (u->semi < w->semi)
 668                                 w->semi = u->semi;
 669                 }
 670
 671                 /* handle keep-alives if we are at the end block */
 672                 if (block == get_irg_end_block(irg)) {
 673                         ir_node *end = get_irg_end(irg);
 674
 675                         irn_arity = get_irn_arity(end);
 676                         for (j = 0; j < irn_arity;  j++) {
 677                                 ir_node *pred = get_irn_n(end, j);
 678                                 tmp_dom_info *u;
 679
 680                                 if (!is_Block(pred) || get_Block_dom_pre_num(pred) == -1)
 681                                         continue;   /* unreachable */
 682
 683                                 u = dom_eval (&tdi_list[get_Block_dom_pre_num(pred)]);
 684                                 if (u->semi < w->semi)
 685                                         w->semi = u->semi;
 686                         }
 687                 }
 688
 689                 /* Add w to w->semi's bucket.  w is in exactly one bucket, so
 690                    buckets can been implemented as linked lists. */
 691                 w->bucket = w->semi->bucket;
 692                 w->semi->bucket = w;
 693
 694                 dom_link (w->parent, w);
 695
 696                 /* Step 3 */
 697                 while (w->parent->bucket) {
 698                         tmp_dom_info *u;
 699                         v = w->parent->bucket;
 700                         /* remove v from w->parent->bucket */
 701                         w->parent->bucket = v->bucket;
 702                         v->bucket = NULL;
 703
 704                         u = dom_eval (v);
 705                         if (u->semi < v->semi)
 706                                 v->dom = u;
 707                         else
 708                                 v->dom = w->parent;
 709                 }
 710         }
 711         /* Step 4 */
 712         tdi_list[0].dom = NULL;
 713         set_Block_idom(tdi_list[0].block, NULL);
 714         set_Block_dom_depth(tdi_list[0].block, 1);
 715         for (i = 1; i < n_blocks;  i++) {
 716                 tmp_dom_info *w = &tdi_list[i];
 717                 int depth;
 718
 719                 if (! w->dom)
 720                         continue; /* control dead */
 721
 722                 if (w->dom != w->semi)
 723                         w->dom = w->dom->dom;
 724                 set_Block_idom(w->block, w->dom->block);
 725
 726                 /* blocks dominated by dead one's are still dead */
 727                 depth = get_Block_dom_depth(w->dom->block);
 728                 if (depth > 0)
 729                         ++depth;
 730                 set_Block_dom_depth(w->block, depth);
 731         }
 732
 733         /* clean up */
 734         free(tdi_list);
 735
 736         /* Do a walk over the tree and assign the tree pre orders. */
 737         {
 738                 unsigned tree_pre_order = 0;
 739                 dom_tree_walk(get_irg_start_block(irg), assign_tree_dom_pre_order,
 740                                   assign_tree_dom_pre_order_max, &tree_pre_order);
 741         }
 742         current_ir_graph = rem;
 743         set_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
 744 }
 745
 746 void assure_doms(ir_graph *irg)
 747 {
 748         if (! is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE))
 749                 compute_doms(irg);
 750 }
 751
 752 void free_dom(ir_graph *irg)
 753 {
 754         /* Update graph state */
 755         assert(get_irg_phase_state(irg) != phase_building);
 756         clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
 757
 758         /* With the implementation right now there is nothing to free,
 759            but better call it anyways... */
 760 }
 761
 762 void compute_postdoms(ir_graph *irg)
 763 {
 764         ir_graph *rem = current_ir_graph;
 765         int n_blocks, used, i, j;
 766         tmp_dom_info *tdi_list;
 767
 768         current_ir_graph = irg;
 769
 770         /* Update graph state */
 771         assert(get_irg_phase_state(irg) != phase_building);
 772
 773         /* Count the number of blocks in the graph. */
 774         n_blocks = 0;
 775         irg_block_walk_graph(irg, count_and_init_blocks_pdom, NULL, &n_blocks);
 776
 777         /* Memory for temporary information. */
 778         tdi_list = XMALLOCNZ(tmp_dom_info, n_blocks);
 779
 780         /* We need the out data structure. */
 781         assure_irg_outs(irg);
 782
 783         /* this with a standard walker as passing the parent to the sons isn't
 784            simple. */
 785         used = 0;
 786         inc_irg_block_visited(irg);
 787         init_tmp_pdom_info(get_irg_end_block(irg), NULL, tdi_list, &used, n_blocks);
 788         /* If not all blocks are reachable from End by cfg edges this assertion
 789            fails.
 790            assert(used == n_blocks && "Precondition for dom construction violated"); */
 791         n_blocks = used;
 792
 793
 794         for (i = n_blocks-1; i > 0; i--) {  /* Don't iterate the root, it's done. */
 795                 int irn_arity;
 796                 tmp_dom_info *w = &tdi_list[i];
 797                 tmp_dom_info *v;
 798
 799                 /* Step 2 */
 800                 irn_arity = get_Block_n_cfg_outs_ka(w->block);
 801                 for (j = 0;  j < irn_arity;  j++) {
 802                         ir_node *succ = get_Block_cfg_out_ka(w->block, j);
 803                         tmp_dom_info *u;
 804
 805                         if (get_Block_postdom_pre_num (succ) == -1)
 806                                 continue;    /* endless-loop */
 807
 808                         u = dom_eval (&tdi_list[get_Block_postdom_pre_num(succ)]);
 809                         if (u->semi < w->semi) w->semi = u->semi;
 810                 }
 811                 /* Add w to w->semi's bucket.  w is in exactly one bucket, so
 812                    buckets can be implemented as linked lists. */
 813                 w->bucket = w->semi->bucket;
 814                 w->semi->bucket = w;
 815
 816                 dom_link (w->parent, w);
 817
 818                 /* Step 3 */
 819                 while (w->parent->bucket) {
 820                         tmp_dom_info *u;
 821                         v = w->parent->bucket;
 822                         /* remove v from w->parent->bucket */
 823                         w->parent->bucket = v->bucket;
 824                         v->bucket = NULL;
 825
 826                         u = dom_eval(v);
 827                         if (u->semi < v->semi)
 828                                 v->dom = u;
 829                         else
 830                                 v->dom = w->parent;
 831                 }
 832         }
 833         /* Step 4 */
 834         tdi_list[0].dom = NULL;
 835         set_Block_ipostdom(tdi_list[0].block, NULL);
 836         set_Block_postdom_depth(tdi_list[0].block, 1);
 837         for (i = 1;  i < n_blocks;  i++) {
 838                 tmp_dom_info *w = &tdi_list[i];
 839
 840                 if (w->dom != w->semi) w->dom = w->dom->dom;
 841                 set_Block_ipostdom(w->block, w->dom->block);
 842                 set_Block_postdom_depth(w->block, get_Block_postdom_depth(w->dom->block) + 1);
 843         }
 844
 845         /* clean up */
 846         free(tdi_list);
 847
 848         /* Do a walk over the tree and assign the tree pre orders. */
 849         {
 850                 unsigned tree_pre_order = 0;
 851                 postdom_tree_walk(get_irg_end_block(irg), assign_tree_postdom_pre_order,
 852                         assign_tree_postdom_pre_order_max, &tree_pre_order);
 853         }
 854         current_ir_graph = rem;
 855         set_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE);
 856 }
 857
 858 void assure_postdoms(ir_graph *irg)
 859 {
 860         if (! is_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE))
 861                 compute_postdoms(irg);
 862 }
 863
 864 void free_postdom(ir_graph *irg)
 865 {
 866         /* Update graph state */
 867         assert(get_irg_phase_state(irg) != phase_building);
 868         clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_POSTDOMINANCE);
 869
 870         /* With the implementation right now there is nothing to free,
 871            but better call it anyways... */
 872 }