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