irgmod.c 8.63 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));
Christian Würdig's avatar
Christian Würdig committed
37
38
39

	hook_replace(old, nw);

Matthias Braun's avatar
Matthias Braun committed
40
41
	/* 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
42
43
44
45
	if (edges_activated(irg)) {
		/* copy all dependencies from old to new */
		add_irn_deps(nw, old);

Matthias Braun's avatar
Matthias Braun committed
46
47
48
		edges_reroute(old, nw);
		edges_reroute_kind(old, nw, EDGE_KIND_DEP);
		edges_node_deleted(old);
49
50
		/* noone is allowed to reference this node anymore */
		set_irn_op(old, op_Deleted);
51
	} else {
Christian Würdig's avatar
Christian Würdig committed
52
53
54
		/* Else, do it the old-fashioned way. */
		hook_turn_into_id(old);

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

Matthias Braun's avatar
Matthias Braun committed
59
			if (block == NULL) {
60
				panic("cannot find legal block for id");
Christian Würdig's avatar
Christian Würdig committed
61
62
63
			}
		}

64
65
66
67
		if (get_irn_op(old)->opar == oparity_dynamic) {
			DEL_ARR_F(get_irn_in(old));
		}

Christian Würdig's avatar
Christian Würdig committed
68
		old->op    = op_Id;
69
		old->in    = NEW_ARR_D(ir_node*, get_irg_obstack(irg), 2);
Christian Würdig's avatar
Christian Würdig committed
70
71
72
		old->in[0] = block;
		old->in[1] = nw;
	}
73
74

	/* update irg flags */
75
	clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS
Matthias Braun's avatar
Matthias Braun committed
76
	                        | IR_GRAPH_PROPERTY_CONSISTENT_LOOPINFO);
Christian Schäfer's avatar
Christian Schäfer committed
77
}
78

Michael Beck's avatar
Michael Beck committed
79
/**
80
 * Walker: links all Phi nodes to their Blocks lists,
Matthias Braun's avatar
Matthias Braun committed
81
 *         all Proj nodes to there predecessors.
Michael Beck's avatar
Michael Beck committed
82
 */
83
84
static void collect_phiprojs_walker(ir_node *n, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
85
	(void)env;
Christian Würdig's avatar
Christian Würdig committed
86
87

	if (is_Phi(n)) {
88
		ir_node *block = get_nodes_block(n);
Michael Beck's avatar
Michael Beck committed
89
		add_Block_phi(block, n);
90
	} else if (is_Proj(n)) {
Matthias Braun's avatar
Matthias Braun committed
91
		ir_node *pred = n;
Christian Würdig's avatar
Christian Würdig committed
92
93
94
95
96
97
98
		do {
			pred = get_Proj_pred(pred);
		} while (is_Proj(pred));

		set_irn_link(n, get_irn_link(pred));
		set_irn_link(pred, n);
	}
99
100
}

101
102
void collect_phiprojs(ir_graph *irg)
{
103
	assert((ir_resources_reserved(irg) & (IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST)) ==
104
		(IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST));
105
	irg_walk_graph(irg, firm_clear_node_and_phi_links, collect_phiprojs_walker, NULL);
106
107
}

Michael Beck's avatar
Michael Beck committed
108
109
110
111
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
112
113
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
114
115
116
	/* move this node */
	set_nodes_block(node, to_bl);

Michael Beck's avatar
Michael Beck committed
117
	/* move its Projs */
118
	if (get_irn_mode(node) == mode_T) {
119
		ir_node *proj = (ir_node*)get_irn_link(node);
120
121
122
		while (proj) {
			if (get_nodes_block(proj) == from_bl)
				set_nodes_block(proj, to_bl);
123
			proj = (ir_node*)get_irn_link(proj);
124
125
		}
	}
Christian Würdig's avatar
Christian Würdig committed
126

127
128
129
	if (is_Phi(node))
		return;

Christian Würdig's avatar
Christian Würdig committed
130
	/* recursion ... */
131
	foreach_irn_in(node, i, pred) {
132
133
134
135
136
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
}

137
138
139
140
141
142
143
144
145
146
147
148
149
150
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);
	}
}

151
152
153
154
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
155
static void move_edges(ir_node *node, ir_node *from_bl, ir_node *to_bl)
156
157
158
159
160
{
	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its Projs */
161
	move_projs(node, to_bl);
162
163
164
165
166

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

170
	/* recursion ... */
171
	foreach_irn_in(node, i, pred) {
Christian Würdig's avatar
Christian Würdig committed
172
		if (get_nodes_block(pred) == from_bl)
173
			move_edges(pred, from_bl, to_bl);
Christian Würdig's avatar
Christian Würdig committed
174
	}
175
176
}

177
178
void part_block(ir_node *node)
{
Christian Würdig's avatar
Christian Würdig committed
179
180
181
182
183
	/* Turn off optimizations so that blocks are not merged again. */
	int rem_opt = get_opt_optimize();
	set_optimize(0);

	/* Transform the control flow */
Matthias Braun's avatar
Matthias Braun committed
184
185
186
187
	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));
188

189
	/* create a jump from new_block to old_block, which is now the lower one */
Matthias Braun's avatar
Matthias Braun committed
190
	ir_node *jmp = new_r_Jmp(new_block);
191
	set_irn_in(old_block, 1, &jmp);
Christian Würdig's avatar
Christian Würdig committed
192
193
194
195
196

	/* 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
197
	ir_node *phi = get_Block_phis(old_block);
Michael Beck's avatar
Michael Beck committed
198
199
	set_Block_phis(new_block, phi);
	set_Block_phis(old_block, NULL);
Christian Würdig's avatar
Christian Würdig committed
200
201
	while (phi) {
		set_nodes_block(phi, new_block);
Michael Beck's avatar
Michael Beck committed
202
		phi = get_Phi_next(phi);
Christian Würdig's avatar
Christian Würdig committed
203
204
205
	}

	set_optimize(rem_opt);
206
}
207

208
209
ir_node *part_block_edges(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
210
211
212
213
214
	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);
215
216
217
218
219

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

	/* move node and its predecessors to new_block */
220
	move_edges(node, old_block, new_block);
221
222

	/* move Phi nodes to new_block */
223
	foreach_out_edge_safe(old_block, edge) {
224
225
226
227
228
229
230
231
232
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;
		set_nodes_block(phi, new_block);
	}

	return old_block;
}

233
234
void kill_node(ir_node *node)
{
235
	ir_graph *irg = get_irn_irg(node);
Matthias Braun's avatar
Matthias Braun committed
236
237
	if (edges_activated(irg)) {
		edges_node_deleted(node);
238
	}
Matthias Braun's avatar
Matthias Braun committed
239
240
	/* noone is allowed to reference this node anymore */
	set_irn_op(node, op_Deleted);
241
}
242
243
244
245
246
247

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)) {
248
	case iro_Address:
249
		return new_rd_Address(dbg, irg, get_Address_entity(n));
250
251
	case iro_Align:
		return new_rd_Align(dbg, irg, mode, get_Align_type(n));
252
253
	case iro_Const:
		return new_rd_Const(dbg, irg, get_Const_tarval(n));
254
255
	case iro_Offset:
		return new_rd_Offset(dbg, irg, mode, get_Offset_entity(n));
256
257
	case iro_Size:
		return new_rd_Size(dbg, irg, mode, get_Size_type(n));
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
285
286
287
288
289
290
291
292
293
294
295
296
297
298
	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);
299
300
	case iro_NoMem:
		return get_irg_no_mem(irg);
301
302
303
304
305
	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);
	}
306
	case iro_Sel: {
307
308
309
		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));
310
	}
311
312
313
314
315
316
317
	case iro_Unknown:
		return new_r_Unknown(irg, mode);
	default:
		break;
	}
	panic("opcode invalid or not implemented %+F", n);
}