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