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