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

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