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

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