dead_code_elimination.c 5.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief    Dead node elimination
 * @author   Michael Beck, Goetz Lindenmaier
 * @version  $Id: opt_inline.c 27265 2010-03-07 15:13:00Z matze $
 *
 * Strictly speaking dead node elimination is unnecessary in firm - everthying
 * which is not used can't be found by any walker.
 * The only drawback is that the nodes still take up memory. This phase fixes
 * this by copying all (reachable) nodes to a new obstack and throwing away
 * the old one.
 */
#include "config.h"

#include "iroptimize.h"
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irphase_t.h"
#include "iredges_t.h"
#include "irhooks.h"
#include "irtools.h"
#include "irgwalk.h"
#include "cgana.h"
#include "irouts.h"
#include "trouts.h"
#include "iropt_t.h"
#include "irpass.h"
#include "pmap.h"

/** a pointer to the new phases */
50
static ir_phase *new_phases[PHASE_LAST + 1];
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
 * Reroute the inputs of a node from nodes in the old graph to copied nodes in
 * the new graph
 */
static void rewire_inputs(ir_node *node, void *env)
{
	(void) env;
	irn_rewire_inputs(node);
}

static void copy_node_dce(ir_node *node, void *env)
{
64
65
66
	ir_phase_id i;
	ir_node    *new_node = exact_copy(node);
	ir_graph   *irg      = get_irn_irg(new_node);
67
68
69
70
71
72
	(void) env;

	/* preserve the node numbers for easier debugging */
	new_node->node_nr = node->node_nr;

	/* copy phase information for this node */
73
	for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
74
		ir_phase *phase = irg_get_phase(irg, i);
75
76
77
78
79
80
81
82
83
84
85
86
87
		if (phase == NULL)
			continue;
		if (!phase_get_irn_data(phase, node))
			continue;
		phase_set_irn_data(new_phases[i], new_node,
		                   phase_get_irn_data(phase, node));
	}

	set_irn_link(node, new_node);
	hook_dead_node_elim_subst(irg, node, new_node);
}

/**
88
89
 * Copies the graph reachable from the End node to the obstack
 * in irg. Then fixes the fields containing nodes of the graph.
90
91
92
93
94
 *
 * @param copy_node_nr  If non-zero, the node number will be copied
 */
static void copy_graph_env(ir_graph *irg)
{
95
96
	ir_node    *new_anchor;
	ir_phase_id i;
97
98

	/* init the new_phases array */
99
100
	/* TODO: this is wrong, it should only allocate a new data_ptr inside
	 * the phase! */
101
	for (i = PHASE_FIRST; i <= PHASE_LAST; ++i) {
102
		ir_phase *old_ph = irg_get_phase(irg, i);
103
104
105
		if (old_ph == NULL) {
			new_phases[i] = NULL;
		} else {
106
107
			new_phases[i] = new_phase(irg, old_ph->data_init);
			new_phases[i]->priv = old_ph->priv;
108
109
110
111
112
113
114
		}
	}

	/* copy nodes */
	irg_walk_anchors(irg, copy_node_dce, rewire_inputs, NULL);

	/* fix the anchor */
115
	new_anchor = (ir_node*)get_irn_link(irg->anchor);
116
117
118
119
	assert(new_anchor != NULL);
	irg->anchor = new_anchor;

	/* 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);
122
123
124
		if (old_ph == NULL)
			continue;

125
126
127
128
		/* Matze: commented out for now: This is a memory leak, but for a real
		 * fix we must not create new phases here, but reuse the old phases
		 * and just create a new data array */
		/* phase_free(old_ph); */
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
		irg->phases[i] = new_phases[i];
	}
}

/**
 * Copies all reachable nodes to a new obstack.  Removes bad inputs
 * from block nodes and the corresponding inputs from Phi nodes.
 * Merges single exit blocks with single entry blocks and removes
 * 1-input Phis.
 * Adds all new nodes to a new hash table for CSE.  Does not
 * perform CSE, so the hash table might contain common subexpressions.
 */
void dead_node_elimination(ir_graph *irg)
{
	struct obstack *graveyard_obst = NULL;
	struct obstack *rebirth_obst   = NULL;

	edges_deactivate(irg);

	/* inform statistics that we started a dead-node elimination run */
	hook_dead_node_elim(irg, 1);

	assert(get_irg_phase_state(irg) != phase_building);

	/* Handle graph state */
	free_callee_info(irg);
	free_irg_outs(irg);
	free_trouts();
	free_loop_information(irg);
158
	clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
159
160
161
162
163
164
165
166
167
168
169
170

	/* A quiet place, where the old obstack can rest in peace,
	   until it will be cremated. */
	graveyard_obst = irg->obst;

	/* A new obstack, where the reachable nodes will be copied to. */
	rebirth_obst = XMALLOC(struct obstack);
	irg->obst = rebirth_obst;
	obstack_init(irg->obst);
	irg->last_node_idx = 0;

	/* We also need a new value table for CSE */
171
	new_identities(irg);
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187

	/* Copy the graph from the old to the new obstack */
	copy_graph_env(irg);

	/* Free memory from old unoptimized obstack */
	obstack_free(graveyard_obst, 0);  /* First empty the obstack ... */
	xfree(graveyard_obst);            /* ... then free it.           */

	/* inform statistics that the run is over */
	hook_dead_node_elim(irg, 0);
}

ir_graph_pass_t *dead_node_elimination_pass(const char *name)
{
	return def_graph_pass(name ? name : "dce", dead_node_elimination);
}