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

   1 /* Copyright (c) 2002 by Universität Karlsruhe (TH).  All Rights Reserved */
   2 /*
   3 ** Time-stamp: <Friday, 05.07.2002, 11:06:38 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 # include "misc.h"
  28
  29 /* init globals: */
  30 static dtree_t *trees = 0;
  31 /*
  32 static dtree_t *last  = 0;
  33 */
  34
  35 /* --------------------------------------------------------------------
  36 ** Helper Functions
  37 ** -------------------------------------------------------------------- */
  38 /*
  39   Helper function for get_n_blocks
  40 */
  41 static void count_block (ir_node *block, void *env)
  42 {
  43   int *n = (int*) env;
  44
  45 # ifdef DEBUG_libfirm
  46   assert (block && "no block");
  47   assert (env   && "no env");
  48 # endif /* def DEBUG_libfirm */
  49
  50   fprintf (stdout, "%s: Block(%p) has # (%i)\n",
  51                    __FILE__ ":" __PRETTY_FUNCTION__, block, *n);
  52
  53   (*n) ++;
  54 }
  55
  56 /*
  57   Count the number of blocks in the given graph
  58 */
  59 static int get_n_blocks (ir_graph *graph)
  60 {
  61   int n = 0;
  62
  63   ir_node *end_block = get_irg_end (graph);
  64
  65 # ifdef DEBUG_libfirm
  66   assert (graph     && "no graph");
  67   assert (end_block && "no end block");
  68 # endif /* def DEBUG_libfirm */
  69
  70   irg_block_walk (end_block, count_block, NULL, &n);
  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 # endif /* def DEBUG_libfirm */
 145
 146   while ((0 != iter) && (graph != iter->graph))
 147         iter = iter->next;
 148
 149   if (0 != iter)
 150         {
 151 # ifdef DEBUG_libfirm
 152           assert ((graph == iter->tree->graph) && "wrong graph");
 153 # endif /* def DEBUG_libfirm */
 154
 155           return (iter->tree);
 156         }
 157   else
 158         {
 159           return (0);
 160         }
 161 }
 162
 163 /*
 164   Given a dominator tree and a graph, enter the tree into the global list.
 165 */
 166 static void add_dominator_tree (dt_t *tree)
 167 {
 168   dtree_t  *dtree = 0;
 169   ir_graph *graph = tree->graph;
 170
 171 # ifdef DEBUG_libfirm
 172   assert (tree  && "no tree" );
 173   assert (graph && "no graph");
 174 # endif /* def DEBUG_libfirm */
 175
 176   dtree = new_dtree (tree, graph);
 177
 178 # ifdef VERBOSE_libfirm
 179   fprintf (stdout, "%s: Adding dtree(%p) into trees(%p)\n",
 180                    __FILE__ ":" __PRETTY_FUNCTION__, dtree, trees);
 181 # endif /* def VERBOSE_libfirm */
 182
 183   /* enter in global list:  */
 184   dtree->next = trees;
 185   trees = dtree;
 186 }
 187
 188 /*
 189   Get (or create) the index for a given block
 190 */
 191 static int get_index (dt_t *dt, ir_node *block)
 192 {
 193   int i;
 194
 195 # ifdef DEBUG_libfirm
 196   assert (dt    && "no dt");
 197   assert (block && "no block");
 198 # endif /* def DEBUG_libfirm */
 199
 200   for (i = 0; (i < dt->n_blocks) && (0 != dt->blocks [i]); i ++)
 201         if (block == dt->blocks [i])
 202           return (i);
 203
 204   /* not found . . . enter new one: */
 205   dt->blocks [i] = block;
 206   if (block == get_irg_start_block (dt->graph))
 207         {
 208           dt->masks  [i] = 0x00000001 << i;
 209
 210 # ifdef VERBOSE_libfirm
 211           fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
 212                            __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
 213 # endif /* def VERBOSE_libfirm */
 214         }
 215   else
 216         {
 217           dt->masks  [i] = ~0x00000000;
 218
 219 # ifdef VERBOSE_libfirm
 220           fprintf (stdout, "%s: Adding block(%p)[%i] with [%#010lx]\n",
 221                            __FILE__ ":" __PRETTY_FUNCTION__, block, i, dt->masks [i]);
 222 # endif /* def VERBOSE_libfirm */
 223         }
 224
 225   return (i);
 226 }
 227
 228 /*
 229   Get the bit mask for a block
 230 */
 231 static bs_t _get_mask (dt_t*, int);
 232 static bs_t get_mask (dt_t *dt, ir_node *block)
 233 {
 234   int index = get_index (dt, block);
 235
 236 # ifdef DEBUG_libfirm
 237   assert (dt    && "no dt");
 238   assert (block && "no block");
 239 # endif /* def DEBUG_libfirm */
 240
 241   return (_get_mask (dt, index));
 242 }
 243
 244 /*
 245   Get the bit mask for a block index
 246 */
 247 static bs_t _get_mask (dt_t *dt, int index)
 248 {
 249 # ifdef DEBUG_libfirm
 250   assert (dt && "no dt");
 251 # endif /* def DEBUG_libfirm */
 252
 253   return (dt->masks [index]);
 254 }
 255
 256 /*
 257   Set the bit mask for a block
 258 */
 259 #if 0
 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 #endif
 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
 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));
 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
 365      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   return env;
 438 }
 439
 440 /*
 441   Dispose a dominator environment
 442 */
 443 void delete_dom_env (dom_env_t *env)
 444 {
 445   env->dt      = 0;
 446   env->a       = 0;
 447   env->graph   = 0;
 448   env->index_a = -1;
 449
 450   free (env);
 451 }
 452
 453 /*
 454   Say wether the node in env dominates b
 455
 456   see get_dom_env
 457 */
 458 bool dominates_l (dom_env_t *env, ir_node *b)
 459 {
 460   int index_a = env->index_a;
 461   dt_t *dt = env->dt;
 462   bs_t b_mask = get_mask  (dt, b);
 463
 464   return (0 != (b_mask & (0x00000001 << index_a)));
 465 }
 466
 467 /*
 468   Build a new dominator tree for the given graph
 469 */
 470 void build_dominator_tree (ir_graph *graph)
 471 {
 472   /*
 473   dt_walk_env_t *w   = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
 474
 475   ir_node *end_block   = get_irg_end_block   (graph);
 476   ir_node *start_block = get_irg_start_block (graph);
 477   int      n_blocks    = get_n_blocks        (graph);
 478   dt_t    *dt          = get_dominator_tree  (graph);
 479   */
 480
 481   dt_walk_env_t *w     = 0;
 482   ir_node *end_block   = 0;
 483   ir_node *start_block = 0;
 484   int      n_blocks    = 0;
 485   dt_t    *dt          = 0;
 486
 487   w           = (dt_walk_env_t*) alloca (sizeof (dt_walk_env_t));
 488   end_block   = get_irg_end_block   (graph);
 489   start_block = get_irg_start_block (graph);
 490   n_blocks    = get_n_blocks        (graph);
 491   dt          = get_dominator_tree  (graph);
 492
 493 # ifdef DEBUG_libfirm
 494   assert (graph && "no graph");
 495 # endif /* def DEBUG_libfirm */
 496
 497 # ifdef VERBOSE_libfirm
 498   fprintf (stdout, "%s: for graph(%p)\n", __FILE__ ":" __PRETTY_FUNCTION__, graph);
 499 # endif /* def VERBOSE_libfirm */
 500
 501   /*if (0 != dt)
 502     free_dt (dt); */
 503
 504   dt = new_dt (graph);
 505
 506   w->dt          = dt;
 507   w->start_block = start_block;
 508   w->changed     = TRUE;        /* at least one walk */
 509
 510   /* do the walk: */
 511   {
 512         int walks = 0;
 513
 514         while (w->changed)
 515           {
 516                 w->changed = FALSE;
 517                 irg_block_walk (end_block, update_dominators, update_dominators, (void*) w);
 518                 walks ++;
 519           }
 520
 521 # ifdef VERBOSE_libfirm
 522         fprintf (stdout, "%s: for graph(%p):  %i passes\n",
 523                          __FILE__ ":" __PRETTY_FUNCTION__, graph, walks);
 524 # endif /* def VERBOSE_libfirm */
 525   }
 526
 527   /* ok, now remember it: */
 528   add_dominator_tree (dt);
 529 }