3 * File name: ir/opt/gvn_pre.c
4 * Purpose: Global Value Numbering Partial Redundancy Elimination
5 * (VanDrunen Hosking 2004)
6 * Author: Michael Beck, Rubino Geiss
9 * Copyright: (c) 1998-2006 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
19 #include "irgraph_t.h"
30 typedef struct block_info {
31 pset *nodes; /**< the set of nodes per block */
32 pset *avail_out; /**< the Avail_out set for a block */
33 pset *antic_in; /**< the Antic_in set for a block */
34 struct block_info *next;
37 typedef struct avail_env {
38 struct obstack *obst; /**< the obstack to allocate on */
41 block_info *list; /**< links all block info entires for easier recovery */
42 int changes; /**< non-zero, if calculation of Antic_in has changed */
46 * returns non-zero if a node is movable.
48 static int is_nice_value(ir_node *n) {
49 ir_mode *mode = get_irn_mode(n);
51 if (mode == mode_M || mode == mode_X)
53 return (get_irn_pinned(n) != op_pin_state_pinned);
56 /** computes dst = dst \/ src */
57 static void pset_union(pset *dst, pset *src, unsigned (*hash)(void *))
61 for (entry = pset_first(src); entry; entry = pset_next(src)) {
62 pset_insert(dst, entry, ir_node_hash(entry));
67 * computes Avail_out(block):
69 * Avail_in(block) = Avail_out(dom(block))
70 * Avail_out(block) = Avail_in(block) \/ Nodes(block)
73 * This function must be called in the top-down dominance order:
74 * Then, it computes Leader(Nodes(block)) instead of Nodes(block) !
76 static void compute_avail_top_down(ir_node *block, void *ctx)
80 block_info *info = get_irn_link(block);
84 /* the root has no dominator */
85 if (block != env->start_block) {
86 dom_blk = get_Block_idom(block);
87 assert(is_Block(dom_blk));
89 dom_info = get_irn_link(dom_blk);
92 pset_union(info->avail_out, dom_info->avail_out, ir_node_hash);
93 pset_union(info->avail_out, info->nodes, ir_node_hash);
99 ir_printf("Avail_out(%+F) = {\n", block);
100 for (i = 0, n = pset_first(info->avail_out); n; ++i, n = pset_next(info->avail_out)) {
103 ir_printf(" %+F,", n);
111 * Implement phi_translate
113 static ir_node *phi_translate(ir_node *node, ir_node *block, int pos, avail_env *env)
117 int i, arity = get_irn_intra_arity(node);
121 if (get_nodes_block(node) == block)
122 return get_Phi_pred(node, pos);
126 /* check if the node has at least one Phi predecessor */
127 for (i = 0; i < arity; ++i) {
128 ir_node *phi = get_irn_intra_n(node, i);
129 if (is_Phi(phi) && get_nodes_block(phi) == block)
133 /* no Phi in the predecessors */
137 pred_block = get_Block_cfgpred_block(block, pos);
139 /* Create a copy of the node in the pos'th predecessor block.
140 Use our environmental obstack, as these nodes are always
142 old = current_ir_graph->obst;
143 current_ir_graph->obst = env->obst;
145 get_irn_dbg_info(node),
152 /* We need the attribute copy here, because the Hash value of a
153 node might depend on that. */
154 copy_node_attr(node, res);
155 current_ir_graph->obst = old;
157 for (i = -1; i < arity; ++i) {
158 ir_node *pred = get_irn_intra_n(node, i);
161 set_irn_n(res, i, pred);
163 set_irn_n(res, i, get_Phi_pred(pred, pos));
165 set_irn_link(res, node);
170 * Retranslate a Phi-translated node back
172 static ir_node *phi_retrans(ir_node *n, avail_env *env)
174 if (node_is_in_irgs_storage(current_ir_graph, n))
176 return get_irn_link(n);
180 * computes Antic_in(block):
183 static void compute_antic(ir_node *block, void *ctx)
185 avail_env *env = ctx;
186 block_info *succ_info;
187 block_info *info = get_irn_link(block);
191 size = pset_count(info->antic_in);
193 /* the root has no dominator */
194 if (block != env->end_block) {
195 int n_succ = get_Block_n_cfg_outs(block);
200 pset *nodes = new_pset(identities_cmp, 8);
202 pset_union(nodes, info->nodes, ir_node_hash);
204 /* find blocks position in succ's block predecessors */
205 succ = get_Block_cfg_out(block, 0);
206 for (i = get_Block_n_cfgpreds(succ) - 1; i >= 0; --i) {
207 if (get_Block_cfgpred_block(succ, i) == block) {
214 succ_info = get_irn_link(succ);
215 for (node = pset_first(succ_info->antic_in);
217 node = pset_next(succ_info->antic_in)) {
218 ir_node *trans = phi_translate(node, succ, pos, env);
220 identify_remember(nodes, trans);
222 /* add all predecessors of node */
223 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
224 ir_node *pred = get_irn_n(node, i);
225 ir_node *trans = phi_translate(pred, succ, pos, env);
227 if (is_nice_value(trans))
228 identify_remember(nodes, trans);
231 /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
232 pset_union(info->antic_in, nodes, ir_node_hash);
237 block_info *succ0_info;
242 /* Select a successor to compute the disjoint of all Nodes
243 sets, it might be useful to select the block with the
244 smallest number of nodes. For simplicity we choose the
246 succ0 = get_Block_cfg_out(block, 0);
247 succ0_info = get_irn_link(succ0);
248 for (n = pset_first(succ0_info->antic_in);
250 n = pset_next(succ0_info->antic_in)) {
251 /* we need the disjoint */
252 for (i = 1; i < n_succ; ++i) {
253 ir_node *succ = get_Block_cfg_out(block, i);
254 block_info *succ_info = get_irn_link(succ);
255 if (pset_find(succ_info->antic_in, n, ir_node_hash(n)) == NULL)
259 /* we found a node that is common in all Antic_in(succ(b)),
260 put it in Antic_in(b) */
261 identify_remember(info->antic_in, n);
264 /* this step calculates Antic_in(b) = Antic_out(b) \/ Nodes(b) */
265 pset_union(info->antic_in, info->nodes, ir_node_hash);
269 if (size != pset_count(info->antic_in))
270 /* the Antic_in set has changed */
277 ir_printf("Antic_in(%+F) = {\n", block);
278 for (i = 0, n = pset_first(info->antic_in); n; ++i, n = pset_next(info->antic_in)) {
279 ir_node *orig = phi_retrans(n, env);
282 ir_printf(" %+F%", n);
284 ir_printf("{%+F}", orig);
293 * allocate a block info
295 static void alloc_blk_info(ir_node *block, void *ctx)
298 avail_env *env = ctx;
299 block_info *info = obstack_alloc(env->obst, sizeof(block_info));
301 set_irn_link(block, info);
302 info->nodes = new_pset(identities_cmp, 8);
303 info->antic_in = new_pset(identities_cmp, 8);
304 info->avail_out = new_pset(identities_cmp, 8);
305 info->next = env->list;
306 env->list = info->next;
308 /* fill the nodes set, we will need it later */
309 for (i = get_irn_n_outs(block) - 1; i >= 0; --i) {
310 ir_node *n = get_irn_out(block, i);
312 /* we cannot optimize pinned nodes, so do not remember them */
313 if (is_nice_value(n))
314 identify_remember(info->nodes, n);
315 else if (is_Phi(n) && get_irn_mode(n) != mode_M) {
317 * Phis are "temporaries" and must be handled special:
318 * They are avail, but are not in Antic_in
320 identify_remember(info->avail_out, n);
328 static void insert_nodes(ir_node *block, void *ctx)
330 avail_env *env = ctx;
331 ir_node *v, *idom, *first_s;
332 block_info *info, *idom_info;
333 int pos, arity = get_irn_intra_arity(block);
334 int all_same, by_some;
339 info = get_irn_link(block);
341 idom = get_Block_idom(block);
342 idom_info = get_irn_link(idom);
343 for (v = pset_first(info->antic_in);
345 v = pset_next(info->antic_in)) {
346 /* If the value was already computed in the dominator, then
347 it is totally redundant. Hence we have nothing to insert. */
348 if (pset_find(idom_info->avail_out, v, ir_node_hash(v))) {
349 // ir_printf("Found %+F from block %+F avail in dom %+F\n", v, block, idom);
357 for (pos = 0; pos < arity; ++pos) {
358 block_info *pred_info;
359 ir_node *pred = get_Block_cfgpred_block(block, pos);
360 ir_node *trans, *found;
365 trans = phi_translate(v, block, pos, env);
367 pred_info = get_irn_link(pred);
368 found = pset_find(pred_info->avail_out, trans, ir_node_hash(trans));
377 else if (first_s != found)
380 ir_printf("Found %+F from block %+F as %+F in pred %+F\n", v, block, found, pred);
384 if (! all_same && by_some) {
385 ir_printf("Partial redundant %+F from block %+F found\n", v, block);
390 void do_gvn_pre(ir_graph *irg)
394 optimization_state_t state;
401 a_env.start_block = get_irg_start_block(irg);
402 a_env.end_block = get_irg_end_block(irg);
404 remove_critical_cf_edges(irg);
406 /* we need dominator AND post dominator information */
407 if (get_irg_dom_state(irg) != dom_consistent)
409 if (get_irg_postdom_state(irg) != dom_consistent)
410 compute_postdoms(irg);
411 if (get_irg_outs_state(irg) != outs_consistent)
412 compute_irg_outs(irg);
414 save_optimization_state(&state);
415 set_opt_global_cse(1);
417 /* allocate block info for all blocks */
418 irg_block_walk_graph(irg, NULL, alloc_blk_info, &a_env);
420 /* compute the available value sets for all blocks */
421 dom_tree_walk_irg(irg, compute_avail_top_down, NULL, &a_env);
423 /* compute the anticipated value sets for all blocks */
426 printf("Antic_in Iteration %d starts ...\n", ++iter);
429 irg_block_walk_graph(irg, compute_antic, NULL, &a_env);
430 // postdom_tree_walk_irg(irg, compute_antic, NULL, &a_env);
432 printf("------------------------\n");
434 } while (a_env.changes != 0);
439 printf("Insert Iteration %d starts ...\n", ++iter);
442 irg_block_walk_graph(irg, insert_nodes, NULL, &a_env);
443 // dom_tree_walk_irg(irg, insert_nodes, NULL, &a_env);
445 printf("------------------------\n");
447 } while (a_env.changes != 0);
449 restore_optimization_state(&state);
451 for (p = a_env.list; p != NULL; p = p->next) {
453 del_pset(p->antic_in);
455 del_pset(p->avail_out);
457 obstack_free(&obst, NULL);