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         bitset_t      *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 = (block_entry_t*)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         size_t i;
  75
  76         for (i = ARR_LEN(list); i > 0;) {
  77                 --i;
  78                 if (list[i] == irn) {
  79                         /* already there */
  80                         return;
  81                 }
  82         }
  83         ARR_APP1(ir_node *, *arr, irn);
  84 }
  85
  86 static void add_live_in(ir_node *block, ir_node *irn)
  87 {
  88         block_entry_t *entry = get_block_entry(block);
  89
  90         add_entry(&entry->live_ins, irn);
  91 }
  92
  93 static void add_live_out(ir_node *block, ir_node *irn)
  94 {
  95         block_entry_t *entry = get_block_entry(block);
  96
  97         add_entry(&entry->live_outs, irn);
  98 }
  99
 100 /**
 101  * Mark a node (value) live out at a certain block. Do this also
 102  * transitively, i.e. if the block is not the block of the value's
 103  * definition, all predecessors are also marked live.
 104  *
 105  * @param def      The node (value).
 106  * @param block    The block to mark the value live out of.
 107  */
 108 static void live_end_at_block(ir_node *def, ir_node *block)
 109 {
 110         add_live_out(block, def);
 111
 112         if (is_irn_constlike(def)) {
 113                 /* do NOT follow Constants further, assume they are
 114                    part of instruction or can easily
 115                    be rematerialized */
 116                 return;
 117         }
 118
 119         if (! bitset_contains_irn(env->visited, block)) {
 120                 bitset_add_irn(env->visited, block);
 121
 122                 /*
 123                  * If this block is not the definition block, we have to go up
 124                  * further.
 125                  */
 126                 if (get_nodes_block(def) != block) {
 127                         int i;
 128
 129                         add_live_in(block, def);
 130
 131                         for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i)
 132                                 live_end_at_block(def, get_Block_cfgpred_block(block, i));
 133                 }
 134         }
 135 }
 136
 137 /**
 138  * Walker: finds live-outs and calculate live-ins from that.
 139  */
 140 static void find_live_outs(ir_node *irn, void *ctx)
 141 {
 142         ir_mode *mode = get_irn_mode(irn);
 143         ir_node *block, *use_block;
 144         int i;
 145
 146         (void)ctx;
 147
 148         /* only data nodes */
 149         if (! mode_is_datab(mode))
 150                 return;
 151
 152         block = get_nodes_block(irn);
 153
 154         for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 155                 ir_node *pred = get_irn_n(irn, i);
 156
 157                 if (mode_is_datab(get_irn_mode(pred))) {
 158                         ir_node *def_block = get_nodes_block(pred);
 159
 160                         if (is_Phi(irn)) {
 161                                 use_block = get_Block_cfgpred_block(block, i);
 162
 163                                 /* even if pred is a Const, it MUST be
 164                                    in a register on block output */
 165                                 bitset_clear_all(env->visited);
 166                                 live_end_at_block(pred, use_block);
 167
 168                                 /* The Block has only one live in, the Phi itself */
 169                                 add_live_in(block, irn);
 170                         }
 171                         else if (def_block != use_block) {
 172                                 /* pred is a live in of our block */
 173                                 if (is_irn_constlike(pred)) {
 174                                         /* ignore Constants, assume they are
 175                                            part of instruction or can easily
 176                                            be rematerialized */
 177                                         continue;
 178                                 }
 179
 180                                 use_block = block;
 181                                 add_live_in(use_block, pred);
 182
 183                                 bitset_clear_all(env->visited);
 184                                 for (i = get_Block_n_cfgpreds(use_block); i >= 0; --i) {
 185                                         ir_node *pred_block = get_Block_cfgpred_block(use_block, i);
 186                                         live_end_at_block(irn, pred_block);
 187                                 }
 188                         }
 189                 }
 190         }
 191 }
 192
 193 /**
 194  * Calculate the live-in and live out of blocks for datab nodes.
 195  * Use it to estimate register pressure.
 196  */
 197 void stat_liveness(ir_graph *irg)
 198 {
 199         environment_t genv;
 200         block_entry_t *p;
 201
 202         env = &genv;
 203
 204         obstack_init(&env->obst);
 205         env->entries = NULL;
 206         env->visited = bitset_obstack_alloc(&env->obst, get_irg_last_idx(irg));
 207
 208         irg_block_walk_graph(irg, NULL, firm_clear_link, NULL);
 209         irg_walk_graph(irg, NULL, find_live_outs, NULL);
 210
 211         for (p = env->entries; p != NULL; p = p->next) {
 212                 DEL_ARR_F(p->live_ins);
 213                 DEL_ARR_F(p->live_outs);
 214         }
 215         obstack_free(&env->obst, NULL);
 216         env = NULL;
 217 }