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                 const ir_edge_t *edge;
 132
 133                 foreach_block_succ(block, edge) {
 134                         ir_node *succ = get_edge_src_irn(edge);
 135                         create_extblk(succ, env);
 136                 }
 137
 138                 return;
 139         }
 140
 141         foreach_block_succ(block, edge) {
 142                 ir_node *succ = get_edge_src_irn(edge);
 143                 double execfreq;
 144
 145                 if (irn_visited(succ))
 146                         continue;
 147
 148                 if (get_Block_n_cfgpreds(succ) > 1) {
 149                         create_extblk(succ, env);
 150                         continue;
 151                 }
 152
 153                 execfreq = get_block_execfreq(env->execfreqs, succ);
 154
 155                 /*
 156                         Remember best successor and make non best successor with only 1
 157                         pred block to new extbb leaders.
 158                 */
 159                 if (execfreq > best_execfreq) {
 160                         if (best_succ != NULL) {
 161                                 create_extblk(best_succ, env);
 162                         }
 163
 164                         best_execfreq = execfreq;
 165                         best_succ = succ;
 166                 }
 167                 else {
 168                         create_extblk(succ, env);
 169                 }
 170         }
 171
 172         /* add best successor and recursively try to pick more */
 173         if (best_succ != NULL) {
 174                 addto_extblk(extblk, best_succ);
 175                 mark_irn_visited(best_succ);
 176                 pick_successor(best_succ, extblk, env);
 177         }
 178 }
 179
 180 /*
 181  * Compute the extended basic blocks for a graph
 182  */
 183 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs)
 184 {
 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 }