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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irdom.c
   4  * Purpose:     Construct and access dominator tree.
   5  * Author:      Goetz Lindenmaier
   6  * Modified by:
   7  * Created:     2.2002
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2002-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 #include "config.h"
  15 #endif
  16
  17 #include "irouts.h"
  18
  19 #include "irgwalk.h"
  20 #include "irdom_t.h"
  21 #include "irgraph_t.h"   /* To access state field. */
  22 #include "irnode_t.h"
  23 #include "ircons_t.h"
  24
  25 /*--------------------------------------------------------------------*/
  26 /** Accessing the dominator data structures                          **/
  27 /*--------------------------------------------------------------------*/
  28
  29 ir_node *get_Block_idom(ir_node *bl) {
  30   assert(get_irn_op(bl) == op_Block);
  31   if (get_Block_dom_depth(bl) == -1) {
  32     /* This block is not reachable from Start */
  33     return new_Bad();
  34   }
  35   return bl->attr.block.dom.idom;
  36 }
  37
  38 void set_Block_idom(ir_node *bl, ir_node *n) {
  39   assert(get_irn_op(bl) == op_Block);
  40   bl->attr.block.dom.idom = n;
  41 }
  42
  43 int get_Block_pre_num(ir_node *bl) {
  44   assert(get_irn_op(bl) == op_Block);
  45   return bl->attr.block.dom.pre_num;
  46 }
  47
  48 void set_Block_pre_num(ir_node *bl, int num) {
  49   assert(get_irn_op(bl) == op_Block);
  50   bl->attr.block.dom.pre_num = num;
  51 }
  52
  53 int get_Block_dom_depth(ir_node *bl) {
  54   assert(get_irn_op(bl) == op_Block);
  55   return bl->attr.block.dom.dom_depth;
  56 }
  57
  58 void set_Block_dom_depth(ir_node *bl, int depth) {
  59   assert(get_irn_op(bl) == op_Block);
  60   bl->attr.block.dom.dom_depth = depth;
  61 }
  62
  63
  64
  65 /*--------------------------------------------------------------------*/
  66 /*  Building and Removing the dominator datastructure                 */
  67 /*--------------------------------------------------------------------*/
  68
  69 static void count_and_init_blocks(ir_node *bl, void *env) {
  70   int *n_blocks = (int *) env;
  71   (*n_blocks) ++;
  72
  73   set_Block_idom(bl, NULL);
  74   set_Block_pre_num(bl, -1);
  75   set_Block_dom_depth(bl, -1);
  76 }
  77
  78 /* temporary type used while constructing the dominator tree. */
  79 typedef struct tmp_dom_info {
  80   ir_node *block;               /* backlink */
  81
  82   struct tmp_dom_info *semi;    /* semidominator */
  83   struct tmp_dom_info *parent;
  84   struct tmp_dom_info *label;   /* used for LINK and EVAL */
  85   struct tmp_dom_info *ancestor;/* used for LINK and EVAL */
  86   struct tmp_dom_info *dom;     /* After step 3, if the semidominator of w is
  87                                    its immediate dominator, then w->dom is the
  88                                    immediate dominator of w.  Otherwise w->dom
  89                                    is a vertex v whose number is smaller than
  90                                    w and whose immediate dominator is also w's
  91                                    immediate dominator. After step 4, w->dom
  92                                    is the immediate dominator of w.  */
  93   struct tmp_dom_info *bucket;  /* set of vertices with same semidominator */
  94 } tmp_dom_info;
  95
  96 /* Struct to pass info through walker. */
  97 typedef struct {
  98   tmp_dom_info *d;
  99   int used;
 100
 101 } dom_env;
 102
 103
 104 /* Walks Blocks along the out datastructure.  If recursion started with
 105    Start block misses control dead blocks. */
 106 static void init_tmp_dom_info(ir_node *bl, tmp_dom_info *parent,
 107                               tmp_dom_info *tdi_list, int* used) {
 108   tmp_dom_info *tdi;
 109   int i;
 110
 111   assert(get_irn_op(bl) == op_Block);
 112   if (get_irg_block_visited(current_ir_graph) == get_Block_block_visited(bl))
 113     return;
 114   mark_Block_block_visited(bl);
 115   set_Block_pre_num(bl, *used);
 116
 117   tdi = &tdi_list[*used];
 118   ++(*used);
 119
 120   tdi->semi = tdi;
 121   tdi->label = tdi;
 122   tdi->ancestor = NULL;
 123   tdi->bucket = NULL;
 124   tdi->parent = parent;
 125   tdi->block = bl;
 126
 127   /* Iterate */
 128   for(i = 0; i < get_Block_n_cfg_outs(bl); i++) {
 129     ir_node *pred = get_Block_cfg_out(bl, i);
 130     assert(get_irn_opcode(pred) == iro_Block);
 131     init_tmp_dom_info(pred, tdi, tdi_list, used);
 132   }
 133 }
 134
 135 static void
 136 dom_compress (tmp_dom_info *v)
 137 {
 138   assert (v->ancestor);
 139   if (v->ancestor->ancestor) {
 140     dom_compress (v->ancestor);
 141     if (v->ancestor->label->semi < v->label->semi) {
 142       v->label = v->ancestor->label;
 143     }
 144     v->ancestor = v->ancestor->ancestor;
 145   }
 146 }
 147
 148 /* if V is a root, return v, else return the vertex u, not being the
 149    root, with minimum u->semi on the path from v to its root. */
 150 INLINE static tmp_dom_info*
 151 dom_eval (tmp_dom_info *v)
 152 {
 153   if (!v->ancestor) return v;
 154   dom_compress (v);
 155   return v->label;
 156 }
 157
 158 /* make V W's ancestor */
 159 INLINE static void
 160 dom_link (tmp_dom_info *v, tmp_dom_info *w)
 161 {
 162   w->ancestor = v;
 163 }
 164
 165 /* Computes the dominator trees.  Sets a flag in irg to "dom_consistent".
 166    If the control flow of the graph is changed this flag must be set to
 167    "dom_inconsistent".  */
 168 void compute_doms(ir_graph *irg) {
 169   ir_graph *rem = current_ir_graph;
 170   int n_blocks, used, i, j;
 171   tmp_dom_info *tdi_list;   /* Ein Golf? */
 172
 173   current_ir_graph = irg;
 174
 175   /* Update graph state */
 176   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 177   current_ir_graph->dom_state = dom_consistent;
 178
 179   /* Count the number of blocks in the graph. */
 180   n_blocks = 0;
 181   irg_block_walk(get_irg_end(current_ir_graph), count_and_init_blocks, NULL, &n_blocks);
 182
 183   /* Memory for temporary information. */
 184   tdi_list = (tmp_dom_info *) calloc(n_blocks, sizeof(tmp_dom_info));
 185
 186   /* We need the out datastructure. */
 187   if (current_ir_graph->outs_state != outs_consistent)
 188     compute_outs(current_ir_graph);
 189
 190   /* this with a standard walker as passing the parent to the sons isn't
 191      simple. */
 192   used = 0;
 193   inc_irg_block_visited(current_ir_graph);
 194   init_tmp_dom_info(get_irg_start_block(current_ir_graph), NULL, tdi_list, &used);
 195   /* If not all blocks are reachable from Start by out edges this assertion
 196      fails.
 197      assert(used == n_blocks && "Precondition for dom construction violated"); */
 198   n_blocks = used;
 199
 200
 201   for (i = n_blocks-1; i > 0; i--) {  /* Don't iterate the root, it's done. */
 202     int irn_arity;
 203     tmp_dom_info *w = &tdi_list[i];
 204     tmp_dom_info *v;
 205
 206     /* Step 2 */
 207     irn_arity = get_irn_arity(w->block);
 208     for (j = 0;  j < irn_arity;  j++) {
 209       ir_node *cf_op = get_Block_cfgpred(w->block, j);
 210       ir_node *pred  = get_nodes_block(cf_op);
 211       tmp_dom_info *u;
 212
 213       if ((is_Bad(cf_op)) || (is_Bad(pred)) ||
 214           (get_Block_pre_num (pred) == -1))
 215         continue;       /* control-dead */
 216
 217       u = dom_eval (&tdi_list[get_Block_pre_num(pred)]);
 218       if (u->semi < w->semi) w->semi = u->semi;
 219     }
 220     /* Add w to w->semi's bucket.  w is in exactly one bucket, so
 221        buckets can ben implemented as linked lists. */
 222     w->bucket = w->semi->bucket;
 223     w->semi->bucket = w;
 224
 225     dom_link (w->parent, w);
 226
 227     /* Step 3 */
 228     while (w->parent->bucket) {
 229       tmp_dom_info *u;
 230       v = w->parent->bucket;
 231       /* remove v from w->parent->bucket */
 232       w->parent->bucket = v->bucket;
 233       v->bucket = NULL;
 234
 235       u = dom_eval (v);
 236       if (u->semi < v->semi)
 237         v->dom = u;
 238       else
 239         v->dom = w->parent;
 240     }
 241   }
 242   /* Step 4 */
 243   tdi_list[0].dom = NULL;
 244   set_Block_idom(tdi_list[0].block, NULL);
 245   set_Block_dom_depth(tdi_list[0].block, 1);
 246   for (i = 1;  i < n_blocks;  i++) {
 247     tmp_dom_info *w = &tdi_list[i];
 248
 249     if (w->dom != w->semi) w->dom = w->dom->dom;
 250     set_Block_idom(w->block, w->dom->block);
 251     set_Block_dom_depth(w->block, get_Block_dom_depth(w->dom->block) + 1);
 252   }
 253
 254   /* clean up */
 255   /*  free(tdi_list); @@@ does not work !!?? */
 256   current_ir_graph = rem;
 257 }
 258
 259 void free_dom_and_peace(ir_graph *irg) {
 260   /* Update graph state */
 261   assert(get_irg_phase_state(current_ir_graph) != phase_building);
 262   current_ir_graph->dom_state = dom_none;
 263
 264   /* With the implementation right now there is nothing to free,
 265      but better call it anyways... */
 266 }