nsz Git - libfirm/blob - ir/ana/irextbb.c

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