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 #include "config.h"
  28
  29 #include "irextbb_t.h"
  30 #include "irgwalk.h"
  31 #include "irnode_t.h"
  32 #include "irgraph_t.h"
  33 #include "iredges_t.h"
  34 #include "irouts.h"
  35 #include "xmalloc.h"
  36 #include "irprintf.h"
  37
  38 /**
  39  * Environment for extbb construction.
  40  */
  41 typedef struct env {
  42         struct obstack *obst;   /**< the obstack where allocations took place */
  43         ir_extblk *head;        /**< head of the list of all extended blocks */
  44         ir_node *start_block;   /**< the start block of the current graph */
  45 } env_t;
  46
  47 int (is_ir_extbb)(const void *thing)
  48 {
  49         return _is_ir_extbb(thing);
  50 }
  51
  52 /**
  53  * allocate a new extended block header.
  54  */
  55 static void allocate_extblk(ir_node *block, env_t *env)
  56 {
  57         ir_extblk *extblk = OALLOC(env->obst, ir_extblk);
  58
  59         extblk->kind    = k_ir_extblk;
  60         extblk->visited = 1;
  61         extblk->blks    = (ir_node **)env->head;
  62         extblk->link    = block;
  63         env->head       = extblk;
  64
  65         set_Block_extbb(block, extblk);
  66         set_irn_link(block, NULL);
  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 {
  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 = (env_t*) 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_visited_else_mark(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                         } else {
 134                                 /* already marked, so begin a new extended block here */
 135                                 allocate_extblk(block, env);
 136                         }
 137                 }
 138         }
 139 }
 140
 141 /** A special extended block used as sentinel */
 142 static ir_extblk _sentinel = { k_ir_extblk, 0xFEA1DEAD, NULL, NULL };
 143
 144 /**
 145  * Post block-walker. Calculates the extended block info.
 146  * During construction, we use the (free) block input of all basic blocks
 147  * to point to there previous block.
 148  */
 149 static void post_walk_calc_extbb(ir_node *block, void *ctx)
 150 {
 151         ir_extblk *extbb = get_Block_extbb(block);
 152         env_t *env = (env_t*) ctx;
 153         ir_extblk *sentinel = &_sentinel;
 154
 155         if (! extbb) {
 156                 ir_node *curr, *prev, *list;
 157
 158                 /*
 159                  * Search the leader. It can happen, that we fall into an endless
 160                  * loop, because we enter an unreachable loop that is not yet detected.
 161                  * We break the loop using a sentinel.
 162                  */
 163                 for (curr = block; !extbb; curr = prev) {
 164                         prev = get_Block_cfgpred_block(curr, 0);
 165                         extbb = get_Block_extbb(prev);
 166                         set_Block_extbb(curr, sentinel);
 167                 }
 168
 169                 if (extbb == sentinel) {
 170                         /* We detect a dead loop. We fix this by allocating a
 171                          * special Extended block
 172                          */
 173                         ir_printf("Dead loop detected starting with %+F::%+F\n", get_irg_entity(current_ir_graph), block);
 174
 175                         allocate_extblk(block, env);
 176                         extbb = get_Block_extbb(block);
 177                         set_Block_extbb(block, sentinel);
 178                 }
 179
 180                 /* replace all sentinels by the extbb info */
 181                 prev = block;
 182                 list = NULL;
 183                 for (;;) {
 184                         if (get_Block_extbb(prev) != sentinel)
 185                                 break;
 186                         set_irn_link(prev, list);
 187                         list = prev;
 188                         prev = get_Block_cfgpred_block(prev, 0);
 189                 }
 190                 /* arg, the list is in wrong order, turn around and add to the extbb list */
 191                 for (curr = list; curr; curr = prev) {
 192                         prev = (ir_node*) get_irn_link(curr);
 193                         set_irn_link(curr, extbb->link);
 194                         extbb->link = curr;
 195                         set_Block_extbb(curr, extbb);
 196                         ++extbb->visited;
 197                 }
 198         }
 199 }
 200
 201 /*
 202  * Compute the extended basic blocks for a graph
 203  */
 204 void compute_extbb(ir_graph *irg)
 205 {
 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(struct obstack);
 213         obstack_init(irg->extbb_obst);
 214
 215         env.obst        = irg->extbb_obst;
 216         env.head        = NULL;
 217         env.start_block = get_irg_start_block(irg);
 218
 219         if (! edges_activated(irg)) {
 220                 /* we don't have edges */
 221                 assure_irg_outs(irg);
 222         }
 223
 224         /* we must mark nodes, so increase the visited flag */
 225         inc_irg_visited(irg);
 226         irg_block_walk_graph(irg, pre_walk_calc_extbb, post_walk_calc_extbb, &env);
 227
 228         /*
 229          * Ok, we have now the list of all extended blocks starting with env.head
 230          * every extended block "knowns" the number of blocks in visited and
 231          * the blocks are linked in link.
 232          * Now we can create arrays that hold the blocks, some kind of "out" edges
 233          * for the extended block
 234          */
 235         for (extbb = env.head; extbb; extbb = next) {
 236                 int i, len = (int)extbb->visited;
 237                 ir_node *block;
 238
 239                 next = (ir_extblk *)extbb->blks;
 240
 241                 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
 242
 243                 for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) {
 244                         ir_node *nblock = (ir_node*) get_irn_link(block);
 245
 246                         /* ensure that the leader is the first one */
 247                         extbb->blks[len - 1 - i] = block;
 248                         set_irn_link(block, NULL);
 249                         block = nblock;
 250                 }
 251
 252 #ifndef NDEBUG
 253                 /* check it */
 254                 for (i = len - 1; i > 0; --i) {
 255                         ir_node *blk = extbb->blks[i];
 256
 257                         if (get_Block_n_cfgpreds(blk) != 1) {
 258                                 assert(!"Block for more than one predecessors is no leader");
 259                         } else if (get_Block_cfgpred_block(blk, 0) != extbb->blks[i - 1]) {
 260                                 assert(!"extbb block order wrong");
 261                         }
 262                 }
 263 #endif
 264
 265                 extbb->link    = NULL;
 266                 extbb->visited = 0;
 267         }
 268
 269         set_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
 270 }
 271
 272 /* free all extended block info. */
 273 void free_extbb(ir_graph *irg)
 274 {
 275         if (irg->extbb_obst) {
 276                 obstack_free(irg->extbb_obst, NULL);
 277                 xfree(irg->extbb_obst);
 278                 irg->extbb_obst = NULL;
 279         }
 280         clear_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
 281 }
 282
 283 /* Return the extended block of a node. */
 284 ir_extblk *get_nodes_extbb(const ir_node *node)
 285 {
 286         const ir_node *block = is_Block(node) ? node : get_nodes_block(node);
 287         return get_Block_extbb(block);
 288 }
 289
 290 /* Gets the visited counter of an extended block. */
 291 ir_visited_t (get_extbb_visited)(const ir_extblk *blk)
 292 {
 293         return _get_extbb_visited(blk);
 294 }
 295
 296 /* Sets the visited counter of an extended block. */
 297 void (set_extbb_visited)(ir_extblk *blk, ir_visited_t visited)
 298 {
 299         _set_extbb_visited(blk, visited);
 300 }
 301
 302 /* Mark an extended block as visited in a graph. */
 303 void (mark_extbb_visited)(ir_extblk *blk)
 304 {
 305         _mark_extbb_visited(blk);
 306 }
 307
 308 /* Returns non-zero if an extended was visited. */
 309 int (extbb_visited)(const ir_extblk *blk)
 310 {
 311         return _extbb_visited(blk);
 312 }
 313
 314 /* Returns non-zero if an extended block was NOT visited. */
 315 int (extbb_not_visited)(const ir_extblk *blk)
 316 {
 317         return _extbb_not_visited(blk);
 318 }
 319
 320 /* Returns the link field of an extended block. */
 321 void *(get_extbb_link)(const ir_extblk *blk)
 322 {
 323         return _get_extbb_link(blk);
 324 }
 325
 326 /* Sets the link field of an extended block. */
 327 void (set_extbb_link)(ir_extblk *blk, void *link)
 328 {
 329         _set_extbb_link(blk, link);
 330 }
 331
 332 /* Return the number of basic blocks of an extended block */
 333 int (get_extbb_n_blocks)(const ir_extblk *blk)
 334 {
 335         return _get_extbb_n_blocks(blk);
 336 }
 337
 338 /* Return the i'th basic block of an extended block */
 339 ir_node *(get_extbb_block)(const ir_extblk *blk, int pos)
 340 {
 341         return _get_extbb_block(blk, pos);
 342 }
 343
 344 /* Return the leader basis block of an extended block. */
 345 ir_node *(get_extbb_leader)(const ir_extblk *blk)
 346 {
 347         return _get_extbb_leader(blk);
 348 }
 349
 350 /* Return the node number of an extended block. */
 351 long get_extbb_node_nr(const ir_extblk *blk)
 352 {
 353         return get_irn_node_nr(get_extbb_leader(blk));
 354 }
 355
 356 static void irg_extblock_walk_2(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 357 {
 358         int i;
 359         ir_node *node;
 360
 361         if (extbb_not_visited(blk)) {
 362                 mark_extbb_visited(blk);
 363
 364                 if (pre) pre(blk, env);
 365
 366                 node = get_extbb_leader(blk);
 367                 for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 368                         /* find the corresponding predecessor block. */
 369                         ir_node *pred = get_Block_cfgpred_block(node, i);
 370                         if (is_Block(pred)) {
 371                                 /* recursion */
 372                                 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
 373                         }
 374                         else {
 375                                 assert(is_Bad(pred));
 376                         }
 377                 }
 378
 379                 if (post) post(blk, env);
 380         }
 381 }
 382
 383 /* walks only over extended Block nodes in the graph.  Has its own visited
 384    flag, so that it can be interleaved with the other walker.         */
 385 void irg_extblock_walk(ir_extblk *blk, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 386 {
 387         ir_node *pred, *start_bl = get_irg_start_block(current_ir_graph);
 388         ir_extblk *start_blk = get_Block_extbb(start_bl);
 389         int i;
 390
 391         assert(blk);
 392         inc_irg_block_visited(current_ir_graph);
 393
 394         /* assure the start block is the first one */
 395         mark_extbb_visited(start_blk);
 396         if (post)
 397                 post(start_blk, env);
 398         irg_extblock_walk_2(blk, pre, post, env);
 399
 400         /* keepalive: the endless loops ... */
 401         if (blk == get_Block_extbb(get_irg_end_block(current_ir_graph))) {
 402                 ir_node *node = get_irg_end(current_ir_graph);
 403                 int arity = get_irn_arity(node);
 404                 for (i = 0; i < arity; i++) {
 405                         pred = get_irn_n(node, i);
 406                         if (is_Block(pred))
 407                                 irg_extblock_walk_2(get_Block_extbb(pred), pre, post, env);
 408                         else if (is_Phi(pred)) {
 409                                 /* Sometimes the blocks died, but are still reachable through Phis.
 410                                  * Make sure the algorithms that try to remove these reach them. */
 411                                 ir_node *block = get_nodes_block(pred);
 412
 413                                 if (! is_Bad(block))
 414                                         irg_extblock_walk_2(get_Block_extbb(block), pre, post, env);
 415                         }
 416                 }
 417         }
 418
 419         if (pre)
 420                 pre(start_blk, env);
 421 }
 422
 423 /* Walks only over reachable Extended Basic Block nodes in the graph. */
 424 void irg_extblock_walk_graph(ir_graph *irg, extbb_walk_func *pre, extbb_walk_func *post, void *env)
 425 {
 426         ir_node *endbl = get_irg_end_block(irg);
 427         ir_extblk *blk = get_Block_extbb(endbl);
 428         ir_graph *rem  = current_ir_graph;
 429         current_ir_graph = irg;
 430         irg_extblock_walk(blk, pre, post, env);
 431         current_ir_graph = rem;
 432 }