irgmod.c 6 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
/**
 * @file
 * @brief    Support for ir graph modification.
 * @author   Martin Trapp, Christian Schaefer, Goetz Lindenmaier
 * @version  $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
25
 */
Boris Boesler's avatar
added    
Boris Boesler committed
26
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
27
# include "config.h"
Boris Boesler's avatar
added    
Boris Boesler committed
28
29
#endif

Michael Beck's avatar
Michael Beck committed
30
31
32
33
34
35
36
37
38
39
40
#include "irvrfy.h"
#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"
41
#include "error.h"
Christian Schäfer's avatar
Christian Schäfer committed
42

Christian Würdig's avatar
Christian Würdig committed
43
44
45
46
47
48
/**
 * Turns a node into a "useless" Tuple.  The Tuple just forms a tuple
 * from several inputs.
 * This is useful if a node returning a tuple is removed, but the Projs
 * extracting values from the tuple are not available.
 */
49
void turn_into_tuple(ir_node *node, int arity) {
Christian Würdig's avatar
Christian Würdig committed
50
51
52
53
54
	assert(node);
	set_irn_op(node, op_Tuple);
	if (get_irn_arity(node) == arity) {
		/* keep old array */
	} else {
Michael Beck's avatar
Michael Beck committed
55
56
57
		ir_graph *irg = get_irn_irg(node);
		ir_node *block = get_nodes_block(node);
		edges_node_deleted(node, irg);
Michael Beck's avatar
Michael Beck committed
58
		/* Allocate new array, don't free old in_array, it's on the obstack. */
Michael Beck's avatar
Michael Beck committed
59
		node->in = NEW_ARR_D(ir_node *, irg->obst, arity+1);
Christian Würdig's avatar
Christian Würdig committed
60
61
		/* clear the new in array, else edge_notify tries to delete garbage */
		memset(node->in, 0, (arity+1) * sizeof(node->in[0]));
Michael Beck's avatar
Michael Beck committed
62
		/* set the block back */
Michael Beck's avatar
Michael Beck committed
63
		set_nodes_block(node, block);
Christian Würdig's avatar
Christian Würdig committed
64
	}
Christian Schäfer's avatar
Christian Schäfer committed
65
66
}

Christian Würdig's avatar
Christian Würdig committed
67
68
69
70
71
/**
 * Insert irnode `new' in place of irnode `old'
 * Since `new' may be bigger than `old' replace `old'
 * by an op_Id which is smaller than everything.
 */
72
void exchange(ir_node *old, ir_node *nw) {
Christian Würdig's avatar
Christian Würdig committed
73
74
75
76
77
78
79
80
81
82
83
	ir_graph *irg;

	assert(old && nw);
	assert(old != nw && "Exchanging node with itself is not allowed");

	irg = get_irn_irg(old);
	assert(irg == get_irn_irg(nw) && "New node must be in same irg as old node");

	hook_replace(old, nw);

	/*
84
85
86
	 * 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
87
88
89
90
91
92
93
94
	if (edges_activated(irg)) {
		/* copy all dependencies from old to new */
		add_irn_deps(nw, old);

		edges_reroute(old, nw, irg);
		edges_reroute_kind(old, nw, EDGE_KIND_DEP, irg);
		edges_node_deleted(old, irg);
		old->op = op_Bad;
95
	} else {
Christian Würdig's avatar
Christian Würdig committed
96
97
98
99
100
101
102
103
104
105
106
107
		/* Else, do it the old-fashioned way. */
		ir_node *block;

		assert(get_irn_op(old)->opar != oparity_dynamic);

		hook_turn_into_id(old);

		block = old->in[0];
		if (! block) {
			block = is_Block(nw) ? nw : get_nodes_block(nw);

			if (! block) {
108
				panic("cannot find legal block for id");
Christian Würdig's avatar
Christian Würdig committed
109
110
111
112
113
114
115
116
			}
		}

		old->op    = op_Id;
		old->in    = NEW_ARR_D (ir_node *, irg->obst, 2);
		old->in[0] = block;
		old->in[1] = nw;
	}
Christian Schäfer's avatar
Christian Schäfer committed
117
}
118

119
120
121
/*--------------------------------------------------------------------*/
/*  Functionality for collect_phis                                    */
/*--------------------------------------------------------------------*/
122

Michael Beck's avatar
Michael Beck committed
123
124
125
126
127
/**
 * Walker: links all Phi nodes to their Blocks and
 *         all Proj nodes to there predecessors
 */
static void collect(ir_node *n, void *env) {
Christian Würdig's avatar
Christian Würdig committed
128
	ir_node *pred;
129
	(void) env;
Christian Würdig's avatar
Christian Würdig committed
130
131
132
133

	if (is_Phi(n)) {
		set_irn_link(n, get_irn_link(get_nodes_block(n)));
		set_irn_link(get_nodes_block(n), n);
134
	} else if (is_Proj(n)) {
Christian Würdig's avatar
Christian Würdig committed
135
136
137
138
139
140
141
142
		pred = n;
		do {
			pred = get_Proj_pred(pred);
		} while (is_Proj(pred));

		set_irn_link(n, get_irn_link(pred));
		set_irn_link(pred, n);
	}
143
144
145
}

void collect_phiprojs(ir_graph *irg) {
Christian Würdig's avatar
Christian Würdig committed
146
	irg_walk_graph(irg, firm_clear_link, collect, NULL);
147
148
149
}


150
151
152
/*--------------------------------------------------------------------*/
/*  Functionality for part_block                                      */
/*--------------------------------------------------------------------*/
153

Michael Beck's avatar
Michael Beck committed
154
155
156
157
/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
Christian Würdig's avatar
Christian Würdig committed
158
159
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl) {
	int i, arity;
160
161
162
163
164
165
166
167
168
169
170
171
172
173
	ir_node *proj, *pred;

	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its projs */
	if (get_irn_mode(node) == mode_T) {
		proj = get_irn_link(node);
		while (proj) {
			if (get_nodes_block(proj) == from_bl)
				set_nodes_block(proj, to_bl);
			proj = get_irn_link(proj);
		}
	}
Christian Würdig's avatar
Christian Würdig committed
174
175
176
177
178
179
180
181
182
183

	/* recursion ... */
	if (get_irn_op(node) == op_Phi) return;

	arity = get_irn_arity(node);
	for (i = 0; i < arity; i++) {
		pred = get_irn_n(node, i);
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
	}
184
185
186
}

void part_block(ir_node *node) {
Christian Würdig's avatar
Christian Würdig committed
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
	ir_node *new_block;
	ir_node *old_block;
	ir_node *phi;

	/* Turn off optimizations so that blocks are not merged again. */
	int rem_opt = get_opt_optimize();
	set_optimize(0);

	/* Transform the control flow */
	old_block = get_nodes_block(node);
	new_block = new_Block(get_Block_n_cfgpreds(old_block),
		get_Block_cfgpred_arr(old_block));
	set_irg_current_block(current_ir_graph, new_block);
	{
		ir_node *jmp = new_Jmp();
		set_irn_in(old_block, 1, &jmp);
		irn_vrfy_irg(old_block, current_ir_graph);
	}

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

	/* move Phi nodes to new_block */
	phi = get_irn_link(old_block);
	set_irn_link(new_block, phi);
	set_irn_link(old_block, NULL);
	while (phi) {
		set_nodes_block(phi, new_block);
		phi = get_irn_link(phi);
	}

	set_optimize(rem_opt);
219
}
220
221
222
223
224
225
226
227
228
229
230
231

/* kill a node by setting its predecessors to Bad and finally exchange the node by Bad itself. */
void kill_node(ir_node *node) {
	ir_graph *irg = get_irn_irg(node);
	ir_node *bad = get_irg_bad(irg);
	int i;

	for (i = get_irn_arity(node) - 1; i >= -1; --i) {
		set_irn_n(node, i, bad);
	}
	exchange(node, bad);
}