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 "xmalloc.h"
  24 #include "irprintf.h"
  25
  26 typedef struct _env {
  27   struct obstack *obst;   /**< the obstack where allocations took place */
  28   ir_extblk *head;        /**< head of the list of all extended blocks */
  29 } env_t;
  30
  31 /**
  32  * allocate a new extended block header.
  33  */
  34 static void allocate_extblk(ir_node *block, env_t *env)
  35 {
  36   ir_extblk *extblk = obstack_alloc(env->obst, sizeof(*extblk));
  37
  38   extblk->kind    = k_ir_extblk;
  39   extblk->visited = 1;
  40   extblk->blks    = (ir_node **)env->head;
  41   extblk->link    = block;
  42   env->head       = extblk;
  43
  44   set_Block_extbb(block, extblk);
  45   set_irn_link(block, NULL);
  46 }
  47
  48 /**
  49  * add a block to an extended block
  50  */
  51 static void addto_extblk(ir_extblk *extblk, ir_node *block)
  52 {
  53   /* link all blocks belonging to this extended block */
  54   set_irn_link(block, extblk->link);
  55
  56   extblk->link = block;
  57   extblk->visited++;
  58
  59   set_Block_extbb(block, extblk);
  60 }
  61
  62
  63 /**
  64  * Pre block-walker. Calculates the extended block info.
  65  */
  66 static void pre_walk_calc_extbb(ir_node *block, void *ctx)
  67 {
  68   int n = get_Block_n_cfgpreds(block);
  69   env_t *env = ctx;
  70
  71   if (n <= 0 || n > 1 || block == get_irg_start_block(current_ir_graph)) {
  72     /*
  73      * block is a JOIN-node ie the control flow from
  74      * many other blocks joins here. block is a leader.
  75      * Note that we handle unreachable blocks (n <= 0) here too.
  76      */
  77     allocate_extblk(block, env);
  78   }
  79   else {    /* we have only one control flow predecessor */
  80     ir_node *add_to = get_Block_cfgpred_block(block, 0);
  81
  82     /* blocks with only one BAD predecessors are leaders too */
  83     if (is_Bad(add_to)) {
  84       allocate_extblk(block, env);
  85     }
  86     else {
  87       /*
  88        * Only one control flow predecessor. This block belongs
  89        * to the same extended basic block as its predecessor.
  90        */
  91       set_Block_extbb(block, NULL);
  92     }
  93   }
  94 }
  95
  96 static int _sentinel;
  97
  98 /**
  99  * Post block-walker. Calculates the extended block info.
 100  * During construction, we use the (free) block input of all basic blocks
 101  * to point to there previous block.
 102  */
 103 static void post_walk_calc_extbb(ir_node *block, void *ctx)
 104 {
 105   ir_extblk *extbb = get_Block_extbb(block);
 106   env_t *env = ctx;
 107   ir_extblk *sentinel = (ir_extblk *)&_sentinel;
 108
 109   if (! extbb) {
 110     ir_node *curr, *prev;
 111
 112     /*
 113      * Search the leader. It can happen, that we fall into an endless
 114      * loop, because we enter an unreachable loop that is not yet detected.
 115      * We break the loop using a sentinel.
 116      */
 117     for (curr = block; !extbb; curr = prev) {
 118       prev = get_Block_cfgpred_block(curr, 0);
 119       extbb = get_Block_extbb(prev);
 120       set_Block_extbb(curr, sentinel);
 121     }
 122
 123     if (extbb == sentinel) {
 124       /* We detect a dead loop. We fix this by allocating an
 125        * special Extended block
 126        */
 127       ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
 128
 129       allocate_extblk(block, env);
 130       extbb = get_Block_extbb(block);
 131       set_Block_extbb(block, sentinel);
 132     }
 133
 134     /* replace all sentinels by the extbb info */
 135     prev = block;
 136     while (1) {
 137       if (get_Block_extbb(prev) != sentinel)
 138         break;
 139       set_Block_extbb(prev, extbb);
 140       prev = get_Block_cfgpred_block(prev, 0);
 141     }
 142   }
 143 }
 144
 145 /*
 146  * Compute the extended basic blocks for a graph
 147  */
 148 void compute_extbb(ir_graph *irg) {
 149   env_t env;
 150   ir_extblk *extbb, *next;
 151
 152   if (irg->extbb_obst)
 153     obstack_free(irg->extbb_obst, NULL);
 154   else {
 155     irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
 156   }
 157   obstack_init(irg->extbb_obst);
 158
 159   env.obst = irg->extbb_obst;
 160   env.head = NULL;
 161
 162   irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
 163
 164   /*
 165    * Ok, we have now the list of all extended blocks starting with env.head
 166    * every extended block "knowns" the number of blocks in visited and
 167    * the blocks are linked in link.
 168    * Now we can create arrays that hold the blocks, some kind of "out" edges
 169    * for the extended block
 170    */
 171   for (extbb = env.head; extbb; extbb = next) {
 172     int i, len = (int)extbb->visited;
 173     ir_node *block;
 174
 175     next = (ir_extblk *)extbb->blks;
 176
 177     extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
 178
 179     for (block = extbb->link, i = 0; i < len; ++i) {
 180       ir_node *nblock = get_irn_link(block);
 181
 182       /* ensure that the leader is the first one */
 183       extbb->blks[len - 1 - i] = block;
 184       set_irn_link(block, NULL);
 185       block = nblock;
 186     }
 187
 188     extbb->link    = NULL;
 189     extbb->visited = 0;
 190   }
 191
 192   irg->extblk_state = ir_extblk_info_valid;
 193 }
 194
 195 /* free all extended block info. */
 196 void free_extbb(ir_graph *irg) {
 197   if (irg->extbb_obst) {
 198     obstack_free(irg->extbb_obst, NULL);
 199     xfree(irg->extbb_obst);
 200     irg->extbb_obst = NULL;
 201   }
 202   irg->extblk_state = ir_extblk_info_none;
 203 }
 204
 205 /* Return the extended block of a node. */
 206 ir_extblk *get_nodes_extbb(ir_node *node) {
 207   ir_node *block = is_Block(node) ? node : get_irn_n(node, -1);
 208   return get_Block_extbb(block);
 209 }
 210
 211 /* Gets the visited counter of an extended block. */
 212 unsigned long (get_extbb_visited)(const ir_extblk *blk) {
 213   return _get_extbb_visited(blk);
 214 }
 215
 216 /* Sets the visited counter of an extended block. */
 217 void (set_extbb_visited)(ir_extblk *blk, unsigned long visited) {
 218   _set_extbb_visited(blk, visited);
 219 }
 220
 221 /* Mark an extended block as visited in a graph. */
 222 void (mark_extbb_visited)(ir_extblk *blk) {
 223   _mark_extbb_visited(blk);
 224 }
 225
 226 /* Returns non-zero if an extended was visited. */
 227 int (extbb_visited)(const ir_extblk *blk) {
 228   return _extbb_visited(blk);
 229 }
 230
 231 /* Returns non-zero if an extended block was NOT visited. */
 232 int (extbb_not_visited)(const ir_extblk *blk) {
 233   return _extbb_not_visited(blk);
 234 }
 235
 236 /* Returns the link field of an extended block. */
 237 void *(get_extbb_link)(const ir_extblk *blk) {
 238   return _get_extbb_link(blk);
 239 }
 240
 241 /* Sets the link field of an extended block. */
 242 void (set_extbb_link)(ir_extblk *blk, void *link) {
 243   _set_extbb_link(blk, link);
 244 }
 245
 246 /* Return the number of basic blocks of an extended block */
 247 int (get_extbb_n_blocks)(const ir_extblk *blk) {
 248   return _get_extbb_n_blocks(blk);
 249 }
 250
 251 /* Return the i'th basic block of an extended block */
 252 ir_node *(get_extbb_block)(ir_extblk *blk, int pos) {
 253   return _get_extbb_block(blk, pos);
 254 }
 255
 256 /* Return the leader basis block of an extended block. */
 257 ir_node *(get_extbb_leader)(ir_extblk *blk) {
 258   return _get_extbb_leader(blk);
 259 }
 260
 261 /* Return the node number of an extended block. */
 262 long get_extbb_node_nr(ir_extblk *blk) {
 263   return get_irn_node_nr(get_extbb_leader(blk));
 264 }