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