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