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