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 Dead node elimination
23 * @author Michael Beck, Goetz Lindenmaier
24 * @version $Id: opt_inline.c 27265 2010-03-07 15:13:00Z matze $
26 * Strictly speaking dead node elimination is unnecessary in firm - everthying
27 * which is not used can't be found by any walker.
28 * The only drawback is that the nodes still take up memory. This phase fixes
29 * this by copying all (reachable) nodes to a new obstack and throwing away
34 #include "iroptimize.h"
36 #include "irgraph_t.h"
37 #include "irphase_t.h"
38 #include "iredges_t.h"
49 /** a pointer to the new phases */
50 static ir_phase *new_phases[PHASE_LAST];
53 * Reroute the inputs of a node from nodes in the old graph to copied nodes in
56 static void rewire_inputs(ir_node *node, void *env)
59 irn_rewire_inputs(node);
62 static void copy_node_dce(ir_node *node, void *env)
65 ir_node *new_node = exact_copy(node);
66 ir_graph *irg = get_irn_irg(new_node);
69 /* preserve the node numbers for easier debugging */
70 new_node->node_nr = node->node_nr;
72 /* copy phase information for this node */
73 for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
74 ir_phase *phase = get_irg_phase(irg, i);
77 if (!phase_get_irn_data(phase, node))
79 phase_set_irn_data(new_phases[i], new_node,
80 phase_get_irn_data(phase, node));
83 set_irn_link(node, new_node);
84 hook_dead_node_elim_subst(irg, node, new_node);
88 * Copies the graph reachable from current_ir_graph->end to the obstack
89 * in current_ir_graph and fixes the environment.
90 * Then fixes the fields in current_ir_graph containing nodes of the
93 * @param copy_node_nr If non-zero, the node number will be copied
95 static void copy_graph_env(ir_graph *irg)
100 /* init the new_phases array */
101 for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
102 ir_phase *old_ph = get_irg_phase(irg, i);
103 if (old_ph == NULL) {
104 new_phases[i] = NULL;
106 new_phases[i] = xmalloc(sizeof(ir_phase));
107 phase_init(new_phases[i], "", irg, old_ph->growth_factor,
108 old_ph->data_init, old_ph->priv);
113 irg_walk_anchors(irg, copy_node_dce, rewire_inputs, NULL);
116 new_anchor = get_irn_link(irg->anchor);
117 assert(new_anchor != NULL);
118 irg->anchor = new_anchor;
120 /* copy the new phases into the irg */
121 for (i = PHASE_NOT_IRG_MANAGED+1; i < PHASE_LAST; i++) {
122 ir_phase *old_ph = get_irg_phase(irg, i);
126 free_irg_phase(irg, i);
127 irg->phases[i] = new_phases[i];
132 * Copies all reachable nodes to a new obstack. Removes bad inputs
133 * from block nodes and the corresponding inputs from Phi nodes.
134 * Merges single exit blocks with single entry blocks and removes
136 * Adds all new nodes to a new hash table for CSE. Does not
137 * perform CSE, so the hash table might contain common subexpressions.
139 void dead_node_elimination(ir_graph *irg)
142 #ifdef INTERPROCEDURAL_VIEW
143 int rem_ipview = get_interprocedural_view();
145 struct obstack *graveyard_obst = NULL;
146 struct obstack *rebirth_obst = NULL;
148 edges_deactivate(irg);
150 /* inform statistics that we started a dead-node elimination run */
151 hook_dead_node_elim(irg, 1);
153 /* Remember external state of current_ir_graph. */
154 rem = current_ir_graph;
155 current_ir_graph = irg;
156 #ifdef INTERPROCEDURAL_VIEW
157 set_interprocedural_view(0);
160 assert(get_irg_phase_state(irg) != phase_building);
162 /* Handle graph state */
163 free_callee_info(irg);
166 free_loop_information(irg);
167 set_irg_doms_inconsistent(irg);
169 /* A quiet place, where the old obstack can rest in peace,
170 until it will be cremated. */
171 graveyard_obst = irg->obst;
173 /* A new obstack, where the reachable nodes will be copied to. */
174 rebirth_obst = XMALLOC(struct obstack);
175 irg->obst = rebirth_obst;
176 obstack_init(irg->obst);
177 irg->last_node_idx = 0;
179 /* We also need a new value table for CSE */
180 del_identities(irg->value_table);
181 irg->value_table = new_identities();
183 /* Copy the graph from the old to the new obstack */
186 /* Free memory from old unoptimized obstack */
187 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
188 xfree(graveyard_obst); /* ... then free it. */
190 /* inform statistics that the run is over */
191 hook_dead_node_elim(irg, 0);
193 current_ir_graph = rem;
194 #ifdef INTERPROCEDURAL_VIEW
195 set_interprocedural_view(rem_ipview);
199 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
201 return def_graph_pass(name ? name : "dce", dead_node_elimination);
208 __)|_| | \_/ | \_/(/_ |_/\__|__
210 The following stuff implements a facility that automatically patches
211 registered ir_node pointers to the new node when a dead node elimination occurs.
214 Warning: This is considered a hack - try hard to avoid this!
217 struct _survive_dce_t {
221 hook_entry_t dead_node_elim;
222 hook_entry_t dead_node_elim_subst;
225 typedef struct _survive_dce_list_t {
226 struct _survive_dce_list_t *next;
228 } survive_dce_list_t;
230 static void dead_node_hook(void *context, ir_graph *irg, int start)
232 survive_dce_t *sd = context;
235 /* Create a new map before the dead node elimination is performed. */
237 sd->new_places = pmap_create_ex(pmap_count(sd->places));
239 /* Patch back all nodes if dead node elimination is over and something is to be done. */
240 pmap_destroy(sd->places);
241 sd->places = sd->new_places;
242 sd->new_places = NULL;
247 * Hook called when dead node elimination replaces old by nw.
249 static void dead_node_subst_hook(void *context, ir_graph *irg, ir_node *old, ir_node *nw)
251 survive_dce_t *sd = context;
252 survive_dce_list_t *list = pmap_get(sd->places, old);
255 /* If the node is to be patched back, write the new address to all registered locations. */
257 survive_dce_list_t *p;
259 for (p = list; p; p = p->next)
262 pmap_insert(sd->new_places, nw, list);
267 * Make a new Survive DCE environment.
269 survive_dce_t *new_survive_dce(void)
271 survive_dce_t *res = XMALLOC(survive_dce_t);
272 obstack_init(&res->obst);
273 res->places = pmap_create();
274 res->new_places = NULL;
276 res->dead_node_elim.hook._hook_dead_node_elim = dead_node_hook;
277 res->dead_node_elim.context = res;
278 res->dead_node_elim.next = NULL;
280 res->dead_node_elim_subst.hook._hook_dead_node_elim_subst = dead_node_subst_hook;
281 res->dead_node_elim_subst.context = res;
282 res->dead_node_elim_subst.next = NULL;
284 register_hook(hook_dead_node_elim, &res->dead_node_elim);
285 register_hook(hook_dead_node_elim_subst, &res->dead_node_elim_subst);
290 * Free a Survive DCE environment.
292 void free_survive_dce(survive_dce_t *sd)
294 obstack_free(&sd->obst, NULL);
295 pmap_destroy(sd->places);
296 unregister_hook(hook_dead_node_elim, &sd->dead_node_elim);
297 unregister_hook(hook_dead_node_elim_subst, &sd->dead_node_elim_subst);
302 * Register a node pointer to be patched upon DCE.
303 * When DCE occurs, the node pointer specified by @p place will be
304 * patched to the new address of the node it is pointing to.
306 * @param sd The Survive DCE environment.
307 * @param place The address of the node pointer.
309 void survive_dce_register_irn(survive_dce_t *sd, ir_node **place)
311 if (*place != NULL) {
312 ir_node *irn = *place;
313 survive_dce_list_t *curr = pmap_get(sd->places, irn);
314 survive_dce_list_t *nw = OALLOC(&sd->obst, survive_dce_list_t);
319 pmap_insert(sd->places, irn, nw);