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) - 1; i >= 0; --i) {
82 ARR_APP1(ir_node *, *arr, irn);
85 static void add_live_in(ir_node *block, ir_node *irn)
87 block_entry_t *entry = get_block_entry(block);
89 add_entry(&entry->live_ins, irn);
92 static void add_live_out(ir_node *block, ir_node *irn)
94 block_entry_t *entry = get_block_entry(block);
96 add_entry(&entry->live_outs, irn);
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.
104 * @param def The node (value).
105 * @param block The block to mark the value live out of.
107 static void live_end_at_block(ir_node *def, ir_node *block)
109 add_live_out(block, def);
111 if (is_irn_constlike(def)) {
112 /* do NOT follow Constants further, assume they are
113 part of instruction or can easily
118 if (! bitset_contains_irn(env->visited, block)) {
119 bitset_add_irn(env->visited, block);
122 * If this block is not the definition block, we have to go up
125 if (get_nodes_block(def) != block) {
128 add_live_in(block, def);
130 for (i = get_Block_n_cfgpreds(block) - 1; i >= 0; --i)
131 live_end_at_block(def, get_Block_cfgpred_block(block, i));
137 * Walker: finds live-outs and calculate live-ins from that.
139 static void find_live_outs(ir_node *irn, void *ctx)
141 ir_mode *mode = get_irn_mode(irn);
142 ir_node *block, *use_block;
147 /* only data nodes */
148 if (! mode_is_datab(mode))
151 block = get_nodes_block(irn);
153 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
154 ir_node *pred = get_irn_n(irn, i);
156 if (mode_is_datab(get_irn_mode(pred))) {
157 ir_node *def_block = get_nodes_block(pred);
160 use_block = get_Block_cfgpred_block(block, i);
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);
167 /* The Block has only one live in, the Phi itself */
168 add_live_in(block, irn);
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
180 add_live_in(use_block, pred);
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);
193 * Calculate the live-in and live out of blocks for datab nodes.
194 * Use it to estimate register pressure.
196 void stat_liveness(ir_graph *irg)
203 obstack_init(&env->obst);
205 env->visited = bitset_obstack_alloc(&env->obst, get_irg_last_idx(irg));
207 irg_block_walk_graph(irg, NULL, firm_clear_link, NULL);
208 irg_walk_graph(irg, NULL, find_live_outs, NULL);
210 for (p = env->entries; p != NULL; p = p->next) {
211 DEL_ARR_F(p->live_ins);
212 DEL_ARR_F(p->live_outs);
214 obstack_free(&env->obst, NULL);