irgmod.c 9.01 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"
Matthias Braun's avatar
Matthias Braun committed
21
#include "panic.h"
Christian Schäfer's avatar
Christian Schäfer committed
22

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

30
31
void exchange(ir_node *old, ir_node *nw)
{
Matthias Braun's avatar
Matthias Braun committed
32
33
	assert(old != NULL && nw != NULL);
	assert(old != nw);
Christian Würdig's avatar
Christian Würdig committed
34

Matthias Braun's avatar
Matthias Braun committed
35
36
	ir_graph *irg = get_irn_irg(old);
	assert(irg == get_irn_irg(nw));
37
38
39
40
#ifndef NDEBUG
	/* When replacing a PhiM node, it must not be hold by a keep-alive edge.
	 * => Keep-alive edges are not normal users and should not move along when
	 * exchanging. */
41
42
	if (is_Phi(old) && get_Phi_loop(old) && !(is_Phi(nw) && get_Phi_loop(nw))
	    && !is_Bad(nw)) {
43
44
45
46
47
48
		ir_node *end = get_irg_end(irg);
		foreach_irn_in(end, i, kept) {
			assert(kept != old);
		}
	}
#endif
Christian Würdig's avatar
Christian Würdig committed
49
50
51

	hook_replace(old, nw);

Matthias Braun's avatar
Matthias Braun committed
52
53
	/* 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
54
55
56
57
	if (edges_activated(irg)) {
		/* copy all dependencies from old to new */
		add_irn_deps(nw, old);

Matthias Braun's avatar
Matthias Braun committed
58
59
60
		edges_reroute(old, nw);
		edges_reroute_kind(old, nw, EDGE_KIND_DEP);
		edges_node_deleted(old);
61
62
		/* noone is allowed to reference this node anymore */
		set_irn_op(old, op_Deleted);
63
	} else {
Christian Würdig's avatar
Christian Würdig committed
64
65
66
		/* Else, do it the old-fashioned way. */
		hook_turn_into_id(old);

Matthias Braun's avatar
Matthias Braun committed
67
68
		ir_node *block = old->in[0];
		if (block == NULL) {
Christian Würdig's avatar
Christian Würdig committed
69
70
			block = is_Block(nw) ? nw : get_nodes_block(nw);

Matthias Braun's avatar
Matthias Braun committed
71
			if (block == NULL) {
72
				panic("cannot find legal block for id");
Christian Würdig's avatar
Christian Würdig committed
73
74
75
			}
		}

76
77
78
79
		if (get_irn_op(old)->opar == oparity_dynamic) {
			DEL_ARR_F(get_irn_in(old));
		}

Christian Würdig's avatar
Christian Würdig committed
80
		old->op    = op_Id;
81
		old->in    = NEW_ARR_D(ir_node*, get_irg_obstack(irg), 2);
Christian Würdig's avatar
Christian Würdig committed
82
83
84
		old->in[0] = block;
		old->in[1] = nw;
	}
85
86

	/* update irg flags */
87
	clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS
Matthias Braun's avatar
Matthias Braun committed
88
	                        | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
Christian Schäfer's avatar
Christian Schäfer committed
89
}
90

Michael Beck's avatar
Michael Beck committed
91
/**
92
 * Walker: links all Phi nodes to their Blocks lists,
Matthias Braun's avatar
Matthias Braun committed
93
 *         all Proj nodes to there predecessors.
Michael Beck's avatar
Michael Beck committed
94
 */
95
96
static void collect_phiprojs_walker(ir_node *n, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
97
	(void)env;
Christian Würdig's avatar
Christian Würdig committed
98
99

	if (is_Phi(n)) {
100
		ir_node *block = get_nodes_block(n);
Michael Beck's avatar
Michael Beck committed
101
		add_Block_phi(block, n);
102
	} else if (is_Proj(n)) {
Matthias Braun's avatar
Matthias Braun committed
103
		ir_node *pred = n;
Christian Würdig's avatar
Christian Würdig committed
104
105
106
107
108
109
110
		do {
			pred = get_Proj_pred(pred);
		} while (is_Proj(pred));

		set_irn_link(n, get_irn_link(pred));
		set_irn_link(pred, n);
	}
111
112
}

113
114
void collect_phiprojs(ir_graph *irg)
{
115
	assert((ir_resources_reserved(irg) & (IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST)) ==
116
		(IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST));
117
	irg_walk_graph(irg, firm_clear_node_and_phi_links, collect_phiprojs_walker, NULL);
118
119
}

Michael Beck's avatar
Michael Beck committed
120
121
122
123
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
124
125
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
126
127
128
	/* move this node */
	set_nodes_block(node, to_bl);

Michael Beck's avatar
Michael Beck committed
129
	/* move its Projs */
130
	if (get_irn_mode(node) == mode_T) {
131
		ir_node *proj = (ir_node*)get_irn_link(node);
132
133
134
		while (proj) {
			if (get_nodes_block(proj) == from_bl)
				set_nodes_block(proj, to_bl);
135
			proj = (ir_node*)get_irn_link(proj);
136
137
		}
	}
Christian Würdig's avatar
Christian Würdig committed
138

139
140
141
	if (is_Phi(node))
		return;

Christian Würdig's avatar
Christian Würdig committed
142
	/* recursion ... */
143
	foreach_irn_in(node, i, pred) {
144
145
146
147
148
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
}

149
150
151
152
153
154
155
156
157
158
159
160
161
162
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);
	}
}

163
164
165
166
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
167
static void move_edges(ir_node *node, ir_node *from_bl, ir_node *to_bl)
168
169
170
171
172
{
	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its Projs */
173
	move_projs(node, to_bl);
174
175
176
177
178

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

182
	/* recursion ... */
183
	foreach_irn_in(node, i, pred) {
Christian Würdig's avatar
Christian Würdig committed
184
		if (get_nodes_block(pred) == from_bl)
185
			move_edges(pred, from_bl, to_bl);
Christian Würdig's avatar
Christian Würdig committed
186
	}
187
188
}

189
190
void part_block(ir_node *node)
{
Christian Würdig's avatar
Christian Würdig committed
191
	/* Turn off optimizations so that blocks are not merged again. */
Matthias Braun's avatar
Matthias Braun committed
192
	int rem_opt = get_optimize();
Christian Würdig's avatar
Christian Würdig committed
193
194
195
	set_optimize(0);

	/* Transform the control flow */
Matthias Braun's avatar
Matthias Braun committed
196
197
198
199
	ir_node  *old_block = get_nodes_block(node);
	ir_graph *irg       = get_irn_irg(node);
	ir_node  *new_block = new_r_Block(irg, get_Block_n_cfgpreds(old_block),
	                                  get_Block_cfgpred_arr(old_block));
200

201
	/* create a jump from new_block to old_block, which is now the lower one */
Matthias Braun's avatar
Matthias Braun committed
202
	ir_node *jmp = new_r_Jmp(new_block);
203
	set_irn_in(old_block, 1, &jmp);
Christian Würdig's avatar
Christian Würdig committed
204
205
206
207
208

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

	/* move Phi nodes to new_block */
Matthias Braun's avatar
Matthias Braun committed
209
	ir_node *phi = get_Block_phis(old_block);
Michael Beck's avatar
Michael Beck committed
210
211
	set_Block_phis(new_block, phi);
	set_Block_phis(old_block, NULL);
Christian Würdig's avatar
Christian Würdig committed
212
213
	while (phi) {
		set_nodes_block(phi, new_block);
Michael Beck's avatar
Michael Beck committed
214
		phi = get_Phi_next(phi);
Christian Würdig's avatar
Christian Würdig committed
215
216
217
	}

	set_optimize(rem_opt);
218
}
219

220
221
ir_node *part_block_edges(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
222
223
224
225
226
	ir_node  *old_block  = get_nodes_block(node);
	int       n_cfgpreds = get_Block_n_cfgpreds(old_block);
	ir_node **cfgpreds   = get_Block_cfgpred_arr(old_block);
	ir_graph *irg        = get_irn_irg(node);
	ir_node  *new_block  = new_r_Block(irg, n_cfgpreds, cfgpreds);
227
228
229
230
231

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

	/* move node and its predecessors to new_block */
232
	move_edges(node, old_block, new_block);
233
234

	/* move Phi nodes to new_block */
235
	foreach_out_edge_safe(old_block, edge) {
236
237
238
239
240
241
242
243
244
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;
		set_nodes_block(phi, new_block);
	}

	return old_block;
}

245
246
void kill_node(ir_node *node)
{
247
	ir_graph *irg = get_irn_irg(node);
Matthias Braun's avatar
Matthias Braun committed
248
249
	if (edges_activated(irg)) {
		edges_node_deleted(node);
250
	}
Matthias Braun's avatar
Matthias Braun committed
251
252
	/* noone is allowed to reference this node anymore */
	set_irn_op(node, op_Deleted);
253
}
254
255
256
257
258
259

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)) {
260
	case iro_Address:
261
		return new_rd_Address(dbg, irg, get_Address_entity(n));
262
263
	case iro_Align:
		return new_rd_Align(dbg, irg, mode, get_Align_type(n));
264
265
	case iro_Const:
		return new_rd_Const(dbg, irg, get_Const_tarval(n));
266
267
	case iro_Offset:
		return new_rd_Offset(dbg, irg, mode, get_Offset_entity(n));
268
269
	case iro_Size:
		return new_rd_Size(dbg, irg, mode, get_Size_type(n));
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
307
308
309
310
	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);
311
312
	case iro_NoMem:
		return get_irg_no_mem(irg);
313
314
315
316
317
	case iro_Member: {
		ir_node   *ptr    = duplicate_subgraph(dbg, get_Member_ptr(n), block);
		ir_entity *entity = get_Member_entity(n);
		return new_rd_Member(dbg, block, ptr, entity);
	}
318
	case iro_Sel: {
319
320
321
		ir_node *ptr   = duplicate_subgraph(dbg, get_Sel_ptr(n), block);
		ir_node *index = duplicate_subgraph(dbg, get_Sel_index(n), block);
		return new_rd_Sel(dbg, block, ptr, index, get_Sel_type(n));
322
	}
323
324
325
326
327
328
329
	case iro_Unknown:
		return new_r_Unknown(irg, mode);
	default:
		break;
	}
	panic("opcode invalid or not implemented %+F", n);
}