irgmod.c 10.5 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
#ifndef NDEBUG
38
	/* When replacing a PhiM node, it must not be held by a keep-alive edge.
39
40
	 * => 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

91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
static void collect_new_start_block_node_(ir_node *node)
{
	/* misuse link field of End node to collect all start-block nodes */
	ir_node *end = get_irg_end(get_irn_irg(node));
	set_irn_link(node, get_irn_link(end));
	set_irn_link(end, node);
}

void collect_new_start_block_node(ir_node *node)
{
	if (is_Start(node))
		return;
	assert(is_irn_start_block_placed(node));
	/* alreayd in list? */
	if (get_irn_link(node) != NULL)
		return;
	collect_new_start_block_node_(node);
}

void collect_new_phi_node(ir_node *node)
{
	ir_node *block = get_nodes_block(node);
	add_Block_phi(block, node);
}

Michael Beck's avatar
Michael Beck committed
116
/**
117
 * Walker: links all Phi nodes to their Blocks lists,
Matthias Braun's avatar
Matthias Braun committed
118
 *         all Proj nodes to there predecessors.
Michael Beck's avatar
Michael Beck committed
119
 */
120
static void collect_nodes(ir_node *node, void *env)
121
{
Matthias Braun's avatar
Matthias Braun committed
122
	(void)env;
Christian Würdig's avatar
Christian Würdig committed
123

124
125
126
127
	if (is_Phi(node)) {
		collect_new_phi_node(node);
	} else if (is_Proj(node)) {
		ir_node *pred = node;
Christian Würdig's avatar
Christian Würdig committed
128
129
130
131
		do {
			pred = get_Proj_pred(pred);
		} while (is_Proj(pred));

132
133
134
135
136
		assert(!is_irn_start_block_placed(pred) || is_Start(pred));
		set_irn_link(node, get_irn_link(pred));
		set_irn_link(pred, node);
	} else if (is_irn_start_block_placed(node) && !is_Start(node)) {
		collect_new_start_block_node_(node);
Christian Würdig's avatar
Christian Würdig committed
137
	}
138
139
}

140
141
142
143
144
145
146
147
148
static void init_links(ir_node *node, void *data)
{
	(void)data;
	if (is_End(node))
		return;
	firm_clear_node_and_phi_links(node, data);
}

void collect_phiprojs_and_start_block_nodes(ir_graph *irg)
149
{
150
	assert((ir_resources_reserved(irg) & (IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST)) ==
151
		(IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST));
152
153
154
	ir_node *end = get_irg_end(irg);
	set_irn_link(end, end);
	irg_walk_anchors(irg, init_links, collect_nodes, NULL);
155
156
}

Michael Beck's avatar
Michael Beck committed
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
162
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
163
164
165
	/* move this node */
	set_nodes_block(node, to_bl);

Michael Beck's avatar
Michael Beck committed
166
	/* move its Projs */
167
	if (get_irn_mode(node) == mode_T) {
168
169
		for (ir_node *proj = (ir_node*)get_irn_link(node);
		     proj != NULL; proj = (ir_node*)get_irn_link(proj)) {
170
171
172
173
			if (get_nodes_block(proj) == from_bl)
				set_nodes_block(proj, to_bl);
		}
	}
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
	foreach_irn_in(node, i, pred) {
180
181
182
183
184
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
}

185
186
187
188
189
190
191
192
193
194
195
196
197
198
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);
	}
}

199
200
201
202
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
203
static void move_edges(ir_node *node, ir_node *from_bl, ir_node *to_bl)
204
205
206
207
208
{
	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its Projs */
209
	move_projs(node, to_bl);
210
211
212
213
214

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

218
	/* recursion ... */
219
	foreach_irn_in(node, i, pred) {
Christian Würdig's avatar
Christian Würdig committed
220
		if (get_nodes_block(pred) == from_bl)
221
			move_edges(pred, from_bl, to_bl);
Christian Würdig's avatar
Christian Würdig committed
222
	}
223
224
}

225
226
227
228
229
230
231
232
233
234
235
236
static void update_startblock(ir_node *old_block, ir_node *new_block)
{
	ir_graph *irg = get_irn_irg(old_block);
	set_irg_start_block(irg, new_block);
	/* move constants around */
	ir_node *end = get_irg_end(irg);
	for (ir_node *cnst = get_irn_link(end); cnst != end;
	     cnst = (ir_node*)get_irn_link(cnst)) {
		set_nodes_block(cnst, new_block);
	}
}

237
238
void part_block(ir_node *node)
{
Christian Würdig's avatar
Christian Würdig committed
239
	/* Turn off optimizations so that blocks are not merged again. */
Matthias Braun's avatar
Matthias Braun committed
240
	int rem_opt = get_optimize();
Christian Würdig's avatar
Christian Würdig committed
241
242
243
	set_optimize(0);

	/* Transform the control flow */
Matthias Braun's avatar
Matthias Braun committed
244
245
246
247
	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));
248

249
	/* create a jump from new_block to old_block, which is now the lower one */
Matthias Braun's avatar
Matthias Braun committed
250
	ir_node *jmp = new_r_Jmp(new_block);
251
	set_irn_in(old_block, 1, &jmp);
Christian Würdig's avatar
Christian Würdig committed
252
253
254
255
256

	/* 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
257
	ir_node *phi = get_Block_phis(old_block);
Michael Beck's avatar
Michael Beck committed
258
259
	set_Block_phis(new_block, phi);
	set_Block_phis(old_block, NULL);
Christian Würdig's avatar
Christian Würdig committed
260
261
	while (phi) {
		set_nodes_block(phi, new_block);
Michael Beck's avatar
Michael Beck committed
262
		phi = get_Phi_next(phi);
Christian Würdig's avatar
Christian Würdig committed
263
264
	}

265
266
267
	if (old_block == get_irg_start_block(irg))
		update_startblock(old_block, new_block);

Christian Würdig's avatar
Christian Würdig committed
268
	set_optimize(rem_opt);
269
}
270

271
272
ir_node *part_block_edges(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
273
274
275
276
277
	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);
278
279
280
281
282

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

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

285
	/* move Phi nodes and constants to new_block */
286
	foreach_out_edge_safe(old_block, edge) {
287
288
		ir_node *blnode = get_edge_src_irn(edge);
		if (!is_Phi(blnode) && !is_irn_start_block_placed(blnode))
289
			continue;
290
		set_nodes_block(blnode, new_block);
291
292
	}

293
294
295
	if (old_block == get_irg_start_block(irg))
		set_irg_start_block(irg, new_block);

296
297
298
	return old_block;
}

299
300
void kill_node(ir_node *node)
{
301
	ir_graph *irg = get_irn_irg(node);
Matthias Braun's avatar
Matthias Braun committed
302
303
	if (edges_activated(irg)) {
		edges_node_deleted(node);
304
	}
Matthias Braun's avatar
Matthias Braun committed
305
306
	/* noone is allowed to reference this node anymore */
	set_irn_op(node, op_Deleted);
307
}
308
309
310
311
312
313

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)) {
314
	case iro_Address:
315
		return new_rd_Address(dbg, irg, get_Address_entity(n));
316
317
	case iro_Align:
		return new_rd_Align(dbg, irg, mode, get_Align_type(n));
318
319
	case iro_Const:
		return new_rd_Const(dbg, irg, get_Const_tarval(n));
320
321
	case iro_Offset:
		return new_rd_Offset(dbg, irg, mode, get_Offset_entity(n));
322
323
	case iro_Size:
		return new_rd_Size(dbg, irg, mode, get_Size_type(n));
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
	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);
365
366
	case iro_NoMem:
		return get_irg_no_mem(irg);
367
368
369
370
371
	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);
	}
372
	case iro_Sel: {
373
374
375
		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));
376
	}
377
378
379
380
381
382
383
	case iro_Unknown:
		return new_r_Unknown(irg, mode);
	default:
		break;
	}
	panic("opcode invalid or not implemented %+F", n);
}