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) {
135 ir_mode *mode = get_irn_mode(irn);
136 ir_node *block, *use_block;
139 /* only data nodes */
140 if (! mode_is_datab(mode))
143 block = get_nodes_block(irn);
145 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
146 ir_node *pred = get_irn_n(irn, i);
148 if (mode_is_datab(get_irn_mode(pred))) {
149 ir_node *def_block = get_nodes_block(pred);
152 use_block = get_Block_cfgpred_block(block, i);
154 /* even if pred is a Const, it MUST be
155 in a register on block output */
156 bitset_clear_all(env->visited);
157 live_end_at_block(pred, use_block);
159 /* The Block has only one live in, the Phi itself */
160 add_live_in(block, irn);
162 else if (def_block != use_block) {
163 /* pred is a live in of our block */
164 if (is_irn_constlike(pred)) {
165 /* ignore Constants, assume they are
166 part of instruction or can easily
172 add_live_in(use_block, pred);
174 bitset_clear_all(env->visited);
175 for (i = get_Block_n_cfgpreds(use_block); i >= 0; --i) {
176 ir_node *pred_block = get_Block_cfgpred_block(use_block, i);
177 live_end_at_block(irn, pred_block);
185 * Calculate the live-in and live out of blocks for datab nodes.
186 * Use it to estimate register pressure.
188 void stat_liveness(ir_graph *irg) {
194 obstack_init(&env->obst);
196 env->visited = bitset_obstack_alloc(&env->obst, get_irg_last_idx(irg));
198 irg_block_walk_graph(irg, NULL, firm_clear_link, NULL);
199 irg_walk_graph(irg, NULL, find_live_outs, NULL);
201 for (p = env->entries; p != NULL; p = p->next) {
202 DEL_ARR_F(p->live_ins);
203 DEL_ARR_F(p->live_outs);
205 obstack_free(&env->obst, NULL);