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

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