dead_code_elimination.c 5.27 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
158
159
160
161
162
163
164
165
166
167
168
169
170
		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);
	set_irg_doms_inconsistent(irg);

	/* 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);
}