irgmod.c 7.47 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.
 */

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
/**
 * @file
 * @brief    Support for ir graph modification.
 * @author   Martin Trapp, Christian Schaefer, Goetz Lindenmaier
 * @version  $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
25
 */
Matthias Braun's avatar
Matthias Braun committed
26
#include "config.h"
Boris Boesler's avatar
added    
Boris Boesler committed
27

Michael Beck's avatar
Michael Beck committed
28
29
30
31
32
33
34
35
36
37
#include "irflag_t.h"
#include "irgwalk.h"
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgmod.h"
#include "array.h"
#include "ircons.h"
#include "irhooks.h"
#include "iredges_t.h"
#include "irtools.h"
38
#include "error.h"
Christian Schäfer's avatar
Christian Schäfer committed
39

Christian Würdig's avatar
Christian Würdig committed
40
41
42
43
44
45
/**
 * Turns a node into a "useless" Tuple.  The Tuple just forms a tuple
 * from several inputs.
 * This is useful if a node returning a tuple is removed, but the Projs
 * extracting values from the tuple are not available.
 */
46
47
void turn_into_tuple(ir_node *node, int arity)
{
48
49
50
51
52
53
54
	ir_graph *irg = get_irn_irg(node);
	ir_node **in  = ALLOCAN(ir_node*, arity);
	int       i;

	/* construct a new in array, with every input being bad */
	for (i = 0; i < arity; ++i) {
		in[i] = new_r_Bad(irg);
Christian Würdig's avatar
Christian Würdig committed
55
	}
56
57
	set_irn_in(node, arity, in);
	set_irn_op(node, op_Tuple);
Christian Schäfer's avatar
Christian Schäfer committed
58
59
}

Christian Würdig's avatar
Christian Würdig committed
60
61
62
63
64
/**
 * Insert irnode `new' in place of irnode `old'
 * Since `new' may be bigger than `old' replace `old'
 * by an op_Id which is smaller than everything.
 */
65
66
void exchange(ir_node *old, ir_node *nw)
{
Christian Würdig's avatar
Christian Würdig committed
67
68
69
70
71
72
73
74
75
76
77
	ir_graph *irg;

	assert(old && nw);
	assert(old != nw && "Exchanging node with itself is not allowed");

	irg = get_irn_irg(old);
	assert(irg == get_irn_irg(nw) && "New node must be in same irg as old node");

	hook_replace(old, nw);

	/*
78
79
80
	 * If new outs are on, we can skip the id node creation and reroute
	 * the edges from the old node to the new directly.
	 */
Christian Würdig's avatar
Christian Würdig committed
81
82
83
84
85
86
87
	if (edges_activated(irg)) {
		/* copy all dependencies from old to new */
		add_irn_deps(nw, old);

		edges_reroute(old, nw, irg);
		edges_reroute_kind(old, nw, EDGE_KIND_DEP, irg);
		edges_node_deleted(old, irg);
88
89
		/* noone is allowed to reference this node anymore */
		set_irn_op(old, op_Deleted);
90
	} else {
Christian Würdig's avatar
Christian Würdig committed
91
92
93
94
95
96
97
98
99
100
		/* Else, do it the old-fashioned way. */
		ir_node *block;

		hook_turn_into_id(old);

		block = old->in[0];
		if (! block) {
			block = is_Block(nw) ? nw : get_nodes_block(nw);

			if (! block) {
101
				panic("cannot find legal block for id");
Christian Würdig's avatar
Christian Würdig committed
102
103
104
			}
		}

105
106
107
108
		if (get_irn_op(old)->opar == oparity_dynamic) {
			DEL_ARR_F(get_irn_in(old));
		}

Christian Würdig's avatar
Christian Würdig committed
109
110
111
112
113
		old->op    = op_Id;
		old->in    = NEW_ARR_D (ir_node *, irg->obst, 2);
		old->in[0] = block;
		old->in[1] = nw;
	}
Christian Schäfer's avatar
Christian Schäfer committed
114
}
115

116
117
118
/*--------------------------------------------------------------------*/
/*  Functionality for collect_phis                                    */
/*--------------------------------------------------------------------*/
119

Michael Beck's avatar
Michael Beck committed
120
/**
121
 * Walker: links all Phi nodes to their Blocks lists,
Matthias Braun's avatar
Matthias Braun committed
122
 *         all Proj nodes to there predecessors.
Michael Beck's avatar
Michael Beck committed
123
 */
124
125
static void collect_phiprojs_walker(ir_node *n, void *env)
{
Christian Würdig's avatar
Christian Würdig committed
126
	ir_node *pred;
127
	(void) env;
Christian Würdig's avatar
Christian Würdig committed
128
129

	if (is_Phi(n)) {
130
		ir_node *block = get_nodes_block(n);
Michael Beck's avatar
Michael Beck committed
131
		add_Block_phi(block, n);
132
	} else if (is_Proj(n)) {
Christian Würdig's avatar
Christian Würdig committed
133
134
135
136
137
138
139
140
		pred = n;
		do {
			pred = get_Proj_pred(pred);
		} while (is_Proj(pred));

		set_irn_link(n, get_irn_link(pred));
		set_irn_link(pred, n);
	}
141
142
}

143
144
void collect_phiprojs(ir_graph *irg)
{
145
	assert((ir_resources_reserved(irg) & (IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST)) ==
146
		(IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST));
147
	irg_walk_graph(irg, firm_clear_node_and_phi_links, collect_phiprojs_walker, NULL);
148
149
}

150
151
152
/*--------------------------------------------------------------------*/
/*  Functionality for part_block                                      */
/*--------------------------------------------------------------------*/
153

Michael Beck's avatar
Michael Beck committed
154
155
156
157
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
158
159
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
Christian Würdig's avatar
Christian Würdig committed
160
	int i, arity;
161
162
163
164

	/* move this node */
	set_nodes_block(node, to_bl);

Michael Beck's avatar
Michael Beck committed
165
	/* move its Projs */
166
	if (get_irn_mode(node) == mode_T) {
Michael Beck's avatar
Michael Beck committed
167
		ir_node *proj = get_irn_link(node);
168
169
170
171
172
173
		while (proj) {
			if (get_nodes_block(proj) == from_bl)
				set_nodes_block(proj, to_bl);
			proj = get_irn_link(proj);
		}
	}
Christian Würdig's avatar
Christian Würdig committed
174

175
176
177
	if (is_Phi(node))
		return;

Christian Würdig's avatar
Christian Würdig committed
178
	/* recursion ... */
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
	arity = get_irn_arity(node);
	for (i = 0; i < arity; i++) {
		ir_node *pred = get_irn_n(node, i);
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
}

/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
static void move_alt(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
	int i, arity;

	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its Projs */
	if (get_irn_mode(node) == mode_T) {
		const ir_edge_t *edge;
		foreach_out_edge(node, edge) {
			ir_node *proj = get_edge_src_irn(edge);
			set_nodes_block(proj, to_bl);
		}
	}

	/* We must not move predecessors of Phi nodes, even if they are in
	 * from_bl. (because these are values from an earlier loop iteration
	 * which are not predecessors of node here)
	 */
Michael Beck's avatar
Michael Beck committed
211
212
	if (is_Phi(node))
		return;
Christian Würdig's avatar
Christian Würdig committed
213

214
	/* recursion ... */
Christian Würdig's avatar
Christian Würdig committed
215
216
	arity = get_irn_arity(node);
	for (i = 0; i < arity; i++) {
Michael Beck's avatar
Michael Beck committed
217
		ir_node *pred = get_irn_n(node, i);
Christian Würdig's avatar
Christian Würdig committed
218
219
220
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
221
222
}

223
224
void part_block(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
225
226
	ir_node *new_block, *old_block;
	ir_node *phi, *jmp;
227
228
	ir_graph *rem = current_ir_graph;

Christian Würdig's avatar
Christian Würdig committed
229
230
231
232
	/* Turn off optimizations so that blocks are not merged again. */
	int rem_opt = get_opt_optimize();
	set_optimize(0);

233
234
	current_ir_graph = get_irn_irg(node);

Christian Würdig's avatar
Christian Würdig committed
235
236
237
	/* Transform the control flow */
	old_block = get_nodes_block(node);
	new_block = new_Block(get_Block_n_cfgpreds(old_block),
238
	                      get_Block_cfgpred_arr(old_block));
239

240
241
242
	/* create a jump from new_block to old_block, which is now the lower one */
	jmp = new_r_Jmp(new_block);
	set_irn_in(old_block, 1, &jmp);
Christian Würdig's avatar
Christian Würdig committed
243
244
245
246
247

	/* move node and its predecessors to new_block */
	move(node, old_block, new_block);

	/* move Phi nodes to new_block */
Michael Beck's avatar
Michael Beck committed
248
249
250
	phi = get_Block_phis(old_block);
	set_Block_phis(new_block, phi);
	set_Block_phis(old_block, NULL);
Christian Würdig's avatar
Christian Würdig committed
251
252
	while (phi) {
		set_nodes_block(phi, new_block);
Michael Beck's avatar
Michael Beck committed
253
		phi = get_Phi_next(phi);
Christian Würdig's avatar
Christian Würdig committed
254
255
256
	}

	set_optimize(rem_opt);
257
	current_ir_graph = rem;
258
}
259

260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
ir_node *part_block_edges(ir_node *node)
{
	ir_node         *old_block = get_nodes_block(node);
	ir_node         *new_block = new_Block(get_Block_n_cfgpreds(old_block),
	                                       get_Block_cfgpred_arr(old_block));
	const ir_edge_t *edge;
	const ir_edge_t *next;

	/* old_block has no predecessors anymore for now */
	set_irn_in(old_block, 0, NULL);

	/* move node and its predecessors to new_block */
	move_alt(node, old_block, new_block);

	/* move Phi nodes to new_block */
	foreach_out_edge_safe(old_block, edge, next) {
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;
		set_nodes_block(phi, new_block);
	}

	return old_block;
}

285
286
void kill_node(ir_node *node)
{
287
288
289
290
291
292
293
294
295
	ir_graph *irg = get_irn_irg(node);
	ir_node *bad = get_irg_bad(irg);
	int i;

	for (i = get_irn_arity(node) - 1; i >= -1; --i) {
		set_irn_n(node, i, bad);
	}
	exchange(node, bad);
}