nsz Git - libfirm/blob - ir/ana/irextbb2.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     Alternative extended basic block computation
  23  * @author    Matthias Braun
  24  * @date      5.2005
  25  * @version   $Id$
  26  * @brief
  27  *  Alternative algorithm for computing extended basic blocks (using out edges
  28  *  and execution frequencies)
  29  */
  30 #include "config.h"
  31
  32 #include "irextbb_t.h"
  33 #include "irgwalk.h"
  34 #include "irnode_t.h"
  35 #include "irgraph_t.h"
  36 #include "iredges_t.h"
  37 #include "irouts.h"
  38 #include "xmalloc.h"
  39 #include "irprintf.h"
  40 #include "execfreq.h"
  41
  42 typedef struct env {
  43         struct obstack *obst;   /**< the obstack where allocations took place */
  44         ir_extblk *head;        /**< head of the list of all extended blocks */
  45         ir_exec_freq *execfreqs;
  46 } env_t;
  47
  48 /**
  49  * allocate a new extended block header.
  50  */
  51 static ir_extblk *allocate_extblk(ir_node *block, env_t *env)
  52 {
  53         ir_extblk *extblk = OALLOC(env->obst, ir_extblk);
  54
  55         extblk->kind    = k_ir_extblk;
  56         extblk->visited = 1;
  57         extblk->blks    = (ir_node **)env->head;
  58         extblk->link    = block;
  59         env->head       = extblk;
  60
  61         set_Block_extbb(block, extblk);
  62         set_irn_link(block, NULL);
  63
  64         return extblk;
  65 }
  66
  67 /**
  68  * add a block to an extended block
  69  */
  70 static void addto_extblk(ir_extblk *extblk, ir_node *block)
  71 {
  72         /* link all blocks belonging to this extended block */
  73         set_irn_link(block, extblk->link);
  74
  75         extblk->link = block;
  76         extblk->visited++;
  77
  78         set_Block_extbb(block, extblk);
  79 }
  80
  81 /**
  82  * Returns the number of block successors.
  83  * we are interested only in 1, 2 and >2.
  84  */
  85 static int get_block_n_succs(ir_node *block)
  86 {
  87         if (edges_activated(current_ir_graph)) {
  88                 const ir_edge_t *edge;
  89
  90                 edge = get_block_succ_first(block);
  91                 if (! edge)
  92                         return 0;
  93
  94                 edge = get_block_succ_next(block, edge);
  95                 if (! edge)
  96                         return 1;
  97
  98                 edge = get_block_succ_next(block, edge);
  99                 return edge ? 3 : 2;
 100         }
 101
 102         return get_Block_n_cfg_outs(block);
 103 }
 104
 105 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env);
 106
 107 static void create_extblk(ir_node *block, env_t *env)
 108 {
 109         ir_extblk *extblk;
 110
 111         if (irn_visited_else_mark(block))
 112                 return;
 113
 114         extblk = allocate_extblk(block, env);
 115
 116         pick_successor(block, extblk, env);
 117 }
 118
 119 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
 120 {
 121         const ir_edge_t *edge;
 122         ir_node         *best_succ    = NULL;
 123         double          best_execfreq = -1;
 124
 125         /*
 126                 More than two successors means we have a jump table.
 127                 we cannot include a jump target into the current extended
 128                 basic block, so create a new one here.
 129         */
 130         if (get_block_n_succs(block) > 2) {
 131                 foreach_block_succ(block, edge) {
 132                         ir_node *succ = get_edge_src_irn(edge);
 133                         create_extblk(succ, env);
 134                 }
 135
 136                 return;
 137         }
 138
 139         foreach_block_succ(block, edge) {
 140                 ir_node *succ = get_edge_src_irn(edge);
 141                 double execfreq;
 142
 143                 if (irn_visited(succ))
 144                         continue;
 145
 146                 if (get_Block_n_cfgpreds(succ) > 1) {
 147                         create_extblk(succ, env);
 148                         continue;
 149                 }
 150
 151                 execfreq = get_block_execfreq(env->execfreqs, succ);
 152
 153                 /*
 154                         Remember best successor and make non best successor with only 1
 155                         pred block to new extbb leaders.
 156                 */
 157                 if (execfreq > best_execfreq) {
 158                         if (best_succ != NULL) {
 159                                 create_extblk(best_succ, env);
 160                         }
 161
 162                         best_execfreq = execfreq;
 163                         best_succ = succ;
 164                 }
 165                 else {
 166                         create_extblk(succ, env);
 167                 }
 168         }
 169
 170         /* add best successor and recursively try to pick more */
 171         if (best_succ != NULL) {
 172                 addto_extblk(extblk, best_succ);
 173                 mark_irn_visited(best_succ);
 174                 pick_successor(best_succ, extblk, env);
 175         }
 176 }
 177
 178 /*
 179  * Compute the extended basic blocks for a graph
 180  */
 181 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs)
 182 {
 183         env_t     env;
 184         ir_extblk *extbb, *next;
 185         ir_node   *endblock;
 186
 187         if (irg->extbb_obst) {
 188                 obstack_free(irg->extbb_obst, NULL);
 189         }
 190         else {
 191                 irg->extbb_obst = XMALLOC(struct obstack);
 192         }
 193         obstack_init(irg->extbb_obst);
 194
 195         env.obst      = irg->extbb_obst;
 196         env.head      = NULL;
 197         env.execfreqs = execfreqs;
 198
 199         assure_irg_outs(irg);
 200
 201         /* we must mark nodes, so increase the visited flag */
 202         inc_irg_visited(irg);
 203         create_extblk(get_irg_start_block(irg), &env);
 204
 205         /* the end block needs a extbb assigned (even for endless loops) */
 206         endblock = get_irg_end_block(irg);
 207         create_extblk(endblock, &env);
 208
 209         /*
 210                 Ok, we have now the list of all extended blocks starting with env.head
 211                 every extended block "knowns" the number of blocks in visited and
 212                 the blocks are linked in link.
 213                 Now we can create arrays that hold the blocks, some kind of "out" edges
 214                 for the extended block
 215         */
 216         for (extbb = env.head; extbb; extbb = next) {
 217                 int i, len = (int)extbb->visited;
 218                 ir_node *block;
 219
 220                 next = (ir_extblk *)extbb->blks;
 221
 222                 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
 223
 224                 for (block = (ir_node*) extbb->link, i = 0; i < len; ++i) {
 225                         ir_node *nblock = (ir_node*) get_irn_link(block);
 226
 227                         /* ensure that the leader is the first one */
 228                         extbb->blks[len - 1 - i] = block;
 229                         set_irn_link(block, NULL);
 230                         block = nblock;
 231                 }
 232
 233 #if 0
 234                 for (i = 0; i < len; ++i) {
 235                         if (i > 0)
 236                                 printf(", ");
 237                         ir_printf("%+F", extbb->blks[i]);
 238                 }
 239                 printf("\n");
 240 #endif
 241
 242                 extbb->link    = NULL;
 243                 extbb->visited = 0;
 244         }
 245
 246         set_irg_state(irg, IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
 247 }