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 + 1];
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_FIRST; i <= PHASE_LAST; ++i) {
74 ir_phase *phase = irg_get_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 the End node to the obstack
89 * in irg. Then fixes the fields containing nodes of the graph.
91 * @param copy_node_nr If non-zero, the node number will be copied
93 static void copy_graph_env(ir_graph *irg)
98 /* init the new_phases array */
99 /* TODO: this is wrong, it should only allocate a new data_ptr inside
101 for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
102 ir_phase *old_ph = irg_get_phase(irg, i);
103 if (old_ph == NULL) {
104 new_phases[i] = NULL;
106 new_phases[i] = new_phase(irg, old_ph->data_init);
107 new_phases[i]->priv = old_ph->priv;
112 irg_walk_anchors(irg, copy_node_dce, rewire_inputs, NULL);
115 new_anchor = (ir_node*)get_irn_link(irg->anchor);
116 assert(new_anchor != NULL);
117 irg->anchor = new_anchor;
119 /* copy the new phases into the irg */
120 for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
121 ir_phase *old_ph = irg_get_phase(irg, i);
125 /* Matze: commented out for now: This is a memory leak, but for a real
126 * fix we must not create new phases here, but reuse the old phases
127 * and just create a new data array */
128 /* phase_free(old_ph); */
129 irg->phases[i] = new_phases[i];
134 * Copies all reachable nodes to a new obstack. Removes bad inputs
135 * from block nodes and the corresponding inputs from Phi nodes.
136 * Merges single exit blocks with single entry blocks and removes
138 * Adds all new nodes to a new hash table for CSE. Does not
139 * perform CSE, so the hash table might contain common subexpressions.
141 void dead_node_elimination(ir_graph *irg)
143 struct obstack *graveyard_obst = NULL;
144 struct obstack *rebirth_obst = NULL;
146 edges_deactivate(irg);
148 /* inform statistics that we started a dead-node elimination run */
149 hook_dead_node_elim(irg, 1);
151 assert(get_irg_phase_state(irg) != phase_building);
153 /* Handle graph state */
154 free_callee_info(irg);
157 free_loop_information(irg);
158 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
160 /* A quiet place, where the old obstack can rest in peace,
161 until it will be cremated. */
162 graveyard_obst = irg->obst;
164 /* A new obstack, where the reachable nodes will be copied to. */
165 rebirth_obst = XMALLOC(struct obstack);
166 irg->obst = rebirth_obst;
167 obstack_init(irg->obst);
168 irg->last_node_idx = 0;
170 /* We also need a new value table for CSE */
173 /* Copy the graph from the old to the new obstack */
176 /* Free memory from old unoptimized obstack */
177 obstack_free(graveyard_obst, 0); /* First empty the obstack ... */
178 xfree(graveyard_obst); /* ... then free it. */
180 /* inform statistics that the run is over */
181 hook_dead_node_elim(irg, 0);
184 ir_graph_pass_t *dead_node_elimination_pass(const char *name)
186 return def_graph_pass(name ? name : "dce", dead_node_elimination);