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