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