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
	hook_replace(node, node);

28
29
	set_irn_in(node, arity, in);
	set_irn_op(node, op_Tuple);
30
31
32

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

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

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

	hook_replace(old, nw);

Matthias Braun's avatar
Matthias Braun committed
57
58
	/* 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
59
	if (edges_activated(irg)) {
Matthias Braun's avatar
Matthias Braun committed
60
61
		edges_reroute(old, nw);
		edges_node_deleted(old);
62
63
		/* noone is allowed to reference this node anymore */
		set_irn_op(old, op_Deleted);
64
	} else {
Christian Würdig's avatar
Christian Würdig committed
65
66
67
		/* Else, do it the old-fashioned way. */
		hook_turn_into_id(old);

Matthias Braun's avatar
Matthias Braun committed
68
69
		ir_node *block = old->in[0];
		if (block == NULL) {
Christoph Mallon's avatar
Christoph Mallon committed
70
			block = get_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
		if (is_irn_dynamic(old))
77
78
			DEL_ARR_F(get_irn_in(old));

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

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

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

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

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);
137
	} else if (is_irn_start_block_placed(node)) {
138
		collect_new_start_block_node_(node);
Christian Würdig's avatar
Christian Würdig committed
139
	}
140
141
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

300
301
302
	return old_block;
}

303
304
void kill_node(ir_node *node)
{
305
306
	hook_replace(node, NULL);

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

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