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