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) {
Christoph Mallon's avatar
Christoph Mallon committed
72
			block = get_block(nw);
Matthias Braun's avatar
Matthias Braun committed
73
			if (block == NULL) {
74
				panic("cannot find legal block for id");
Christian Würdig's avatar
Christian Würdig committed
75
76
77
			}
		}

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

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

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

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

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

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

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

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

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

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

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

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

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

222
	/* recursion ... */
223
	foreach_irn_in(node, i, pred) {
Christian Würdig's avatar
Christian Würdig committed
224
		if (get_nodes_block(pred) == from_bl)
225
			move_edges(pred, from_bl, to_bl);
Christian Würdig's avatar
Christian Würdig committed
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)) {
237
		move_node(cnst, new_block);
238
	}
239
240
	ir_node *start = get_irg_start(irg);
	move_node(start, new_block);
241
242
}

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

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

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

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

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

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

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

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

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

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

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

302
303
304
	return old_block;
}

305
306
void kill_node(ir_node *node)
{
307
308
	hook_replace(node, NULL);

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

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