nsz Git - libfirm/blob - ir/ana/irextbb.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ana/irextbb.c
   4  * Purpose:     Extended basis block support.
   5  * Author:      Michael Beck
   6  * Modified by:
   7  * Created:     5.2005
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 2002-2005 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 /**
  14  * @file irextbb.c
  15  *
  16  *  Computes extended basic blocks.
  17  *
  18  *  @author Michael Beck
  19  */
  20 #include "irextbb_t.h"
  21 #include "irgwalk.h"
  22 #include "irnode_t.h"
  23 #include "irgraph_t.h"
  24 #include "iredges_t.h"
  25 #include "irouts.h"
  26 #include "xmalloc.h"
  27 #include "irprintf.h"
  28
  29 typedef struct _env {
  30   struct obstack *obst;   /**< the obstack where allocations took place */
  31   ir_extblk *head;        /**< head of the list of all extended blocks */
  32 } env_t;
  33
  34 int (is_ir_extbb)(const void *thing) {
  35         return _is_ir_extbb(thing);
  36 }
  37
  38 /**
  39  * allocate a new extended block header.
  40  */
  41 static void allocate_extblk(ir_node *block, env_t *env)
  42 {
  43   ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
  44
  45   extblk->kind    = k_ir_extblk;
  46   extblk->visited = 1;
  47   extblk->blks    = (ir_node **)env->head;
  48   extblk->link    = block;
  49   env->head       = extblk;
  50
  51   set_Block_extbb(block, extblk);
  52   set_irn_link(block, NULL);
  53 }
  54
  55 /**
  56  * add a block to an extended block
  57  */
  58 static void addto_extblk(ir_extblk *extblk, ir_node *block)
  59 {
  60   /* link all blocks belonging to this extended block */
  61   set_irn_link(block, extblk->link);
  62
  63   extblk->link = block;
  64   extblk->visited++;
  65
  66   set_Block_extbb(block, extblk);
  67 }
  68
  69 /**
  70  * Returns the number of block successors.
  71  * we are interested only in 1, 2 and >2.
  72  */
  73 static int get_block_n_succs(ir_node *block) {
  74   if (edges_activated(current_ir_graph)) {
  75     const ir_edge_t *edge;
  76
  77     edge = get_block_succ_first(block);
  78     if (! edge)
  79       return 0;
  80     edge = get_block_succ_next(block, edge);
  81     if (! edge)
  82       return 1;
  83     edge = get_block_succ_next(block, edge);
  84     return edge ? 3 : 2;
  85   }
  86   return get_Block_n_cfg_outs(block);
  87 }
  88
  89 /**
  90  * Pre block-walker. Calculates the extended block info.
  91  */
  92 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
  93 {
  94   int n = get_Block_n_cfgpreds(block);
  95   env_t *env = ctx;
  96
  97   if (n <= 0 || n > 1 ||
  98     block == get_irg_start_block(current_ir_graph)) {
  99     /*
 100      * block is a JOIN-node ie the control flow from
 101      * many other blocks joins here. block is a leader.
 102      * Note that we handle unreachable blocks (n <= 0) here too.
 103      */
 104     allocate_extblk(block, env);
 105   }
 106   else {    /* we have only one control flow predecessor */
 107     ir_node *add_to = get_Block_cfgpred_block(block, 0);
 108
 109     /* blocks with only one BAD predecessors are leaders too */
 110     if (is_Bad(add_to)) {
 111       allocate_extblk(block, env);
 112     }
 113     else {
 114       /*
 115        * Only one control flow predecessor. This block belongs
 116        * to the same extended basic block as its predecessor.
 117        */
 118       ir_node *cf_op = skip_Proj(get_Block_cfgpred(block, 0));
 119
 120       if (irn_not_visited(cf_op)) {
 121         ir_node *pred_bl = get_nodes_block(cf_op);
 122         if (get_block_n_succs(pred_bl) > 2) {
 123           /* More than two successors means we have a jump table.
 124            * we cannot include a jump target into the current extended
 125            * basic block, so create a new one here.
 126            */
 127           allocate_extblk(block, env);
 128         }
 129         else {
 130           /* either the previous block has only one successor or
 131            * this is the first successor after an if, include it.
 132            */
 133           set_Block_extbb(block, NULL);
 134         }
 135         mark_irn_visited(cf_op);
 136       }
 137       else {
 138         /* already marked, so begin a new extended block here */
 139         allocate_extblk(block, env);
 140       }
 141     }
 142   }
 143 }
 144
 145 /** A special extended block used as sentinel */
 146 static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD };
 147
 148 /**
 149  * Post block-walker. Calculates the extended block info.
 150  * During construction, we use the (free) block input of all basic blocks
 151  * to point to there previous block.
 152  */
 153 static void post_walk_calc_extbb(ir_node *block, void *ctx)
 154 {
 155   ir_extblk *extbb = get_Block_extbb(block);
 156   env_t *env = ctx;
 157   ir_extblk *sentinel = &_sentinel;
 158
 159   if (! extbb) {
 160     ir_node *curr, *prev;
 161
 162     /*
 163      * Search the leader. It can happen, that we fall into an endless
 164      * loop, because we enter an unreachable loop that is not yet detected.
 165      * We break the loop using a sentinel.
 166      */
 167     for (curr = block; !extbb; curr = prev) {
 168       prev = get_Block_cfgpred_block(curr, 0);
 169       extbb = get_Block_extbb(prev);
 170       set_Block_extbb(curr, sentinel);
 171     }
 172
 173     if (extbb == sentinel) {
 174       /* We detect a dead loop. We fix this by allocating an
 175        * special Extended block
 176        */
 177       ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
 178
 179       allocate_extblk(block, env);
 180       extbb = get_Block_extbb(block);
 181       set_Block_extbb(block, sentinel);
 182     }
 183
 184     /* replace all sentinels by the extbb info */
 185     prev = block;
 186     while (1) {
 187       if (get_Block_extbb(prev) != sentinel)
 188         break;
 189       set_Block_extbb(prev, extbb);
 190                         ++extbb->visited;
 191                         set_irn_link(prev, extbb->link);
 192                         extbb->link = prev;
 193       prev = get_Block_cfgpred_block(prev, 0);
 194     }
 195   }
 196 }
 197
 198 #ifdef NEED_SORT
 199 /**
 200  * Walker for cf_dependent_on().
 201  * This function searches a node tgt recursively from a given node
 202  * but is restricted to the given extended basic block.
 203  *
 204  * @return 1 if tgt was reachable from curr, 0 if not.
 205  */
 206 static int check_cf_dependence(ir_node *curr, ir_node *tgt, ir_extblk *extbb)
 207 {
 208         int n, i;
 209
 210   /* Note: we did not include the leader in our serach, so
 211      there could not be any loops here. */
 212         if (get_Block_extbb(curr) != extbb)
 213                 return 0;
 214
 215         if (curr == tgt)
 216                 return 1;
 217
 218         for (i = 0, n = get_Block_n_cfgpreds(curr); i < n; ++i) {
 219                 if (check_cf_dependence(get_Block_cfgpred_block(curr, i), tgt, extbb))
 220                         return 1;
 221         }
 222         return 0;
 223 }
 224
 225 /**
 226  * Check if a block is control dependent on another one.
 227  * Both blocks must be in the same extended basic block.
 228  * @param blk1  The first block.
 229  * @param blk2  The second block.
 230  * @return 1, if blk1 is control dependent (transitively) on blk2, 0 if not.
 231  */
 232 static int cf_dependent_on(ir_node *blk1, ir_node *blk2)
 233 {
 234         ir_extblk *extbb = get_Block_extbb(blk1);
 235         ir_graph *irg = get_irn_irg(blk1);
 236
 237         assert(extbb == get_Block_extbb(blk2));
 238         return check_cf_dependence(blk1, blk2, extbb);
 239 }
 240
 241 /**
 242  * Compare two blocks for dependency.
 243  *
 244  * @return
 245  *      0  if both blocks nodes are equal
 246  *      1  block b1 depends on block b2
 247  *      -1 block b2 depends on block d2
 248  */
 249 static int block_order(const void *b1, const void *b2)
 250 {
 251         ir_node *n1 = *(ir_node **)b1;
 252         ir_node *n2 = *(ir_node **)b2;
 253
 254         return n1 == n2 ? 0 : (cf_dependent_on(n1, n2) ? -1 : 1);
 255 }
 256 #endif /* NEED_SORT */
 257
 258 /*
 259  * Compute the extended basic blocks for a graph
 260  */
 261 void compute_extbb(ir_graph *irg) {
 262   env_t env;
 263   ir_extblk *extbb, *next;
 264
 265   if (irg->extbb_obst)
 266     obstack_free(irg->extbb_obst, NULL);
 267   else {
 268     irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
 269   }
 270   obstack_init(irg->extbb_obst);
 271
 272   env.obst = irg->extbb_obst;
 273   env.head = NULL;
 274
 275   if (! edges_activated(irg)) {
 276     /* we don't have edges */
 277     assure_irg_outs(irg);
 278   }
 279
 280   /* we must mark nodes, so increase the visited flag */
 281   inc_irg_visited(irg);
 282   irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
 283
 284   /*
 285    * Ok, we have now the list of all extended blocks starting with env.head
 286    * every extended block "knowns" the number of blocks in visited and
 287    * the blocks are linked in link.
 288    * Now we can create arrays that hold the blocks, some kind of "out" edges
 289    * for the extended block
 290    */
 291   for (extbb = env.head; extbb; extbb = next) {
 292     int i, len = (int)extbb->visited;
 293     ir_node *block;
 294
 295     next = (ir_extblk *)extbb->blks;
 296
 297     extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
 298
 299     for (block = extbb->link, i = 0; i < len; ++i) {
 300       ir_node *nblock = get_irn_link(block);
 301
 302       /* ensure that the leader is the first one */
 303       extbb->blks[len - 1 - i] = block;
 304       set_irn_link(block, NULL);
 305       block = nblock;
 306     }
 307
 308     extbb->link    = NULL;
 309     extbb->visited = 0;
 310
 311 #ifdef NEED_SORT
 312     /* we want the blocks in scheduled order, so sort them */
 313     /* FIXME: is this really needed? Or generates the algorithm automagically ordered ones? */
 314     if (len > 1) {
 315       /* temporary remove the leader from the extended block to break loops */
 316       set_Block_extbb(extbb->blks[0], NULL);
 317       qsort(&extbb->blks[1], len-1, sizeof(extbb->blks[0]), block_order);
 318       set_Block_extbb(extbb->blks[0], extbb);
 319     }
 320 #endif
 321   }
 322
 323   irg->extblk_state = extblk_valid;
 324 }
 325
 326 /* free all extended block info. */
 327 void free_extbb(ir_graph *irg) {
 328   if (irg->extbb_obst) {
 329     obstack_free(irg->extbb_obst, NULL);
 330     xfree(irg->extbb_obst);
 331     irg->extbb_obst = NULL;
 332   }
 333   irg->extblk_state = extblk_none;
 334 }
 335
 336 /* Return the extended block of a node. */
 337 ir_extblk *get_nodes_extbb(ir_node *node) {
 338   ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
 339   return get_Block_extbb(block);
 340 }
 341
 342 /* Gets the visited counter of an extended block. */
 343 unsigned long (get_extbb_visited)(const ir_extblk *blk) {
 344   return _get_extbb_visited(blk);
 345 }
 346
 347 /* Sets the visited counter of an extended block. */
 348 void (set_extbb_visited)(ir_extblk *blk, unsigned long visited) {
 349   _set_extbb_visited(blk, visited);
 350 }
 351
 352 /* Mark an extended block as visited in a graph. */
 353 void (mark_extbb_visited)(ir_extblk *blk) {
 354   _mark_extbb_visited(blk);
 355 }
 356
 357 /* Returns non-zero if an extended was visited. */
 358 int (extbb_visited)(const ir_extblk *blk) {
 359   return _extbb_visited(blk);
 360 }
 361
 362 /* Returns non-zero if an extended block was NOT visited. */
 363 int (extbb_not_visited)(const ir_extblk *blk) {
 364   return _extbb_not_visited(blk);
 365 }
 366
 367 /* Returns the link field of an extended block. */
 368 void *(get_extbb_link)(const ir_extblk *blk) {
 369   return _get_extbb_link(blk);
 370 }
 371
 372 /* Sets the link field of an extended block. */
 373 void (set_extbb_link)(ir_extblk *blk, void *link) {
 374   _set_extbb_link(blk, link);
 375 }
 376
 377 /* Return the number of basic blocks of an extended block */
 378 int (get_extbb_n_blocks)(const ir_extblk *blk) {
 379   return _get_extbb_n_blocks(blk);
 380 }
 381
 382 /* Return the i'th basic block of an extended block */
 383 ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
 384   return _get_extbb_block(blk, pos);
 385 }
 386
 387 /* Return the leader basis block of an extended block. */
 388 ir_node *(get_extbb_leader)(ir_extblk *blk) {
 389   return _get_extbb_leader(blk);
 390 }
 391
 392 /* Return the node number of an extended block. */
 393 long get_extbb_node_nr(ir_extblk *blk) {
 394   return get_irn_node_nr(get_extbb_leader(blk));
 395 }
 396
 397 static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 398 {
 399   int i;
 400   ir_node *node;
 401
 402   if (extbb_not_visited(blk)) {
 403     mark_extbb_visited(blk);
 404
 405     if (pre) pre(blk, env);
 406
 407     node = get_extbb_leader(blk);
 408     for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 409       /* find the corresponding predecessor block. */
 410       ir_node *pred = get_Block_cfgpred_block(node, i);
 411       if (is_Block(pred)) {
 412         /* recursion */
 413         irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
 414       }
 415       else {
 416         assert(is_Bad(pred));
 417       }
 418     }
 419
 420     if (post) post(blk, env);
 421   }
 422 }
 423
 424 /* walks only over extended Block nodes in the graph.  Has it's own visited
 425    flag, so that it can be interleaved with the other walker.         */
 426 void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 427 {
 428   ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
 429   ir_extblk *start_blk = get_Block_extbb(start_bl);
 430   int i;
 431
 432   assert(blk);
 433   assert(!get_interprocedural_view());   /* interprocedural_view not implemented */
 434   inc_irg_block_visited(current_ir_graph);
 435
 436   /* assure the start block is the first one */
 437   mark_extbb_visited(start_blk);
 438   if (post)
 439     post(start_blk, env);
 440   irg_extblock_walk_2(blk, pre, post, env);
 441
 442   /* keepalive: the endless loops ... */
 443   if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
 444     ir_node *node = get_irg_end(current_ir_graph);
 445     int arity = get_irn_arity(node);
 446     for (i = 0; i < arity; i++) {
 447       pred = get_irn_n(node, i);
 448       if (is_Block(pred))
 449         irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
 450       else if (is_Phi(pred)) {
 451         /* Sometimes the blocks died, but are still reachable through Phis.
 452          * Make sure the algorithms that try to remove these reach them. */
 453         ir_node *block = get_nodes_block(pred);
 454
 455         if (! is_Bad(block))
 456           irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
 457       }
 458     }
 459   }
 460
 461   if (pre)
 462     pre(start_blk, env);
 463 }
 464
 465 /* Walks only over reachable Extended Basic Block nodes in the graph. */
 466 void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 467 {
 468   ir_node *endbl = get_irg_end_block(irg);
 469   ir_extblk *blk = get_Block_extbb(endbl);
 470   ir_graph *rem  = current_ir_graph;
 471   current_ir_graph = irg;
 472   irg_extblock_walk(blk, pre, post, env);
 473   current_ir_graph = rem;
 474 }