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