2 * Interblock liveness analysis.
3 * @author Sebastian Hack
13 #include "irprintf_t.h"
18 #define DEFAULT_LIVE_SET_SIZE 8
20 FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *)
21 FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *)
22 FIRM_IMPL2(is_live_end, int, const ir_node *, const ir_node *)
24 /** The offset of the liveness information in a firm node. */
25 size_t live_irn_data_offset = 0;
27 void be_liveness_init(void)
29 live_irn_data_offset = register_additional_node_data(sizeof(live_info_t));
32 static INLINE void mark_live_in(ir_node *block, const ir_node *irn)
34 block_live_info_t *info = get_block_live_info(block);
35 pset_insert_ptr(info->in, irn);
38 static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
40 block_live_info_t *info = get_block_live_info(block);
41 pset_insert_ptr(info->out, irn);
44 static INLINE void mark_live_end(ir_node *block, const ir_node *irn)
46 block_live_info_t *info = get_block_live_info(block);
47 pset_insert_ptr(info->end, irn);
51 * Mark a node (value) live out at a certain block. Do this also
52 * transitively, i.e. if the block is not the block of the value's
53 * definition, all predecessors are also marked live.
54 * @param def The node (value).
55 * @param block The block to mark the value live out of.
56 * @param visited A set were all visited blocks are recorded.
57 * @param is_true_out Is the node real out there or only live at the end
60 static void live_end_at_block(ir_node *def, ir_node *block,
61 pset *visited, int is_true_out)
63 if(pset_find_ptr(visited, block))
66 pset_insert_ptr(visited, block);
67 mark_live_end(block, def);
70 mark_live_out(block, def);
73 * If this block is not the definition block, we have to go up
76 if(get_nodes_block(def) != block) {
79 mark_live_in(block, def);
81 for(i = 0, n = get_irn_arity(block); i < n; ++i)
82 live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1);
87 * Liveness analysis for a value.
88 * This functions is meant to be called by a firm walker, to compute the
89 * set of all blocks a value is live in.
90 * @param irn The node (value).
93 static void liveness_for_node(ir_node *irn, void *env)
99 /* Don't compute liveness information fornon-data nodes. */
100 if(!is_data_node(irn))
103 visited = pset_new_ptr(512);
104 def_block = get_nodes_block(irn);
106 /* Go over all uses of the value */
107 for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) {
108 ir_node *use = get_irn_out(irn, i);
112 * If the usage is no data node, skip this use, since it does not
113 * affect the liveness of the node.
115 if(!is_data_node(use))
118 /* Get the block where the usage is in. */
119 use_block = get_nodes_block(use);
122 * If the block of the definition equals the use block, we can skip
123 * the following computations, since this use is local to a block.
125 if(def_block == use_block)
129 * If the use is a phi function, determine the corresponding block
130 * through which the value reaches the phi function and mark the
131 * value as live out of that block.
136 /* Mark the node as a phi operand, since a use by a phi was found. */
137 get_node_live_info(irn)->is_phi_op = 1;
139 for(i = 0, n = get_irn_arity(use); i < n; ++i) {
140 if(get_irn_n(use, i) == irn) {
141 ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
142 live_end_at_block(irn, pred_block, visited, 0);
148 * Else, the value is live in at this block. Mark it and call live
149 * out on the predecessors.
154 mark_live_in(use_block, irn);
156 for(i = 0, n = get_irn_arity(use_block); i < n; ++i) {
157 ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
158 live_end_at_block(irn, pred_block, visited, 1);
166 static void create_sets(ir_node *block, void *env)
168 block_live_info_t *info = get_block_live_info(block);
169 info->in = pset_new_ptr(DEFAULT_LIVE_SET_SIZE);
170 info->out = pset_new_ptr(DEFAULT_LIVE_SET_SIZE);
171 info->end = pset_new_ptr(DEFAULT_LIVE_SET_SIZE);
175 static void liveness_dump(ir_node *block, void *env)
178 block_live_info_t *info = get_block_live_info(block);
180 assert(is_Block(block) && "Need a block here");
181 ir_fprintf(f, "liveness at block %n\n", block);
182 ir_fprintf(f, "\tlive in: %*n\n", pset_iterator, info->in);
183 ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out);
184 ir_fprintf(f, "\tlive end: %*n\n", pset_iterator, info->end);
187 void be_liveness_dump(FILE *f, ir_graph *irg)
189 irg_block_walk_graph(irg, liveness_dump, NULL, f);
192 void be_liveness(ir_graph *irg)
194 irg_block_walk_graph(irg, create_sets, NULL, NULL);
195 irg_walk_graph(irg, liveness_for_node, NULL, NULL);