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