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 bitset_t *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)
57 block_entry_t *entry = (block_entry_t*)get_irn_link(block);
60 entry = OALLOC(&env->obst, block_entry_t);
62 entry->live_ins = NEW_ARR_F(ir_node *, 0);
63 entry->live_outs = NEW_ARR_F(ir_node *, 0);
65 entry->next = env->entries;
71 static void add_entry(ir_node ***arr, ir_node *irn)
73 ir_node **list = *arr;
76 for (i = ARR_LEN(list); i > 0;) {
83 ARR_APP1(ir_node *, *arr, irn);
86 static void add_live_in(ir_node *block, ir_node *irn)
88 block_entry_t *entry = get_block_entry(block);
90 add_entry(&entry->live_ins, irn);
93 static void add_live_out(ir_node *block, ir_node *irn)
95 block_entry_t *entry = get_block_entry(block);
97 add_entry(&entry->live_outs, irn);
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.
105 * @param def The node (value).
106 * @param block The block to mark the value live out of.
108 static void live_end_at_block(ir_node *def, ir_node *block)
110 add_live_out(block, def);
112 if (is_irn_constlike(def)) {
113 /* do NOT follow Constants further, assume they are
114 part of instruction or can easily
119 if (! bitset_contains_irn(env->visited, block)) {
120 bitset_add_irn(env->visited, block);
123 * If this block is not the definition block, we have to go up
126 if (get_nodes_block(def) != block) {
129 add_live_in(block, def);
131 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i)
132 live_end_at_block(def, get_Block_cfgpred_block(block, i));
138 * Walker: finds live-outs and calculate live-ins from that.
140 static void find_live_outs(ir_node *irn, void *ctx)
142 ir_mode *mode = get_irn_mode(irn);
143 ir_node *block, *use_block;
148 /* only data nodes */
149 if (! mode_is_datab(mode))
152 block = get_nodes_block(irn);
154 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
155 ir_node *pred = get_irn_n(irn, i);
157 if (mode_is_datab(get_irn_mode(pred))) {
158 ir_node *def_block = get_nodes_block(pred);
161 use_block = get_Block_cfgpred_block(block, i);
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);
168 /* The Block has only one live in, the Phi itself */
169 add_live_in(block, irn);
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
181 add_live_in(use_block, pred);
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);
194 * Calculate the live-in and live out of blocks for datab nodes.
195 * Use it to estimate register pressure.
197 void stat_liveness(ir_graph *irg)
204 obstack_init(&env->obst);
206 env->visited = bitset_obstack_alloc(&env->obst, get_irg_last_idx(irg));
208 irg_block_walk_graph(irg, NULL, firm_clear_link, NULL);
209 irg_walk_graph(irg, NULL, find_live_outs, NULL);
211 for (p = env->entries; p != NULL; p = p->next) {
212 DEL_ARR_F(p->live_ins);
213 DEL_ARR_F(p->live_outs);
215 obstack_free(&env->obst, NULL);