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