2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Statistics for Firm, register pressure estimation.
23 * @author Michael Beck
33 typedef struct block_entry_t block_entry_t;
34 typedef struct environment_t environment_t;
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. */
44 struct environment_t {
46 block_entry_t *entries; /**< List of all allocated block entries. */
47 void *visited; /**< a Bitset to mark visited nodes */
50 static environment_t *env;
53 * Get the block entry or allocate one if not yet assigned.
55 static block_entry_t *get_block_entry(ir_node *block) {
56 block_entry_t *entry = get_irn_link(block);
59 entry = obstack_alloc(&env->obst, sizeof(*entry));
61 entry->live_ins = NEW_ARR_F(ir_node *, 0);
62 entry->live_outs = NEW_ARR_F(ir_node *, 0);
64 entry->next = env->entries;
70 static void add_entry(ir_node ***arr, ir_node *irn) {
71 ir_node **list = *arr;
74 for (i = ARR_LEN(list) - 1; i >= 0; --i) {
80 ARR_APP1(ir_node *, *arr, irn);
83 static void add_live_in(ir_node *block, ir_node *irn) {
84 block_entry_t *entry = get_block_entry(block);
86 add_entry(&entry->live_ins, irn);
89 static void add_live_out(ir_node *block, ir_node *irn) {
90 block_entry_t *entry = get_block_entry(block);
92 add_entry(&entry->live_outs, irn);
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.
100 * @param def The node (value).
101 * @param block The block to mark the value live out of.
103 static void live_end_at_block(ir_node *def, ir_node *block) {
104 add_live_out(block, def);
106 if (is_irn_constlike(def)) {
107 /* do NOT follow Constants further, assume they are
108 part of instruction or can easily
113 if (! bitset_contains_irn(env->visited, block)) {
114 bitset_add_irn(env->visited, block);
117 * If this block is not the definition block, we have to go up
120 if (get_nodes_block(def) != block) {
123 add_live_in(block, def);
125 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i)
126 live_end_at_block(def, get_Block_cfgpred_block(block, i));
132 * Walker: finds live-outs and calculate live-ins from that.
134 static void find_live_outs(ir_node *irn, void *ctx)
136 ir_mode *mode = get_irn_mode(irn);
137 ir_node *block, *use_block;
142 /* only data nodes */
143 if (! mode_is_datab(mode))
146 block = get_nodes_block(irn);
148 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
149 ir_node *pred = get_irn_n(irn, i);
151 if (mode_is_datab(get_irn_mode(pred))) {
152 ir_node *def_block = get_nodes_block(pred);
155 use_block = get_Block_cfgpred_block(block, i);
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);
162 /* The Block has only one live in, the Phi itself */
163 add_live_in(block, irn);
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
175 add_live_in(use_block, pred);
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);
188 * Calculate the live-in and live out of blocks for datab nodes.
189 * Use it to estimate register pressure.
191 void stat_liveness(ir_graph *irg) {
197 obstack_init(&env->obst);
199 env->visited = bitset_obstack_alloc(&env->obst, get_irg_last_idx(irg));
201 irg_block_walk_graph(irg, NULL, firm_clear_link, NULL);
202 irg_walk_graph(irg, NULL, find_live_outs, NULL);
204 for (p = env->entries; p != NULL; p = p->next) {
205 DEL_ARR_F(p->live_ins);
206 DEL_ARR_F(p->live_outs);
208 obstack_free(&env->obst, NULL);