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