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

   1 /*
   2  * Copyrigth (C) 1995-2007 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(block))
 113                 return;
 114
 115         extblk = allocate_extblk(block, env);
 116         mark_irn_visited(block);
 117
 118         pick_successor(block, extblk, env);
 119 }
 120
 121 static void pick_successor(ir_node *block, ir_extblk *extblk, env_t *env)
 122 {
 123         const ir_edge_t *edge;
 124         ir_node         *best_succ    = NULL;
 125         double          best_execfreq = -1;
 126
 127         /*
 128                 More than two successors means we have a jump table.
 129                 we cannot include a jump target into the current extended
 130                 basic block, so create a new one here.
 131         */
 132         if (get_block_n_succs(block) > 2) {
 133                 const ir_edge_t *edge;
 134
 135                 foreach_block_succ(block, edge) {
 136                         ir_node *succ = get_edge_src_irn(edge);
 137                         create_extblk(succ, env);
 138                 }
 139
 140                 return;
 141         }
 142
 143         foreach_block_succ(block, edge) {
 144                 ir_node *succ = get_edge_src_irn(edge);
 145                 double execfreq;
 146
 147                 if(irn_visited(succ))
 148                         continue;
 149
 150                 if(get_Block_n_cfgpreds(succ) > 1) {
 151                         create_extblk(succ, env);
 152                         continue;
 153                 }
 154
 155                 execfreq = get_block_execfreq(env->execfreqs, succ);
 156
 157                 /*
 158                         Remember best successor and make non best successor with only 1
 159                         pred block to new extbb leaders.
 160                 */
 161                 if (execfreq > best_execfreq) {
 162                         if (best_succ != NULL) {
 163                                 create_extblk(best_succ, env);
 164                         }
 165
 166                         best_execfreq = execfreq;
 167                         best_succ = succ;
 168                 }
 169                 else {
 170                         create_extblk(succ, env);
 171                 }
 172         }
 173
 174         /* add best successor and recursively try to pick more */
 175         if(best_succ != NULL) {
 176                 addto_extblk(extblk, best_succ);
 177                 mark_irn_visited(best_succ);
 178                 pick_successor(best_succ, extblk, env);
 179         }
 180 }
 181
 182 /*
 183  * Compute the extended basic blocks for a graph
 184  */
 185 void compute_extbb_execfreqs(ir_graph *irg, ir_exec_freq *execfreqs) {
 186         env_t     env;
 187         ir_extblk *extbb, *next;
 188         ir_node   *endblock;
 189
 190         if (irg->extbb_obst) {
 191                 obstack_free(irg->extbb_obst, NULL);
 192         }
 193         else {
 194                 irg->extbb_obst = xmalloc(sizeof(*irg->extbb_obst));
 195         }
 196         obstack_init(irg->extbb_obst);
 197
 198         env.obst      = irg->extbb_obst;
 199         env.head      = NULL;
 200         env.execfreqs = execfreqs;
 201
 202         assure_irg_outs(irg);
 203
 204         /* we must mark nodes, so increase the visited flag */
 205         inc_irg_visited(irg);
 206         create_extblk(get_irg_start_block(irg), &env);
 207
 208         /* the end block needs a extbb assigned (even for endless loops) */
 209         endblock = get_irg_end_block(irg);
 210         if (! irn_visited(endblock)) {
 211                 create_extblk(endblock, &env);
 212         }
 213
 214         /*
 215                 Ok, we have now the list of all extended blocks starting with env.head
 216                 every extended block "knowns" the number of blocks in visited and
 217                 the blocks are linked in link.
 218                 Now we can create arrays that hold the blocks, some kind of "out" edges
 219                 for the extended block
 220         */
 221         for (extbb = env.head; extbb; extbb = next) {
 222                 int i, len = (int)extbb->visited;
 223                 ir_node *block;
 224
 225                 next = (ir_extblk *)extbb->blks;
 226
 227                 extbb->blks = NEW_ARR_D(ir_node *, env.obst, len);
 228
 229                 for (block = extbb->link, i = 0; i < len; ++i) {
 230                         ir_node *nblock = get_irn_link(block);
 231
 232                         /* ensure that the leader is the first one */
 233                         extbb->blks[len - 1 - i] = block;
 234                         set_irn_link(block, NULL);
 235                         block = nblock;
 236                 }
 237
 238 #if 0
 239                 for(i = 0; i < len; ++i) {
 240                         if(i > 0)
 241                                 printf(", ");
 242                         ir_printf("%+F", extbb->blks[i]);
 243                 }
 244                 printf("\n");
 245 #endif
 246
 247                 extbb->link    = NULL;
 248                 extbb->visited = 0;
 249         }
 250
 251         irg->extblk_state = extblk_valid;
 252 }