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 "xmalloc.h"
  25 #include "irprintf.h"
  26
  27 typedef struct _env {
  28   struct obstack *obst;   /**< the obstack where allocations took place */
  29   ir_extblk *head;        /**< head of the list of all extended blocks */
  30 } env_t;
  31
  32 /**
  33  * allocate a new extended block header.
  34  */
  35 static void allocate_extblk(ir_node *block, env_t *env)
  36 {
  37   ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
  38
  39   extblk->kind    = k_ir_extblk;
  40   extblk->visited = 1;
  41   extblk->blks    = (ir_node **)env->head;
  42   extblk->link    = block;
  43   env->head       = extblk;
  44
  45   set_Block_extbb(block, extblk);
  46   set_irn_link(block, NULL);
  47 }
  48
  49 /**
  50  * add a block to an extended block
  51  */
  52 static void addto_extblk(ir_extblk *extblk, ir_node *block)
  53 {
  54   /* link all blocks belonging to this extended block */
  55   set_irn_link(block, extblk->link);
  56
  57   extblk->link = block;
  58   extblk->visited++;
  59
  60   set_Block_extbb(block, extblk);
  61 }
  62
  63
  64 /**
  65  * Pre block-walker. Calculates the extended block info.
  66  */
  67 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
  68 {
  69   int n = get_Block_n_cfgpreds(block);
  70   env_t *env = ctx;
  71
  72   if (n <= 0 || n > 1 ||
  73                   block == get_irg_start_block(current_ir_graph) ||
  74                         block == get_irg_end_block(current_ir_graph)) {
  75     /*
  76      * block is a JOIN-node ie the control flow from
  77      * many other blocks joins here. block is a leader.
  78      * Note that we handle unreachable blocks (n <= 0) here too.
  79      */
  80     allocate_extblk(block, env);
  81   }
  82   else {    /* we have only one control flow predecessor */
  83     ir_node *add_to = get_Block_cfgpred_block(block, 0);
  84
  85     /* blocks with only one BAD predecessors are leaders too */
  86     if (is_Bad(add_to)) {
  87       allocate_extblk(block, env);
  88     }
  89     else {
  90       /*
  91        * Only one control flow predecessor. This block belongs
  92        * to the same extended basic block as its predecessor.
  93        */
  94       set_Block_extbb(block, NULL);
  95     }
  96   }
  97 }
  98
  99 static int _sentinel;
 100
 101 /**
 102  * Post block-walker. Calculates the extended block info.
 103  * During construction, we use the (free) block input of all basic blocks
 104  * to point to there previous block.
 105  */
 106 static void post_walk_calc_extbb(ir_node *block, void *ctx)
 107 {
 108   ir_extblk *extbb = get_Block_extbb(block);
 109   env_t *env = ctx;
 110   ir_extblk *sentinel = (ir_extblk *)&_sentinel;
 111
 112   if (! extbb) {
 113     ir_node *curr, *prev;
 114
 115     /*
 116      * Search the leader. It can happen, that we fall into an endless
 117      * loop, because we enter an unreachable loop that is not yet detected.
 118      * We break the loop using a sentinel.
 119      */
 120     for (curr = block; !extbb; curr = prev) {
 121       prev = get_Block_cfgpred_block(curr, 0);
 122       extbb = get_Block_extbb(prev);
 123       set_Block_extbb(curr, sentinel);
 124     }
 125
 126     if (extbb == sentinel) {
 127       /* We detect a dead loop. We fix this by allocating an
 128        * special Extended block
 129        */
 130       ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
 131
 132       allocate_extblk(block, env);
 133       extbb = get_Block_extbb(block);
 134       set_Block_extbb(block, sentinel);
 135     }
 136
 137     /* replace all sentinels by the extbb info */
 138     prev = block;
 139     while (1) {
 140       if (get_Block_extbb(prev) != sentinel)
 141         break;
 142       set_Block_extbb(prev, extbb);
 143                         ++extbb->visited;
 144                         set_irn_link(prev, extbb->link);
 145                         extbb->link = prev;
 146       prev = get_Block_cfgpred_block(prev, 0);
 147     }
 148   }
 149 }
 150
 151 /*
 152  * Compute the extended basic blocks for a graph
 153  */
 154 void compute_extbb(ir_graph *irg) {
 155   env_t env;
 156   ir_extblk *extbb, *next;
 157
 158   if (irg->extbb_obst)
 159     obstack_free(irg->extbb_obst, NULL);
 160   else {
 161     irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
 162   }
 163   obstack_init(irg->extbb_obst);
 164
 165   env.obst = irg->extbb_obst;
 166   env.head = NULL;
 167
 168   irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
 169
 170   /*
 171    * Ok, we have now the list of all extended blocks starting with env.head
 172    * every extended block "knowns" the number of blocks in visited and
 173    * the blocks are linked in link.
 174    * Now we can create arrays that hold the blocks, some kind of "out" edges
 175    * for the extended block
 176    */
 177   for (extbb = env.head; extbb; extbb = next) {
 178     int i, len = (int)extbb->visited;
 179     ir_node *block;
 180
 181     next = (ir_extblk *)extbb->blks;
 182
 183     extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
 184
 185     for (block = extbb->link, i = 0; i < len; ++i) {
 186       ir_node *nblock = get_irn_link(block);
 187
 188       /* ensure that the leader is the first one */
 189       extbb->blks[len - 1 - i] = block;
 190       set_irn_link(block, NULL);
 191       block = nblock;
 192     }
 193
 194     extbb->link    = NULL;
 195     extbb->visited = 0;
 196   }
 197
 198   irg->extblk_state = ir_extblk_info_valid;
 199 }
 200
 201 /* free all extended block info. */
 202 void free_extbb(ir_graph *irg) {
 203   if (irg->extbb_obst) {
 204     obstack_free(irg->extbb_obst, NULL);
 205     xfree(irg->extbb_obst);
 206     irg->extbb_obst = NULL;
 207   }
 208   irg->extblk_state = ir_extblk_info_none;
 209 }
 210
 211 /* Return the extended block of a node. */
 212 ir_extblk *get_nodes_extbb(ir_node *node) {
 213   ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
 214   return get_Block_extbb(block);
 215 }
 216
 217 /* Gets the visited counter of an extended block. */
 218 unsigned long (get_extbb_visited)(const ir_extblk *blk) {
 219   return _get_extbb_visited(blk);
 220 }
 221
 222 /* Sets the visited counter of an extended block. */
 223 void (set_extbb_visited)(ir_extblk *blk, unsigned long visited) {
 224   _set_extbb_visited(blk, visited);
 225 }
 226
 227 /* Mark an extended block as visited in a graph. */
 228 void (mark_extbb_visited)(ir_extblk *blk) {
 229   _mark_extbb_visited(blk);
 230 }
 231
 232 /* Returns non-zero if an extended was visited. */
 233 int (extbb_visited)(const ir_extblk *blk) {
 234   return _extbb_visited(blk);
 235 }
 236
 237 /* Returns non-zero if an extended block was NOT visited. */
 238 int (extbb_not_visited)(const ir_extblk *blk) {
 239   return _extbb_not_visited(blk);
 240 }
 241
 242 /* Returns the link field of an extended block. */
 243 void *(get_extbb_link)(const ir_extblk *blk) {
 244   return _get_extbb_link(blk);
 245 }
 246
 247 /* Sets the link field of an extended block. */
 248 void (set_extbb_link)(ir_extblk *blk, void *link) {
 249   _set_extbb_link(blk, link);
 250 }
 251
 252 /* Return the number of basic blocks of an extended block */
 253 int (get_extbb_n_blocks)(const ir_extblk *blk) {
 254   return _get_extbb_n_blocks(blk);
 255 }
 256
 257 /* Return the i'th basic block of an extended block */
 258 ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
 259   return _get_extbb_block(blk, pos);
 260 }
 261
 262 /* Return the leader basis block of an extended block. */
 263 ir_node *(get_extbb_leader)(ir_extblk *blk) {
 264   return _get_extbb_leader(blk);
 265 }
 266
 267 /* Return the node number of an extended block. */
 268 long get_extbb_node_nr(ir_extblk *blk) {
 269   return get_irn_node_nr(get_extbb_leader(blk));
 270 }
 271
 272 static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 273 {
 274   int i;
 275   ir_node *node;
 276
 277   if (extbb_not_visited(blk)) {
 278     mark_extbb_visited(blk);
 279
 280     if (pre) pre(blk, env);
 281
 282     node = get_extbb_leader(blk);
 283     for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 284       /* find the corresponding predecessor block. */
 285       ir_node *pred = get_Block_cfgpred_block(node, i);
 286       if (is_Block(pred)) {
 287         /* recursion */
 288         irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
 289       }
 290       else {
 291         assert(is_Bad(pred));
 292       }
 293     }
 294
 295     if (post) post(blk, env);
 296   }
 297 }
 298
 299 /* walks only over extended Block nodes in the graph.  Has it's own visited
 300    flag, so that it can be interleaved with the other walker.         */
 301 void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 302 {
 303   ir_node *block, *pred;
 304   int i;
 305
 306   assert(blk);
 307   assert(!get_interprocedural_view());   /* interprocedural_view not implemented */
 308   inc_irg_block_visited(current_ir_graph);
 309   irg_extblock_walk_2(block, pre, post, env);
 310
 311   /* keepalive: the endless loops ... */
 312   if (get_extbb_leader(blk) == get_irg_end_block(current_ir_graph)) {
 313     ir_node *node = get_irg_end(current_ir_graph);
 314     int arity = get_irn_arity(node);
 315     for (i = 0; i < arity; i++) {
 316       pred = get_irn_n(node, i);
 317       if (is_Block(pred))
 318         irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
 319       else if (is_Phi(pred)) {
 320         /* Sometimes the blocks died, but are still reachable through Phis.
 321          * Make sure the algorithms that try to remove these reach them. */
 322         ir_node *block = get_nodes_block(pred);
 323
 324         if (! is_Bad(block))
 325           irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
 326       }
 327     }
 328   }
 329 }
 330
 331 /* Walks only over reachable Extended Basic Block nodes in the graph. */
 332 void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 333 {
 334   ir_node *end = get_irg_end(irg);
 335   ir_extblk *blk = get_Block_extbb(end);
 336   ir_graph *rem  = current_ir_graph;
 337   current_ir_graph = irg;
 338   irg_extblock_walk(blk, pre, post, env);
 339   current_ir_graph = rem;
 340 }