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

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