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

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