irgmod.c 8.62 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
/**
 * @file
 * @brief    Support for ir graph modification.
 * @author   Martin Trapp, Christian Schaefer, Goetz Lindenmaier
Götz Lindenmaier's avatar
Götz Lindenmaier committed
10
 */
Michael Beck's avatar
Michael Beck committed
11
12
13
14
15
16
17
18
19
20
#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"
21
#include "error.h"
Christian Schäfer's avatar
Christian Schäfer committed
22

23
void turn_into_tuple(ir_node *const node, int const arity, ir_node *const *const in)
24
{
25
26
	set_irn_in(node, arity, in);
	set_irn_op(node, op_Tuple);
Christian Schäfer's avatar
Christian Schäfer committed
27
28
}

29
30
void exchange(ir_node *old, ir_node *nw)
{
Christian Würdig's avatar
Christian Würdig committed
31
32
33
34
35
36
37
38
39
40
41
	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);

	/*
42
43
44
	 * 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
45
46
47
48
	if (edges_activated(irg)) {
		/* copy all dependencies from old to new */
		add_irn_deps(nw, old);

Matthias Braun's avatar
Matthias Braun committed
49
50
51
		edges_reroute(old, nw);
		edges_reroute_kind(old, nw, EDGE_KIND_DEP);
		edges_node_deleted(old);
52
53
		/* noone is allowed to reference this node anymore */
		set_irn_op(old, op_Deleted);
54
	} else {
Christian Würdig's avatar
Christian Würdig committed
55
56
57
58
59
60
61
62
63
64
		/* 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) {
65
				panic("cannot find legal block for id");
Christian Würdig's avatar
Christian Würdig committed
66
67
68
			}
		}

69
70
71
72
		if (get_irn_op(old)->opar == oparity_dynamic) {
			DEL_ARR_F(get_irn_in(old));
		}

Christian Würdig's avatar
Christian Würdig committed
73
		old->op    = op_Id;
74
		old->in    = NEW_ARR_D(ir_node*, get_irg_obstack(irg), 2);
Christian Würdig's avatar
Christian Würdig committed
75
76
77
		old->in[0] = block;
		old->in[1] = nw;
	}
78
79

	/* update irg flags */
80
81
	clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS
	                   | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
Christian Schäfer's avatar
Christian Schäfer committed
82
}
83

Michael Beck's avatar
Michael Beck committed
84
/**
85
 * Walker: links all Phi nodes to their Blocks lists,
Matthias Braun's avatar
Matthias Braun committed
86
 *         all Proj nodes to there predecessors.
Michael Beck's avatar
Michael Beck committed
87
 */
88
89
static void collect_phiprojs_walker(ir_node *n, void *env)
{
Christian Würdig's avatar
Christian Würdig committed
90
	ir_node *pred;
91
	(void) env;
Christian Würdig's avatar
Christian Würdig committed
92
93

	if (is_Phi(n)) {
94
		ir_node *block = get_nodes_block(n);
Michael Beck's avatar
Michael Beck committed
95
		add_Block_phi(block, n);
96
	} else if (is_Proj(n)) {
Christian Würdig's avatar
Christian Würdig committed
97
98
99
100
101
102
103
104
		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);
	}
105
106
}

107
108
void collect_phiprojs(ir_graph *irg)
{
109
	assert((ir_resources_reserved(irg) & (IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST)) ==
110
		(IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST));
111
	irg_walk_graph(irg, firm_clear_node_and_phi_links, collect_phiprojs_walker, NULL);
112
113
}

Michael Beck's avatar
Michael Beck committed
114
115
116
117
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
118
119
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
120
121
122
	/* move this node */
	set_nodes_block(node, to_bl);

Michael Beck's avatar
Michael Beck committed
123
	/* move its Projs */
124
	if (get_irn_mode(node) == mode_T) {
125
		ir_node *proj = (ir_node*)get_irn_link(node);
126
127
128
		while (proj) {
			if (get_nodes_block(proj) == from_bl)
				set_nodes_block(proj, to_bl);
129
			proj = (ir_node*)get_irn_link(proj);
130
131
		}
	}
Christian Würdig's avatar
Christian Würdig committed
132

133
134
135
	if (is_Phi(node))
		return;

Christian Würdig's avatar
Christian Würdig committed
136
	/* recursion ... */
137
	foreach_irn_in(node, i, pred) {
138
139
140
141
142
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
}

143
144
145
146
147
148
149
150
151
152
153
154
155
156
static void move_projs(const ir_node *node, ir_node *to_bl)
{
	if (get_irn_mode(node) != mode_T)
		return;

	foreach_out_edge(node, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;
		set_nodes_block(proj, to_bl);
		move_projs(proj, to_bl);
	}
}

157
158
159
160
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
161
static void move_edges(ir_node *node, ir_node *from_bl, ir_node *to_bl)
162
163
164
165
166
{
	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its Projs */
167
	move_projs(node, to_bl);
168
169
170
171
172

	/* 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
173
174
	if (is_Phi(node))
		return;
Christian Würdig's avatar
Christian Würdig committed
175

176
	/* recursion ... */
177
	foreach_irn_in(node, i, pred) {
Christian Würdig's avatar
Christian Würdig committed
178
		if (get_nodes_block(pred) == from_bl)
179
			move_edges(pred, from_bl, to_bl);
Christian Würdig's avatar
Christian Würdig committed
180
	}
181
182
}

183
184
void part_block(ir_node *node)
{
185
186
187
	ir_graph *irg = get_irn_irg(node);
	ir_node  *new_block, *old_block;
	ir_node  *phi, *jmp;
188

Christian Würdig's avatar
Christian Würdig committed
189
190
191
192
193
194
	/* Turn off optimizations so that blocks are not merged again. */
	int rem_opt = get_opt_optimize();
	set_optimize(0);

	/* Transform the control flow */
	old_block = get_nodes_block(node);
195
196
	new_block = new_r_Block(irg, get_Block_n_cfgpreds(old_block),
	                        get_Block_cfgpred_arr(old_block));
197

198
199
200
	/* 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
201
202
203
204
205

	/* 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
206
207
208
	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
209
210
	while (phi) {
		set_nodes_block(phi, new_block);
Michael Beck's avatar
Michael Beck committed
211
		phi = get_Phi_next(phi);
Christian Würdig's avatar
Christian Würdig committed
212
213
214
	}

	set_optimize(rem_opt);
215
}
216

217
218
ir_node *part_block_edges(ir_node *node)
{
219
220
221
	ir_graph *irg       = get_irn_irg(node);
	ir_node  *old_block = get_nodes_block(node);
	ir_node  *new_block = new_r_Block(irg, get_Block_n_cfgpreds(old_block), get_Block_cfgpred_arr(old_block));
222
223
224
225
226

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

	/* move node and its predecessors to new_block */
227
	move_edges(node, old_block, new_block);
228
229

	/* move Phi nodes to new_block */
230
	foreach_out_edge_safe(old_block, edge) {
231
232
233
234
235
236
237
238
239
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;
		set_nodes_block(phi, new_block);
	}

	return old_block;
}

240
241
void kill_node(ir_node *node)
{
242
243
	ir_graph *irg = get_irn_irg(node);

Matthias Braun's avatar
Matthias Braun committed
244
245
	if (edges_activated(irg)) {
		edges_node_deleted(node);
246
	}
Matthias Braun's avatar
Matthias Braun committed
247
248
	/* noone is allowed to reference this node anymore */
	set_irn_op(node, op_Deleted);
249
}
250
251
252
253
254
255

ir_node *duplicate_subgraph(dbg_info *dbg, ir_node *n, ir_node *block)
{
	ir_graph *irg  = get_irn_irg(block);
	ir_mode  *mode = get_irn_mode(n);
	switch (get_irn_opcode(n)) {
256
	case iro_Address:
257
		return new_rd_Address(dbg, irg, get_Address_entity(n));
258
259
	case iro_Align:
		return new_rd_Align(dbg, irg, mode, get_Align_type(n));
260
261
	case iro_Const:
		return new_rd_Const(dbg, irg, get_Const_tarval(n));
262
263
	case iro_Offset:
		return new_rd_Offset(dbg, irg, mode, get_Offset_entity(n));
264
265
	case iro_Size:
		return new_rd_Size(dbg, irg, mode, get_Size_type(n));
266
267
268
269
270
271
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
305
306
	case iro_Add:
		return new_rd_Add(dbg, block,
		                  duplicate_subgraph(dbg, get_Add_left(n), block),
		                  duplicate_subgraph(dbg, get_Add_right(n), block),
		                  mode);
	case iro_Sub:
		return new_rd_Sub(dbg, block,
		                  duplicate_subgraph(dbg, get_Sub_left(n), block),
		                  duplicate_subgraph(dbg, get_Sub_right(n), block),
		                  mode);
	case iro_Mul:
		return new_rd_Mul(dbg, block,
		                  duplicate_subgraph(dbg, get_Mul_left(n), block),
		                  duplicate_subgraph(dbg, get_Mul_right(n), block),
		                  mode);
	case iro_And:
		return new_rd_And(dbg, block,
		                  duplicate_subgraph(dbg, get_And_left(n), block),
		                  duplicate_subgraph(dbg, get_And_right(n), block),
		                  mode);
	case iro_Or:
		return new_rd_Or(dbg, block,
		                 duplicate_subgraph(dbg, get_Or_left(n), block),
		                 duplicate_subgraph(dbg, get_Or_right(n), block),
		                 mode);
	case iro_Eor:
		return new_rd_Eor(dbg, block,
		                  duplicate_subgraph(dbg, get_Eor_left(n), block),
		                  duplicate_subgraph(dbg, get_Eor_right(n), block),
		                  mode);
	case iro_Conv:
		return new_rd_Conv(dbg, block,
		                   duplicate_subgraph(dbg, get_Conv_op(n), block),
		                   mode);
	case iro_Minus:
		return new_rd_Minus(dbg, block,
		                    duplicate_subgraph(dbg, get_Minus_op(n), block),
		                    mode);
	case iro_Not:
		return new_rd_Not(dbg, block,
		                  duplicate_subgraph(dbg, get_Not_op(n), block), mode);
307
308
309
310
311
312
313
314
315
316
	case iro_NoMem:
		return get_irg_no_mem(irg);
	case iro_Sel: {
		ir_node  *ptr = duplicate_subgraph(dbg, get_Sel_ptr(n), block);
		int       n_indexs = get_Sel_n_indexs(n);
		ir_node **in       = ALLOCAN(ir_node*, n_indexs);
		for (int i = 0; i < n_indexs; ++i) {
			in[i] = duplicate_subgraph(dbg, get_Sel_index(n, i), block);
		}
		ir_entity *entity = get_Sel_entity(n);
317
		return new_rd_Sel(dbg, block, ptr, n_indexs, in, entity);
318
	}
319
320
321
322
323
324
325
	case iro_Unknown:
		return new_r_Unknown(irg, mode);
	default:
		break;
	}
	panic("opcode invalid or not implemented %+F", n);
}