irgmod.c 10.9 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);
28
29
30

	/* update irg flags */
	clear_irg_properties(get_irn_irg(node), IR_GRAPH_PROPERTY_NO_TUPLES);
Christian Schäfer's avatar
Christian Schäfer committed
31
32
}

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

Matthias Braun's avatar
Matthias Braun committed
38
39
	ir_graph *irg = get_irn_irg(old);
	assert(irg == get_irn_irg(nw));
40
#ifndef NDEBUG
41
	/* When replacing a PhiM node, it must not be held by a keep-alive edge.
42
43
	 * => Keep-alive edges are not normal users and should not move along when
	 * exchanging. */
44
45
	if (is_Phi(old) && get_Phi_loop(old) && !(is_Phi(nw) && get_Phi_loop(nw))
	    && !is_Bad(nw)) {
46
47
48
49
50
51
		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
52
53
54

	hook_replace(old, nw);

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

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

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

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

79
		if (is_irn_dynamic(old))
80
81
			DEL_ARR_F(get_irn_in(old));

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

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

93
94
static void collect_new_start_block_node_(ir_node *node)
{
95
96
97
98
99
	/* 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;
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
	/* 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
121
/**
122
 * Walker: links all Phi nodes to their Blocks lists,
123
 *         all Proj nodes to their predecessors.
Michael Beck's avatar
Michael Beck committed
124
 */
125
static void collect_nodes(ir_node *node, void *env)
126
{
Matthias Braun's avatar
Matthias Braun committed
127
	(void)env;
Christian Würdig's avatar
Christian Würdig committed
128

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

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

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

162
163
164
static void move_node(ir_node *node, ir_node *to_bl)
{
	set_nodes_block(node, to_bl);
165
	/* if no mode_T node, do not move Projs. Note that BadT shouldn't have
166
167
168
169
170
171
172
173
174
175
176
	 * 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
177
178
179
180
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
181
182
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
183
	move_node(node, to_bl);
Christian Würdig's avatar
Christian Würdig committed
184

185
186
187
	if (is_Phi(node))
		return;

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

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

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

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

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

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

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

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

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

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

272
273
274
	if (old_block == get_irg_start_block(irg))
		update_startblock(old_block, new_block);

Christian Würdig's avatar
Christian Würdig committed
275
	set_optimize(rem_opt);
276
}
277

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

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

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

292
	/* move Phi nodes and constants to new_block */
293
	foreach_out_edge_safe(old_block, edge) {
294
		ir_node *blnode = get_edge_src_irn(edge);
yb9976's avatar
yb9976 committed
295
296
297
		ir_node *skip   = skip_Proj(skip_Proj(blnode));
		if (is_Phi(skip) || is_irn_start_block_placed(skip))
			set_nodes_block(blnode, new_block);
298
299
	}

300
301
302
	if (old_block == get_irg_start_block(irg))
		set_irg_start_block(irg, new_block);

303
304
305
	return old_block;
}

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

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