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

   1 /* Copyright (c) 2002 by Universität Karlsruhe (TH).  All Rights Reserved */
   2 //
   3 // Time-stamp: <Monday, 13.05.2002, 13:27:22 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    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 n_blocks = get_n_blocks (graph);
 102
 103   dt_t *res = (dt_t*) malloc (sizeof (dt_t));
 104
 105 # ifdef DEBUG_libfirm
 106   assert (n_blocks && "no blocks for dt");
 107   assert (res      && "no memory for dt");
 108 # endif /* def DEBUG_libfirm */
 109
 110   res->n_blocks = n_blocks;
 111   res->graph    = graph;
 112   res->blocks   = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
 113   res->idoms    = (ir_node**) calloc (n_blocks, sizeof (ir_node*));
 114   res->masks    = (bs_t*)     calloc (n_blocks, sizeof (bs_t));
 115
 116   assert (res && "no dt");
 117
 118   return (res);
 119 }
 120
 121 static void free_dt (dt_t *dt)
 122 {
 123   free (dt->blocks);    dt->blocks = 0;
 124   free (dt->masks);             dt->masks  = 0;
 125   free (dt);
 126 }
 127
 128
 129 // --------------------------------------------------------------------
 130 // Private Functions
 131 // --------------------------------------------------------------------
 132
 133 /*
 134   Given a graph, find its dominator tree in the global list:
 135
 136   @return       The tree, if it exists, and 0 else
 137 */
 138 static dt_t *get_dominator_tree   (ir_graph *graph)
 139 {
 140   dtree_t *iter = trees;
 141
 142 # ifdef DEBUG_libfirm
 143   assert (graph && "no graph");
 144   // assert (iter  && "no trees");
 145 # endif /* def DEBUG_libfirm */
 146
 147   while ((0 != iter) && (graph != iter->graph))
 148         iter = iter->next;
 149
 150   if (0 != iter)
 151         {
 152 # ifdef DEBUG_libfirm
 153           assert ((graph == iter->tree->graph) && "wrong graph");
 154 # endif /* def DEBUG_libfirm */
 155
 156           return (iter->tree);
 157         }
 158   else
 159         {
 160           return (0);
 161         }
 162 }
 163
 164 /*
 165   Given a dominator tree and a graph, enter the tree into the global list.
 166 */
 167 static void add_dominator_tree (dt_t *tree)
 168 {
 169   dtree_t  *dtree = 0;
 170   ir_graph *graph = tree->graph;
 171
 172 # ifdef DEBUG_libfirm
 173   assert (tree  && "no tree" );
 174   assert (graph && "no graph");
 175 # endif /* def DEBUG_libfirm */
 176
 177   dtree = new_dtree (tree, graph);
 178
 179 # ifdef VERBOSE_libfirm
 180   fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
 181                    __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
 182 # endif /* def VERBOSE_libfirm */
 183
 184   //enter in global list:
 185   dtree->next = trees;
 186   trees = dtree;
 187 }
 188
 189 /*
 190   Get (or create) the index for a given block
 191 */
 192 static int get_index (dt_t *dt, ir_node *block)
 193 {
 194   int i;
 195
 196 # ifdef DEBUG_libfirm
 197   assert (dt    && "no dt");
 198   assert (block && "no block");
 199 # endif /* def DEBUG_libfirm */
 200
 201   for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
 202         if (block == dt->blocks [i])
 203           return (i);
 204
 205   /* not found . . . enter new one: */
 206   dt->blocks [i] = block;
 207   if (block == get_irg_start_block (dt->graph))
 208         {
 209           dt->masks  [i] = 0x00000001 << i;
 210
 211 # ifdef VERBOSE_libfirm
 212           fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
 213                            __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
 214 # endif /* def VERBOSE_libfirm */
 215         }
 216   else
 217         {
 218           dt->masks  [i] = ~0x00000000;
 219
 220 # ifdef VERBOSE_libfirm
 221           fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
 222                            __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
 223 # endif /* def VERBOSE_libfirm */
 224         }
 225
 226   return (i);
 227 }
 228
 229 /*
 230   Get the bit mask for a block
 231 */
 232 static bs_t _get_mask (dt_t*, int);
 233 static bs_t get_mask (dt_t *dt, ir_node *block)
 234 {
 235   int index = get_index (dt, block);
 236
 237 # ifdef DEBUG_libfirm
 238   assert (dt    && "no dt");
 239   assert (block && "no block");
 240 # endif /* def DEBUG_libfirm */
 241
 242   return (_get_mask (dt, index));
 243 }
 244
 245 /*
 246   Get the bit mask for a block index
 247 */
 248 static bs_t _get_mask (dt_t *dt, int index)
 249 {
 250 # ifdef DEBUG_libfirm
 251   assert (dt && "no dt");
 252 # endif /* def DEBUG_libfirm */
 253
 254   return (dt->masks [index]);
 255 }
 256
 257 /*
 258   Set the bit mask for a block
 259 */
 260 static void _set_mask (dt_t*, int, bs_t);
 261 static void set_mask (dt_t *dt, ir_node *block, bs_t mask)
 262 {
 263   int index = get_index (dt, block);
 264
 265 # ifdef DEBUG_libfirm
 266   assert (dt    && "no dt");
 267   assert (block && "no block");
 268 # endif /* def DEBUG_libfirm */
 269
 270   _set_mask (dt, index, mask);
 271 }
 272
 273 /*
 274   Set the bit mask for a block index
 275 */
 276 static void _set_mask (dt_t *dt, int index, bs_t mask)
 277 {
 278 # ifdef DEBUG_libfirm
 279   assert (dt && "no dt");
 280 # endif /* def DEBUG_libfirm */
 281
 282   dt->masks [index] = mask;
 283 }
 284
 285 /*
 286   Update the list of dominators of a given block
 287 */
 288 typedef struct dt_walk_env_t // grrr
 289 {
 290   dt_t    *dt;                                  // the dominator relation we're building
 291   ir_node *start_block;                 // need to know the start block of this graph
 292   bool     changed;                             // wether the relation has changed recently
 293 }
 294 dt_walk_env_t;
 295
 296 /*
 297   Helper function for build_dominator_tree
 298 */
 299 static void update_dominators (ir_node *block, void *env)
 300 {
 301   int i;
 302   dt_walk_env_t *w  = (dt_walk_env_t*) env;
 303   dt_t          *dt = w->dt;
 304
 305   int block_index = get_index     (dt, block);
 306   int n_ins       = get_irn_arity (block);
 307
 308   bs_t old_mask   = _get_mask     (dt, block_index);
 309   bs_t new_mask   = ~0x00000000;
 310
 311   // Special handling of Start Block:
 312   if (block == w->start_block)
 313         return;
 314
 315   // check preds:
 316   for (i = 0; i < n_ins; i ++)
 317         {
 318           ir_node *in  = get_nodes_Block (get_irn_n (block, i)); // hope that's the block
 319           bs_t in_mask = get_mask  (dt, in);
 320
 321           new_mask &= in_mask;
 322         }
 323
 324   // and remember ourselves:
 325   new_mask |= (0x00000001 << block_index);
 326
 327   if (new_mask != old_mask)
 328         {
 329           w->changed = TRUE;
 330           _set_mask (dt, block_index, new_mask);
 331
 332 # ifdef VERBOSE_libfirm
 333           fprintf (stdout, "%s: Updating block(%p)[%i] from [%#010lx] to [%#010lx]\n",
 334                            __FILE__ ":" __PRETTY_FUNCTION__,
 335                            block, block_index, old_mask, new_mask);
 336 # endif /* def VERBOSE_libfirm */
 337         }
 338 }
 339
 340 /*
 341   Say wether a dominates b
 342 */
 343
 344 static bool _dominates (dt_t *dt, ir_node *a, ir_node *b)
 345 {
 346   int index_a = get_index (dt, a);
 347   bs_t b_mask = get_mask  (dt, b);
 348
 349   return (0 != (b_mask & (0x00000001 << index_a)));
 350 }
 351
 352 /*
 353   Return the immediate dominator of block a
 354 */
 355 static ir_node *_get_idom (dt_t *dt, ir_node *block)
 356 {
 357   ir_node *idom   = 0;
 358   int block_index = get_index (dt, block);
 359
 360   if (0 != (idom = dt->idoms [block_index]))
 361         return (idom);
 362
 363   // check all CFG preds:
 364   // Question: Shouldn't it be good enough to just ask our first CFG predecessor?
 365   {
 366         int i         = 0;
 367         int n         = get_irn_arity (block);
 368         ir_node *pred = 0;
 369
 370         idom = block;                                   // prime the loop:
 371
 372         for (i = 0; i < n; i ++)
 373           {
 374                 ir_node *ndom = 0;
 375
 376                 pred = get_nodes_Block (get_irn_n (block, i));
 377                 ndom = _get_idom (dt, pred);
 378
 379                 if (ndom != idom)
 380                   if (_dominates (dt, idom, ndom))
 381                         idom = ndom;
 382           }
 383   }
 384
 385   assert (idom && "Something terribly wrong in _get_idom");
 386
 387 # ifdef VERBOSE_libfirm
 388   fprintf (stdout, "%s: idom(%p) = %p\n",
 389                    __FILE__ ":" __PRETTY_FUNCTION__,
 390                    block, idom);
 391 # endif /* def VERBOSE_libfirm */
 392
 393   // remember it:
 394   dt->idoms [block_index] = idom;
 395
 396   return (idom);
 397 }
 398
 399 // --------------------------------------------------------------------
 400 // Public Functions
 401 // --------------------------------------------------------------------
 402
 403 /*
 404   Say wether a dominates b
 405 */
 406 bool dominates (ir_graph *g, ir_node *a, ir_node *b)
 407 {
 408   dt_t *dt    = get_dominator_tree (g);
 409
 410   return (_dominates (dt, a, b));
 411 }
 412
 413 /*
 414   Return the immediate dominator of block a
 415 */
 416 ir_node *get_idom (ir_graph *g, ir_node *a)
 417 {
 418   dt_t *dt = get_dominator_tree (g);
 419
 420   return (_get_idom (dt, a));
 421 }
 422
 423 /*
 424   Allow for precomputation of necessary data
 425   This will allow for a slightly faster lookup of the dominator
 426   relation if one node is checked for dominance against many other nodes.
 427 */
 428 dom_env_t *get_dom_env (ir_graph *graph, ir_node *a)
 429 {
 430   dom_env_t *env = (dom_env_t*) calloc (1, sizeof (dom_env_t));
 431
 432   env->graph   = graph;
 433   env->dt      = get_dominator_tree (graph);
 434   env->a       = a;
 435   env->index_a = get_index (env->dt, a);
 436   return env;
 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 }