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