nsz Git - libfirm/blob - ir/stat/stat_liveness.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   Statistics for Firm, register pressure estimation.
  23  * @author  Michael Beck
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27 #include "irgwalk.h"
  28 #include "irbitset.h"
  29 #include "irtools.h"
  30 #include "array_t.h"
  31 #include "irnode_t.h"
  32
  33 typedef struct block_entry_t block_entry_t;
  34 typedef struct environment_t environment_t;
  35
  36 /** A Block entry. */
  37 struct block_entry_t {
  38         ir_node **live_ins;   /**< The array of live ins. */
  39         ir_node **live_outs;  /**< The array of live outs. */
  40         ir_node *block;       /**< The associated block. */
  41         block_entry_t *next;  /**< Links to the next block entry. */
  42 };
  43
  44 struct environment_t {
  45         struct obstack obst;
  46         block_entry_t *entries;  /**< List of all allocated block entries. */
  47         void          *visited;  /**< a Bitset to mark visited nodes */
  48 };
  49
  50 static environment_t *env;
  51
  52 /**
  53  * Get the block entry or allocate one if not yet assigned.
  54  */
  55 static block_entry_t *get_block_entry(ir_node *block)
  56 {
  57         block_entry_t *entry = get_irn_link(block);
  58
  59         if (entry == NULL) {
  60                 entry = OALLOC(&env->obst, block_entry_t);
  61
  62                 entry->live_ins  = NEW_ARR_F(ir_node *, 0);
  63                 entry->live_outs = NEW_ARR_F(ir_node *, 0);
  64
  65                 entry->next  = env->entries;
  66                 env->entries = entry;
  67         }
  68         return entry;
  69 }
  70
  71 static void add_entry(ir_node ***arr, ir_node *irn)
  72 {
  73         ir_node **list = *arr;
  74         int i;
  75
  76         for (i = ARR_LEN(list) - 1; i >= 0; --i) {
  77                 if (list[i] == irn) {
  78                         /* already there */
  79                         return;
  80                 }
  81         }
  82         ARR_APP1(ir_node *, *arr, irn);
  83 }
  84
  85 static void add_live_in(ir_node *block, ir_node *irn)
  86 {
  87         block_entry_t *entry = get_block_entry(block);
  88
  89         add_entry(&entry->live_ins, irn);
  90 }
  91
  92 static void add_live_out(ir_node *block, ir_node *irn)
  93 {
  94         block_entry_t *entry = get_block_entry(block);
  95
  96         add_entry(&entry->live_outs, irn);
  97 }
  98
  99 /**
 100  * Mark a node (value) live out at a certain block. Do this also
 101  * transitively, i.e. if the block is not the block of the value's
 102  * definition, all predecessors are also marked live.
 103  *
 104  * @param def      The node (value).
 105  * @param block    The block to mark the value live out of.
 106  */
 107 static void live_end_at_block(ir_node *def, ir_node *block)
 108 {
 109         add_live_out(block, def);
 110
 111         if (is_irn_constlike(def)) {
 112                 /* do NOT follow Constants further, assume they are
 113                    part of instruction or can easily
 114                    be rematerialized */
 115                 return;
 116         }
 117
 118         if (! bitset_contains_irn(env->visited, block)) {
 119                 bitset_add_irn(env->visited, block);
 120
 121                 /*
 122                  * If this block is not the definition block, we have to go up
 123                  * further.
 124                  */
 125                 if (get_nodes_block(def) != block) {
 126                         int i;
 127
 128                         add_live_in(block, def);
 129
 130                         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i)
 131                                 live_end_at_block(def, get_Block_cfgpred_block(block, i));
 132                 }
 133         }
 134 }
 135
 136 /**
 137  * Walker: finds live-outs and calculate live-ins from that.
 138  */
 139 static void find_live_outs(ir_node *irn, void *ctx)
 140 {
 141         ir_mode *mode = get_irn_mode(irn);
 142         ir_node *block, *use_block;
 143         int i;
 144
 145         (void)ctx;
 146
 147         /* only data nodes */
 148         if (! mode_is_datab(mode))
 149                 return;
 150
 151         block = get_nodes_block(irn);
 152
 153         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 154                 ir_node *pred = get_irn_n(irn, i);
 155
 156                 if (mode_is_datab(get_irn_mode(pred))) {
 157                         ir_node *def_block = get_nodes_block(pred);
 158
 159                         if (is_Phi(irn)) {
 160                                 use_block = get_Block_cfgpred_block(block, i);
 161
 162                                 /* even if pred is a Const, it MUST be
 163                                    in a register on block output */
 164                                 bitset_clear_all(env->visited);
 165                                 live_end_at_block(pred, use_block);
 166
 167                                 /* The Block has only one live in, the Phi itself */
 168                                 add_live_in(block, irn);
 169                         }
 170                         else if (def_block != use_block) {
 171                                 /* pred is a live in of our block */
 172                                 if (is_irn_constlike(pred)) {
 173                                         /* ignore Constants, assume they are
 174                                            part of instruction or can easily
 175                                            be rematerialized */
 176                                         continue;
 177                                 }
 178
 179                                 use_block = block;
 180                                 add_live_in(use_block, pred);
 181
 182                                 bitset_clear_all(env->visited);
 183                                 for (i = get_Block_n_cfgpreds(use_block); i >= 0; --i) {
 184                                         ir_node *pred_block = get_Block_cfgpred_block(use_block, i);
 185                                         live_end_at_block(irn, pred_block);
 186                                 }
 187                         }
 188                 }
 189         }
 190 }
 191
 192 /**
 193  * Calculate the live-in and live out of blocks for datab nodes.
 194  * Use it to estimate register pressure.
 195  */
 196 void stat_liveness(ir_graph *irg)
 197 {
 198         environment_t genv;
 199         block_entry_t *p;
 200
 201         env = &genv;
 202
 203         obstack_init(&env->obst);
 204         env->entries = NULL;
 205         env->visited = bitset_obstack_alloc(&env->obst, get_irg_last_idx(irg));
 206
 207         irg_block_walk_graph(irg, NULL, firm_clear_link, NULL);
 208         irg_walk_graph(irg, NULL, find_live_outs, NULL);
 209
 210         for (p = env->entries; p != NULL; p = p->next) {
 211                 DEL_ARR_F(p->live_ins);
 212                 DEL_ARR_F(p->live_outs);
 213         }
 214         obstack_free(&env->obst, NULL);
 215         env = NULL;
 216 }