irgmod.c 10.8 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
static void collect_new_start_block_node_(ir_node *node)
{
93
94
95
96
97
	/* special handling for the Start node: it needs to be at the beginning
	 * of the list of Projs, and in the start_block node list. Do not put it
	 * into the start block node list. */
	if (is_Start(node))
		return;
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
	/* 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)
{
	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
119
/**
120
 * Walker: links all Phi nodes to their Blocks lists,
121
 *         all Proj nodes to their predecessors.
Michael Beck's avatar
Michael Beck committed
122
 */
123
static void collect_nodes(ir_node *node, void *env)
124
{
Matthias Braun's avatar
Matthias Braun committed
125
	(void)env;
Christian Würdig's avatar
Christian Würdig committed
126

127
128
129
130
	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
131
132
133
134
		do {
			pred = get_Proj_pred(pred);
		} while (is_Proj(pred));

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

143
144
145
146
147
148
149
150
151
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)
152
{
153
	assert((ir_resources_reserved(irg) & (IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST)) ==
154
		(IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST));
155
156
157
	ir_node *end = get_irg_end(irg);
	set_irn_link(end, end);
	irg_walk_anchors(irg, init_links, collect_nodes, NULL);
158
159
}

160
161
162
static void move_node(ir_node *node, ir_node *to_bl)
{
	set_nodes_block(node, to_bl);
163
	/* if no mode_T node, do not move Projs. Note that BadT shouldn't have
164
165
166
167
168
169
170
171
172
173
174
	 * any Projs as well and is part of the start_block list and therefore
	 * doesn't have a valid Proj list */
	if (get_irn_mode(node) != mode_T || is_Bad(node))
		return;

	for (ir_node *proj = (ir_node*)get_irn_link(node);
	     proj != NULL; proj = (ir_node*)get_irn_link(proj)) {
		set_nodes_block(proj, to_bl);
	}
}

Michael Beck's avatar
Michael Beck committed
175
176
177
178
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
179
180
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
181
	move_node(node, to_bl);
Christian Würdig's avatar
Christian Würdig committed
182

183
184
185
	if (is_Phi(node))
		return;

Christian Würdig's avatar
Christian Würdig committed
186
	/* recursion ... */
187
	foreach_irn_in(node, i, pred) {
188
189
190
191
192
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
}

193
static void move_node_edges(ir_node *node, ir_node *to_bl)
194
{
195
	set_nodes_block(node, to_bl);
196
197
198
199
200
201
202
	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;
203
		move_node_edges(proj, to_bl);
204
205
206
	}
}

207
208
209
210
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
211
static void move_edges(ir_node *node, ir_node *from_bl, ir_node *to_bl)
212
{
213
	move_node_edges(node, to_bl);
214
215
216

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

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

228
229
230
231
232
233
234
235
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)) {
236
		move_node(cnst, new_block);
237
	}
238
239
	ir_node *start = get_irg_start(irg);
	move_node(start, new_block);
240
241
}

242
243
void part_block(ir_node *node)
{
Christian Würdig's avatar
Christian Würdig committed
244
	/* Turn off optimizations so that blocks are not merged again. */
Matthias Braun's avatar
Matthias Braun committed
245
	int rem_opt = get_optimize();
Christian Würdig's avatar
Christian Würdig committed
246
247
248
	set_optimize(0);

	/* Transform the control flow */
Matthias Braun's avatar
Matthias Braun committed
249
250
251
252
	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));
253

254
	/* create a jump from new_block to old_block, which is now the lower one */
Matthias Braun's avatar
Matthias Braun committed
255
	ir_node *jmp = new_r_Jmp(new_block);
256
	set_irn_in(old_block, 1, &jmp);
Christian Würdig's avatar
Christian Würdig committed
257
258
259
260
261

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

270
271
272
	if (old_block == get_irg_start_block(irg))
		update_startblock(old_block, new_block);

Christian Würdig's avatar
Christian Würdig committed
273
	set_optimize(rem_opt);
274
}
275

276
277
ir_node *part_block_edges(ir_node *node)
{
Matthias Braun's avatar
Matthias Braun committed
278
279
280
281
282
	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);
283
284
285
286
287

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

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

290
	/* move Phi nodes and constants to new_block */
291
	foreach_out_edge_safe(old_block, edge) {
292
		ir_node *blnode = get_edge_src_irn(edge);
yb9976's avatar
yb9976 committed
293
		if (!is_Phi(blnode) && !is_irn_start_block_placed(blnode))
294
			continue;
295
		move_node_edges(blnode, new_block);
296
297
	}

298
299
300
	if (old_block == get_irg_start_block(irg))
		set_irg_start_block(irg, new_block);

301
302
303
	return old_block;
}

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

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)) {
319
	case iro_Address:
320
		return new_rd_Address(dbg, irg, get_Address_entity(n));
321
322
	case iro_Align:
		return new_rd_Align(dbg, irg, mode, get_Align_type(n));
323
324
	case iro_Const:
		return new_rd_Const(dbg, irg, get_Const_tarval(n));
325
326
	case iro_Offset:
		return new_rd_Offset(dbg, irg, mode, get_Offset_entity(n));
327
328
	case iro_Size:
		return new_rd_Size(dbg, irg, mode, get_Size_type(n));
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
365
366
367
368
369
	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);
370
371
	case iro_NoMem:
		return get_irg_no_mem(irg);
372
373
374
375
376
	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);
	}
377
	case iro_Sel: {
378
379
380
		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));
381
	}
382
383
384
385
386
387
388
	case iro_Unknown:
		return new_r_Unknown(irg, mode);
	default:
		break;
	}
	panic("opcode invalid or not implemented %+F", n);
}