irgmod.c 11 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
80
81
82
		if (get_irn_op(old)->opar == oparity_dynamic) {
			DEL_ARR_F(get_irn_in(old));
		}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

304
305
306
	return old_block;
}

307
308
void kill_node(ir_node *node)
{
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);
}