beirgmod.c 8.69 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * 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.
 */

Christian Würdig's avatar
Christian Würdig committed
20
/**
21
 * @file
Christian Würdig's avatar
Christian Würdig committed
22
23
24
25
26
 * @brief       Backend IRG modification routines.
 * @author      Sebastian Hack, Daniel Grund, Matthias Braun, Christian Wuerdig
 * @date        04.05.2005
 * @version     $Id$
 *
Christian Würdig's avatar
Christian Würdig committed
27
28
29
30
31
 * This file contains the following IRG modifications for be routines:
 * - insertion of Perm nodes
 * - empty block elimination
 * - a simple dead node elimination (set inputs of unreachable nodes to BAD)
 */
32
#include "config.h"
Sebastian Hack's avatar
Sebastian Hack committed
33
34
35
36
37
38
39

#include <stdlib.h>

#include "hashptr.h"
#include "pdeq.h"
#include "pset.h"
#include "pmap.h"
40
#include "util.h"
Sebastian Hack's avatar
Sebastian Hack committed
41
#include "debug.h"
42
#include "error.h"
43
#include "xmalloc.h"
Sebastian Hack's avatar
Sebastian Hack committed
44
45
46
47

#include "irflag_t.h"
#include "ircons_t.h"
#include "irnode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
48
#include "ircons_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
49
50
51
#include "irmode_t.h"
#include "irdom_t.h"
#include "iredges_t.h"
52
#include "irgraph_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
53
#include "irgopt.h"
54
#include "irgmod.h"
Sebastian Hack's avatar
Sebastian Hack committed
55
56
#include "irprintf_t.h"
#include "irgwalk.h"
Sebastian Hack's avatar
Sebastian Hack committed
57

58
#include "be_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
59
#include "bechordal_t.h"
60
61
#include "bearch.h"
#include "besched.h"
62
#include "belive_t.h"
63
#include "benode.h"
Sebastian Hack's avatar
Sebastian Hack committed
64
#include "beutil.h"
Sebastian Hack's avatar
Sebastian Hack committed
65
#include "beinsn_t.h"
66
#include "bessaconstr.h"
67
#include "beirg.h"
Sebastian Hack's avatar
Sebastian Hack committed
68
#include "beirgmod.h"
Christian Würdig's avatar
Christian Würdig committed
69
#include "bemodule.h"
Sebastian Hack's avatar
Sebastian Hack committed
70

Matthias Braun's avatar
Matthias Braun committed
71
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
Sebastian Hack's avatar
Sebastian Hack committed
72

Sebastian Hack's avatar
Sebastian Hack committed
73
74
75
76
77
78
79
80
81
/*
  ___                     _     ____
 |_ _|_ __  ___  ___ _ __| |_  |  _ \ ___ _ __ _ __ ___
  | || '_ \/ __|/ _ \ '__| __| | |_) / _ \ '__| '_ ` _ \
  | || | | \__ \  __/ |  | |_  |  __/  __/ |  | | | | | |
 |___|_| |_|___/\___|_|   \__| |_|   \___|_|  |_| |_| |_|

*/

82
ir_node *insert_Perm_after(ir_graph *irg, const arch_register_class_t *cls,
Sebastian Hack's avatar
Sebastian Hack committed
83
84
						   ir_node *pos)
{
85
	be_lv_t *lv     = be_get_irg_liveness(irg);
Sebastian Hack's avatar
Sebastian Hack committed
86
	ir_node *bl     = is_Block(pos) ? pos : get_nodes_block(pos);
87
88
	ir_nodeset_t          live;
	ir_nodeset_iterator_t iter;
Sebastian Hack's avatar
Sebastian Hack committed
89

90
	ir_node *irn, *perm, **nodes;
91
	size_t i, n;
Sebastian Hack's avatar
Sebastian Hack committed
92
93
94

	DBG((dbg, LEVEL_1, "Insert Perm after: %+F\n", pos));

95
	ir_nodeset_init(&live);
96
	be_liveness_nodes_live_at(lv, cls, pos, &live);
Sebastian Hack's avatar
Sebastian Hack committed
97

98
	n = ir_nodeset_size(&live);
99
	if (n == 0) {
100
		ir_nodeset_destroy(&live);
Sebastian Hack's avatar
Sebastian Hack committed
101
		return NULL;
Michael Beck's avatar
Michael Beck committed
102
	}
Sebastian Hack's avatar
Sebastian Hack committed
103

104
	nodes = XMALLOCN(ir_node*, n);
Sebastian Hack's avatar
Sebastian Hack committed
105
106

	DBG((dbg, LEVEL_1, "live:\n"));
107
108
	i = 0;
	foreach_ir_nodeset(&live, irn, iter) {
Sebastian Hack's avatar
Sebastian Hack committed
109
110
		DBG((dbg, LEVEL_1, "\t%+F\n", irn));
		nodes[i] = irn;
111
		i++;
Sebastian Hack's avatar
Sebastian Hack committed
112
	}
113
	ir_nodeset_destroy(&live);
Sebastian Hack's avatar
Sebastian Hack committed
114

115
	perm = be_new_Perm(cls, bl, n, nodes);
Sebastian Hack's avatar
Sebastian Hack committed
116
117
118
	sched_add_after(pos, perm);
	free(nodes);

119
	for (i = 0; i < n; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
120
		ir_node *perm_op = get_irn_n(perm, i);
121
		const arch_register_t *reg = arch_get_irn_register(perm_op);
122
		be_ssa_construction_env_t senv;
Sebastian Hack's avatar
Sebastian Hack committed
123
124

		ir_mode *mode = get_irn_mode(perm_op);
125
		ir_node *proj = new_r_Proj(perm, mode, i);
126
		arch_set_irn_register(proj, reg);
Sebastian Hack's avatar
Sebastian Hack committed
127

128
		be_ssa_construction_init(&senv, irg);
129
130
131
132
133
134
135
		be_ssa_construction_add_copy(&senv, perm_op);
		be_ssa_construction_add_copy(&senv, proj);
		be_ssa_construction_fix_users(&senv, perm_op);
		be_ssa_construction_update_liveness_phis(&senv, lv);
		be_liveness_update(lv, perm_op);
		be_liveness_update(lv, proj);
		be_ssa_construction_destroy(&senv);
Sebastian Hack's avatar
Sebastian Hack committed
136
	}
Sebastian Hack's avatar
Sebastian Hack committed
137

Sebastian Hack's avatar
Sebastian Hack committed
138
139
	return perm;
}
Sebastian Hack's avatar
Sebastian Hack committed
140

141
142
static int blocks_removed;

143
144
145
146
/**
 * Post-block-walker: Find blocks containing only one jump and
 * remove them.
 */
147
148
static void remove_empty_block(ir_node *block)
{
149
	const ir_edge_t *edge, *next;
150
	int      i, arity;
151
	ir_node *node;
152
	ir_node *pred;
153
	ir_node *succ_block;
154
	ir_node *jump = NULL;
155
	ir_graph *irg = get_irn_irg(block);
156

157
	if (irn_visited_else_mark(block))
158
		return;
159

160
	if (get_Block_n_cfgpreds(block) != 1)
161
		goto check_preds;
162
163

	sched_foreach(block, node) {
164
		if (! is_Jmp(node)
165
				&& !(arch_get_irn_flags(node) & arch_irn_flags_simple_jump))
166
			goto check_preds;
167
168
		if (jump != NULL) {
			/* we should never have 2 jumps in a block */
169
			panic("found 2 jumps in a block");
170
171
172
		}
		jump = node;
	}
173
174

	if (jump == NULL)
175
		goto check_preds;
176

177
	pred       = get_Block_cfgpred(block, 0);
178
	succ_block = NULL;
179
	foreach_out_edge_safe(jump, edge, next) {
180
		int pos = get_edge_src_pos(edge);
181

182
183
		assert(succ_block == NULL);
		succ_block = get_edge_src_irn(edge);
184
		if (has_Block_entity(succ_block) && has_Block_entity(block)) {
185
186
187
188
189
190
			/*
			 * Currently we can add only one label for a block.
			 * Therefore we cannot combine them if  both block already have one.
			 */
			goto check_preds;
		}
191

192
		set_irn_n(succ_block, pos, pred);
193
194
	}

195
	if (has_Block_entity(block)) {
196
		/* move the label to the successor block */
197
198
		ir_entity *entity = get_Block_entity(block);
		set_Block_entity(succ_block, entity);
199
200
	}

201
	/* there can be some non-scheduled Pin nodes left in the block, move them
202
	 * to the succ block (Pin) or pred block (Sync) */
203
204
205
	foreach_out_edge_safe(block, edge, next) {
		node = get_edge_src_irn(edge);

206
		if (node == jump)
207
			continue;
208
		/* we simply kill Pins, because there are some strange interactions
yb9976's avatar
yb9976 committed
209
210
		 * between jump threading, which produce PhiMs with Pins, we simply
		 * kill the pins here, everything is scheduled anyway */
211
		if (is_Pin(node)) {
212
			exchange(node, get_Pin_op(node));
213
214
			continue;
		}
215
216
217
218
		if (is_Sync(node)) {
			set_nodes_block(node, get_nodes_block(pred));
			continue;
		}
219
220
221
222
223
		if (is_End(node)) { /* End-keep, reroute it to the successor */
			int pos = get_edge_src_pos(edge);
			set_irn_n(node, pos, succ_block);
			continue;
		}
224
		panic("Unexpected node %+F in block %+F with empty schedule", node, block);
225
226
	}

Matthias Braun's avatar
Matthias Braun committed
227
	set_Block_cfgpred(block, 0, new_r_Bad(irg, mode_X));
228
	kill_node(jump);
229
230
231
232
233
234
235
236
	blocks_removed = 1;

	/* check predecessor */
	remove_empty_block(get_nodes_block(pred));
	return;

check_preds:
	arity = get_Block_n_cfgpreds(block);
237
	for (i = 0; i < arity; ++i) {
238
239
240
		ir_node *pred = get_Block_cfgpred_block(block, i);
		remove_empty_block(pred);
	}
241
242
}

243
/* removes basic blocks that just contain a jump instruction */
244
245
246
247
248
249
250
int be_remove_empty_blocks(ir_graph *irg)
{
	ir_node *end;
	int      i, arity;

	blocks_removed = 0;

251
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
252
253
254
255
	inc_irg_visited(irg);
	remove_empty_block(get_irg_end_block(irg));
	end   = get_irg_end(irg);
	arity = get_irn_arity(end);
256
	for (i = 0; i < arity; ++i) {
257
		ir_node *pred = get_irn_n(end, i);
258
		if (!is_Block(pred))
259
260
261
			continue;
		remove_empty_block(pred);
	}
262
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
263

264
	if (blocks_removed) {
265
		/* invalidate analysis info */
266
267
		clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE
		                   | IR_GRAPH_STATE_VALID_EXTENDED_BLOCKS);
268
	}
269
	return blocks_removed;
270
}
Matthias Braun's avatar
Matthias Braun committed
271

Matthias Braun's avatar
Matthias Braun committed
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
//---------------------------------------------------------------------------

typedef struct remove_dead_nodes_env_t_ {
	bitset_t *reachable;
	ir_graph *irg;
	be_lv_t  *lv;
} remove_dead_nodes_env_t;

/**
 * Post-walker: remember all visited nodes in a bitset.
 */
static void mark_dead_nodes_walker(ir_node *node, void *data)
{
	remove_dead_nodes_env_t *env = (remove_dead_nodes_env_t*) data;
	bitset_set(env->reachable, get_irn_idx(node));
}

/**
 * Post-block-walker:
 * Walk through the schedule of every block and remove all dead nodes from it.
 */
static void remove_dead_nodes_walker(ir_node *block, void *data)
{
	remove_dead_nodes_env_t *env = (remove_dead_nodes_env_t*) data;
	ir_node                 *node, *next;

	for (node = sched_first(block); ! sched_is_end(node); node = next) {
		/* get next node now, as after calling sched_remove it will be invalid */
		next = sched_next(node);

		if (bitset_is_set(env->reachable, get_irn_idx(node)))
			continue;

305
		if (env->lv != NULL)
Matthias Braun's avatar
Matthias Braun committed
306
307
			be_liveness_remove(env->lv, node);
		sched_remove(node);
308
309
310
311
312
313
314
315
316
317
318
319
320
321

		/* kill projs */
		if (get_irn_mode(node) == mode_T) {
			const ir_edge_t *edge;
			const ir_edge_t *next_edge;
			foreach_out_edge_safe(node, edge, next_edge) {
				ir_node *proj = get_edge_src_irn(edge);
				if (!is_Proj(proj))
					continue;
				if (env->lv != NULL)
					be_liveness_remove(env->lv, proj);
				kill_node(proj);
			}
		}
Matthias Braun's avatar
Matthias Braun committed
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
		kill_node(node);
	}
}

void be_remove_dead_nodes_from_schedule(ir_graph *irg)
{
	remove_dead_nodes_env_t env;
	env.reachable = bitset_alloca(get_irg_last_idx(irg));
	env.lv        = be_get_irg_liveness(irg);
	env.irg       = irg;

	// mark all reachable nodes
	irg_walk_graph(irg, mark_dead_nodes_walker, NULL, &env);

	// walk schedule and remove non-marked nodes
	irg_block_walk_graph(irg, remove_dead_nodes_walker, NULL, &env);
}

Matthias Braun's avatar
Matthias Braun committed
340
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_irgmod)
Matthias Braun's avatar
Matthias Braun committed
341
342
343
344
void be_init_irgmod(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.irgmod");
}