nsz Git - libfirm/blob - ir/st/st.c

   1 /* Copyright (c) 2002 by Universität Karlsruhe (TH).  All Rights Reserved */
   2 /*
   3 * Time-stamp: <Thursday, 31.10.2002, 16:03:00 goetz@i44pc2.info.uni-karlsruhe.de>
   4 */
   5
   6 /**
   7    NAME
   8      st.h
   9    PURPOSE
  10      provide some auxilliary structures for firm graphs.
  11    S
  12      not quite complete
  13    HISTORY
  14      liekweg - Feb 26, 2002: Created.
  15    CVS:
  16      $Id$
  17 ***/
  18
  19 #ifdef HAVE_CONFIG_H
  20 #include "config.h"
  21 #endif
  22
  23 # include "st.h"
  24
  25 # include "irgwalk.h"
  26
  27 #  include <stdio.h>
  28 # ifdef DEBUG_libfirm
  29 # endif /* def DEBUG_libfirm */
  30 #  include <stdlib.h>
  31 # include "misc.h"
  32
  33 /* init globals: */
  34 /*static*/ dtree_t *trees = 0;
  35 /*
  36 static dtree_t *last  = 0;
  37 */
  38
  39 /* --------------------------------------------------------------------
  40 * Helper Functions
  41 * -------------------------------------------------------------------- */
  42 /*
  43   Helper function for get_n_blocks
  44 */
  45 static void count_block (ir_node *block, void *env)
  46 {
  47   int *n = (int*) env;
  48
  49 # ifdef DEBUG_libfirm
  50   assert (block && "no block");
  51   assert (env   && "no env");
  52 # endif /* def DEBUG_libfirm */
  53
  54   fprintf (stdout, "%s: Block(%p) has # (%i)\n",
  55                    __FILE__ ":count_block", block, *n);
  56
  57   (*n) ++;
  58 }
  59
  60 /*
  61   Count the number of blocks in the given graph
  62 */
  63 static int get_n_blocks (ir_graph *graph)
  64 {
  65   int n = 0;
  66
  67   ir_node *end_block = get_irg_end (graph);
  68
  69 # ifdef DEBUG_libfirm
  70   assert (graph     && "no graph");
  71   assert (end_block && "no end block");
  72 # endif /* def DEBUG_libfirm */
  73
  74   irg_block_walk (end_block, count_block, NULL, &n);
  75
  76   fprintf (stdout, "%s: Graph(%p) has (%i) blocks\n",
  77                    __FILE__ ":get_n_blocks", graph, n);
  78
  79   return (n);
  80 }
  81
  82 /*
  83   Build an empty dominator relation entry
  84 */
  85 static dtree_t *new_dtree (dt_t *tree, ir_graph *graph)
  86 {
  87   dtree_t *res = (dtree_t*) malloc (sizeof (dtree_t));
  88
  89 # ifdef DEBUG_libfirm
  90   assert (res      && "no memory for dtree");
  91 # endif /* def DEBUG_libfirm */
  92
  93   res->tree  = tree;
  94   res->graph = graph;
  95   res->next  = 0;
  96
  97   return (res);
  98 }
  99
 100 /*
 101   Build an empty dominator relation
 102 */
 103 static dt_t *new_dt (ir_graph *graph)
 104 {
 105   int n_blocks = get_n_blocks (graph);
 106
 107   dt_t *res = (dt_t*) malloc (sizeof (dt_t));
 108
 109 # ifdef DEBUG_libfirm
 110   assert (n_blocks && "no blocks for dt");
 111   assert (res      && "no memory for dt");
 112 # endif /* def DEBUG_libfirm */
 113
 114   res->n_blocks = n_blocks;
 115   res->graph    = graph;
 116   res->blocks   = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
 117   res->idoms    = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
 118   res->masks    = (bs_t*)     calloc (n_blocks, sizeof (bs_t));
 119
 120   assert (res && "no dt");
 121
 122   return (res);
 123 }
 124 /*
 125 static void free_dt (dt_t *dt)
 126 {
 127   free (dt->blocks);    dt->blocks = 0;
 128   free (dt->masks);             dt->masks  = 0;
 129   free (dt);
 130 }
 131 */
 132
 133 /* --------------------------------------------------------------------
 134 * Private Functions
 135 * -------------------------------------------------------------------- */
 136
 137 /*
 138   Given a graph, find its dominator tree in the global list:
 139
 140   @return       The tree, if it exists, and 0 else
 141 */
 142 static dt_t *get_dominator_tree   (ir_graph *graph)
 143 {
 144   dtree_t *iter = trees;
 145
 146 # ifdef DEBUG_libfirm
 147   assert (graph && "no graph");
 148 # endif /* def DEBUG_libfirm */
 149
 150   while ((0 != iter) && (graph != iter->graph))
 151         iter = iter->next;
 152
 153   if (0 != iter)
 154         {
 155 # ifdef DEBUG_libfirm
 156           assert ((graph == iter->tree->graph) && "wrong graph");
 157 # endif /* def DEBUG_libfirm */
 158
 159           return (iter->tree);
 160         }
 161   else
 162         {
 163           return (0);
 164         }
 165 }
 166
 167 /*
 168   Given a dominator tree and a graph, enter the tree into the global list.
 169 */
 170 static void add_dominator_tree (dt_t *tree)
 171 {
 172   dtree_t  *dtree = 0;
 173   ir_graph *graph = tree->graph;
 174
 175 # ifdef DEBUG_libfirm
 176   assert (tree  && "no tree" );
 177   assert (graph && "no graph");
 178 # endif /* def DEBUG_libfirm */
 179
 180   dtree = new_dtree (tree, graph);
 181
 182 # ifdef VERBOSE_libfirm
 183   fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
 184                    __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
 185 # endif /* def VERBOSE_libfirm */
 186
 187   /* enter in global list:  */
 188   dtree->next = trees;
 189   trees = dtree;
 190 }
 191
 192 /*
 193   Get (or create) the index for a given block
 194 */
 195 static int get_index (dt_t *dt, ir_node *block)
 196 {
 197   int i;
 198
 199 # ifdef DEBUG_libfirm
 200   assert (dt    && "no dt");
 201   assert (block && "no block");
 202 # endif /* def DEBUG_libfirm */
 203
 204   for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
 205         if (block == dt->blocks [i])
 206           return (i);
 207
 208   /* not found . . . enter new one: */
 209   dt->blocks [i] = block;
 210   if (block == get_irg_start_block (dt->graph))
 211         {
 212           dt->masks  [i] = 0x00000001 << i;
 213
 214 # ifdef VERBOSE_libfirm
 215           fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
 216                            __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
 217 # endif /* def VERBOSE_libfirm */
 218         }
 219   else
 220         {
 221           dt->masks  [i] = ~0x00000000;
 222
 223 # ifdef VERBOSE_libfirm
 224           fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
 225                            __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
 226 # endif /* def VERBOSE_libfirm */
 227         }
 228
 229   return (i);
 230 }
 231
 232 /*
 233   Get the bit mask for a block
 234 */
 235 static bs_t _get_mask (dt_t*, int);
 236 static bs_t get_mask (dt_t *dt, ir_node *block)
 237 {
 238   int index = get_index (dt, block);
 239
 240 # ifdef DEBUG_libfirm
 241   assert (dt    && "no dt");
 242   assert (block && "no block");
 243 # endif /* def DEBUG_libfirm */
 244
 245   return (_get_mask (dt, index));
 246 }
 247
 248 /*
 249   Get the bit mask for a block index
 250 */
 251 static bs_t _get_mask (dt_t *dt, int index)
 252 {
 253 # ifdef DEBUG_libfirm
 254   assert (dt && "no dt");
 255 # endif /* def DEBUG_libfirm */
 256
 257   return (dt->masks [index]);
 258 }
 259
 260 /*
 261   Set the bit mask for a block
 262 */
 263 #if 0
 264 static void _set_mask (dt_t*, int, bs_t);
 265 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
 266 {
 267   int index = get_index (dt, block);
 268
 269 # ifdef DEBUG_libfirm
 270   assert (dt    && "no dt");
 271   assert (block && "no block");
 272   # endif /* def DEBUG_libfirm */
 273
 274   _set_mask (dt, index, mask);
 275 }
 276 #endif
 277 /*
 278   Set the bit mask for a block index
 279 */
 280 static void _set_mask (dt_t *dt, int index, bs_t mask)
 281 {
 282 # ifdef DEBUG_libfirm
 283   assert (dt && "no dt");
 284 # endif /* def DEBUG_libfirm */
 285
 286   dt->masks [index] = mask;
 287 }
 288
 289 /*
 290   Update the list of dominators of a given block
 291 */
 292 typedef struct dt_walk_env_t
 293 {
 294   dt_t    *dt;          /* the dominator relation we're building */
 295   ir_node *start_block; /* need to know the start block of this graph */
 296   bool     changed;     /* wether the relation has changed recently */
 297 }
 298 dt_walk_env_t;
 299
 300 /*
 301   Helper function for build_dominator_tree
 302 */
 303 static void update_dominators (ir_node *block, void *env)
 304 {
 305   int i;
 306   dt_walk_env_t *w  = (dt_walk_env_t*) env;
 307   dt_t          *dt = w->dt;
 308
 309   int block_index = get_index     (dt, block);
 310   int n_ins       = get_irn_arity (block);
 311
 312   bs_t old_mask   = _get_mask     (dt, block_index);
 313   bs_t new_mask   = ~0x00000000;
 314
 315   /* Special handling of Start Block: */
 316   if (block == w->start_block)
 317         return;
 318
 319   /* check preds: */
 320   for (i = 0; i < n_ins; i ++)
 321     {
 322       ir_node *in  = get_nodes_Block (get_irn_n (block, i));
 323       bs_t in_mask = get_mask  (dt, in);
 324
 325       new_mask &= in_mask;
 326     }
 327
 328   /* and remember ourselves: */
 329   new_mask |= (0x00000001 << block_index);
 330
 331   if (new_mask != old_mask)
 332         {
 333           w->changed = true;
 334           _set_mask (dt, block_index, new_mask);
 335
 336 # ifdef VERBOSE_libfirm
 337           fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
 338                            __FILE__ ":" __PRETTY_FUNCTION__,
 339                            block, block_index, old_mask, new_mask);
 340 # endif /* def VERBOSE_libfirm */
 341         }
 342 }
 343
 344 /*
 345   Say wether a dominates b
 346 */
 347
 348 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
 349 {
 350   int index_a = get_index (dt, a);
 351   bs_t b_mask = get_mask  (dt, b);
 352
 353   return (0 != (b_mask & (0x00000001 << index_a)));
 354 }
 355
 356 /*
 357   Return the immediate dominator of block a
 358 */
 359 static ir_node *_get_idom (dt_t *dt, ir_node *block)
 360 {
 361   ir_node *idom   = 0;
 362   int block_index = get_index (dt, block);
 363
 364   if (0 != (idom = dt->idoms [block_index]))
 365         return (idom);
 366
 367   /* check all CFG preds:
 368      Question: Shouldn't it be good enough to just ask our first CFG
 369      predecessor?  */
 370   {
 371         int i         = 0;
 372         int n         = get_irn_arity (block);
 373         ir_node *pred = 0;
 374
 375         idom = block;                                   /* prime the loop: */
 376
 377         for (i = 0; i < n; i ++)
 378           {
 379                 ir_node *ndom = 0;
 380
 381                 pred = get_nodes_Block (get_irn_n (block, i));
 382                 ndom = _get_idom (dt, pred);
 383
 384                 if (ndom != idom)
 385                   if (_dominates (dt, idom, ndom))
 386                         idom = ndom;
 387           }
 388   }
 389
 390   assert (idom && "Something terribly wrong in _get_idom");
 391
 392 # ifdef VERBOSE_libfirm
 393   fprintf (stdout, "%s: idom(%p) = %p\n",
 394                    __FILE__ ":" __PRETTY_FUNCTION__,
 395                    block, idom);
 396 # endif /* def VERBOSE_libfirm */
 397
 398   /*  remember it: */
 399   dt->idoms [block_index] = idom;
 400
 401   return (idom);
 402 }
 403
 404 /* --------------------------------------------------------------------
 405 * Public Functions
 406 * -------------------------------------------------------------------- */
 407
 408 /*
 409   Say wether a dominates b
 410 */
 411 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
 412 {
 413   dt_t *dt    = get_dominator_tree (g);
 414
 415   return (_dominates (dt, a, b));
 416 }
 417
 418 /*
 419   Return the immediate dominator of block a
 420 */
 421 ir_node *get_idom (ir_graph *g, ir_node *a)
 422 {
 423   dt_t *dt = get_dominator_tree (g);
 424
 425   return (_get_idom (dt, a));
 426 }
 427
 428 /*
 429   Allow for precomputation of necessary data
 430   This will allow for a slightly faster lookup of the dominator
 431   relation if one node is checked for dominance against many other nodes.
 432 */
 433 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
 434 {
 435   dom_env_t *env = (dom_env_t*) calloc (1, sizeof (dom_env_t));
 436
 437   env->graph   = graph;
 438   env->dt      = get_dominator_tree (graph);
 439   env->a       = a;
 440   env->index_a = get_index (env->dt, a);
 441   return env;
 442 }
 443
 444 /*
 445   Dispose a dominator environment
 446 */
 447 void delete_dom_env (dom_env_t *env)
 448 {
 449   env->dt      = 0;
 450   env->a       = 0;
 451   env->graph   = 0;
 452   env->index_a = -1;
 453
 454   free (env);
 455 }
 456
 457 /*
 458   Say wether the node in env dominates b
 459
 460   see get_dom_env
 461 */
 462 bool dominates_l (dom_env_t *env, ir_node *b)
 463 {
 464   int index_a = env->index_a;
 465   dt_t *dt = env->dt;
 466   bs_t b_mask = get_mask  (dt, b);
 467
 468   return (0 != (b_mask & (0x00000001 << index_a)));
 469 }
 470
 471 /*
 472   Build a new dominator tree for the given graph
 473 */
 474 void build_dominator_tree (ir_graph *graph)
 475 {
 476   /*
 477   dt_walk_env_t *w   = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
 478
 479   ir_node *end_block   = get_irg_end_block   (graph);
 480   ir_node *start_block = get_irg_start_block (graph);
 481   int      n_blocks    = get_n_blocks        (graph);
 482   dt_t    *dt          = get_dominator_tree  (graph);
 483   */
 484
 485   dt_walk_env_t *w     = 0;
 486   ir_node *end_block   = 0;
 487   ir_node *start_block = 0;
 488   int      n_blocks    = 0;
 489   dt_t    *dt          = 0;
 490
 491   w           = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
 492   end_block   = get_irg_end_block   (graph);
 493   start_block = get_irg_start_block (graph);
 494   n_blocks    = get_n_blocks        (graph);
 495   dt          = get_dominator_tree  (graph);
 496
 497 # ifdef DEBUG_libfirm
 498   assert (graph && "no graph");
 499 # endif /* def DEBUG_libfirm */
 500
 501 # ifdef VERBOSE_libfirm
 502   fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
 503 # endif /* def VERBOSE_libfirm */
 504
 505   /*if (0 != dt)
 506     free_dt (dt); */
 507
 508   dt = new_dt (graph);
 509
 510   w->dt          = dt;
 511   w->start_block = start_block;
 512   w->changed     = true;        /* at least one walk */
 513
 514   /* do the walk: */
 515   {
 516         int walks = 0;
 517
 518         while (w->changed)
 519           {
 520                 w->changed = false;
 521                 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
 522                 walks ++;
 523           }
 524
 525 # ifdef VERBOSE_libfirm
 526         fprintf (stdout, "%s: for graph(%p):  %i passes\n",
 527                          __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
 528 # endif /* def VERBOSE_libfirm */
 529   }
 530
 531   /* ok, now remember it: */
 532   add_dominator_tree (dt);
 533 }