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