condeval.c 6.1 KB
Newer Older
1
2
3
4
5
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <assert.h>
6
#include "array.h"
Christoph Mallon's avatar
Christoph Mallon committed
7
#include "condeval.h"
8
9
#include "debug.h"
#include "ircons.h"
Christoph Mallon's avatar
Christoph Mallon committed
10
11
#include "irgmod.h"
#include "irgopt.h"
12
13
#include "irgwalk.h"
#include "irnode.h"
14
#include "iredges.h"
15
16
17
18
#include "tv.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg);

Christoph Mallon's avatar
Christoph Mallon committed
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/**
 * Add the new predecessor x to node node, which is either a Block or a Phi
 */
static void add_pred(ir_node* node, ir_node* x)
{
	ir_node** ins;
	int n;
	int i;

	assert(is_Block(node) || is_Phi(node));

	n = get_irn_arity(node);
	NEW_ARR_A(ir_node*, ins, n + 1);
	for (i = 0; i < n; i++) ins[i] = get_irn_n(node, i);
	ins[n] = x;
	set_irn_in(node, n + 1, ins);
}


/**
 * Remove predecessor j from node, which is either a Block or a Phi
 * returns true if only one predecessor is left
 */
static int remove_pred(ir_node* node, int j)
{
	int n;

	assert(is_Block(node) || is_Phi(node));

	n = get_irn_arity(node);
	if (n == 2) {
		ir_node* pred = get_irn_n(node, 1 - j);

		if (is_Block(node)) pred = get_nodes_block(pred);
		exchange(node, pred);
		return 1;
	} else {
		ir_node** ins;
		int i;

		NEW_ARR_A(ir_node*, ins, n - 1);
		for (i = 0; i < j; i++) ins[i]     = get_irn_n(node, i);
		for (i++;   i < n; i++) ins[i - 1] = get_irn_n(node, i);
		set_irn_in(node, n - 1, ins);
		return 0;
	}
}


static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode)
{
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
	int i;
	int n_cfgpreds;
	ir_graph *irg;
	ir_node *phi;
	ir_node **in;

	assert(!is_Bad(block));

	// already processed this block?
	if(irn_visited(block)) {
		ir_node *value = (ir_node*) get_irn_link(block);
		return value;
	}

	// blocks with only 1 pred need no phi
	n_cfgpreds = get_Block_n_cfgpreds(block);
	if(n_cfgpreds == 1) {
		ir_node *pred_block = get_Block_cfgpred_block(block, 0);
		ir_node *value = search_def_and_create_phis(pred_block, mode);

		set_irn_link(block, value);
		mark_irn_visited(block);
		return value;
	}

	// create a new phi
	in = alloca(sizeof(in[0]) * n_cfgpreds);
	for(i = 0; i < n_cfgpreds; ++i)
		in[i] = new_Unknown(mode);

	irg = get_irn_irg(block);
	phi = new_r_Phi(irg, block, n_cfgpreds, in, mode);
	set_irn_link(block, phi);
	mark_irn_visited(block);

	// set phi preds
	for(i = 0; i < n_cfgpreds; ++i) {
		ir_node *pred_block = get_Block_cfgpred_block(block, i);
		ir_node *pred_val;

		pred_val = search_def_and_create_phis(pred_block, mode);
		set_irn_n(phi, i, pred_val);
	}

	return phi;
}

Christoph Mallon's avatar
Christoph Mallon committed
118

119
120
121
122
/**
 * Given a set of values this function constructs SSA-form for all users of the
 * values (the user are determined through the out-edges of the values).
 */
Christoph Mallon's avatar
Christoph Mallon committed
123
124
static void construct_ssa(ir_node * const *vals, int n_vals)
{
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
	int i;
	ir_graph *irg;
	ir_mode *mode;

	assert(n_vals > 0);

	irg = get_irn_irg(vals[0]);
	inc_irg_visited(irg);

	mode = get_irn_mode(vals[0]);
	for(i = 0; i < n_vals; ++i) {
		ir_node *value = vals[i];
		ir_node *value_block = get_nodes_block(value);

		assert(get_irn_mode(value) == mode);

		set_irn_link(value_block, value);
		mark_irn_visited(value_block);
	}

	for(i = 0; i < n_vals; ++i) {
		const ir_edge_t *edge;
		ir_node *value = vals[i];

		foreach_out_edge(value, edge) {
			ir_node *user = get_edge_src_irn(edge);
			ir_node *user_block = get_nodes_block(user);
			ir_node *newval;

			newval = search_def_and_create_phis(user_block, mode);
			set_irn_n(user, get_edge_src_pos(edge), newval);
		}
	}
}

Christoph Mallon's avatar
Christoph Mallon committed
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
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

#if 0
/**
 * Compare node compares two Const nodes
 * Returns true if this direction is taken
 */
static int handle_const_const(ir_node* cnst_left, cnst_right, pn_Cmp pnc)
{
	// TODO
}
#endif


/**
 *
 */
static void handle_phi_const(ir_node* block, ir_node* cond_block, ir_node* phi, ir_node* cnst, pn_Cmp pnc)
{
	tarval* tv_cnst;
	int n_phi;
	int j;

	tv_cnst = get_Const_tarval(cnst);
	n_phi = get_Phi_n_preds(phi);
	for (j = 0; j < n_phi; j++) {
		ir_node* pred;
		tarval* tv_phi;
		pn_Cmp cmp_val;

		pred = get_Phi_pred(phi, j);
		// TODO handle Phi cascades
		if (!is_Const(pred)) continue;

		tv_phi  = get_Const_tarval(pred);

		cmp_val = tarval_cmp(tv_phi, tv_cnst);
		if (cmp_val == pn_Cmp_False) continue;
		if ((cmp_val & pnc) != cmp_val) continue;

		DB((
			dbg, LEVEL_1,
			"> Found condition evaluation candidate %+F->%+F predecessor %d\n",
			block, cond_block, j
		));

#if 0 // TODO repair data flow and dominance
		add_pred(block, get_Block_cfgpred(cond_block, j));

		remove_pred(phi, j);
		if (remove_pred(cond_block, j)) break;
#endif
	}
}


215
216
217
/**
 * Block-walker:
 */
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
static void cond_eval(ir_node* block, void* env)
{
	int n_block = get_Block_n_cfgpreds(block);
	int i;

	for (i = 0; i < n_block; i++) {
		ir_node* pred;
		ir_node* projx;
		ir_node* cond;
		ir_node* cmp;
		ir_node* left;
		ir_node* right;
		ir_node* cond_block;
		pn_Cmp pnc;

		pred = get_Block_cfgpred(block, i);
		if (!is_Proj(pred)) continue;
		projx = pred;

		pred = get_Proj_pred(projx);
		if (!is_Cond(pred)) continue;
		cond = pred;

		pred = get_Cond_selector(cond);
		assert(is_Proj(pred));
		// TODO handle switches
		if (get_irn_mode(pred) != mode_b) continue;
		pnc = get_Proj_proj(pred);

		cmp = get_Proj_pred(pred);
		assert(is_Cmp(cmp));

		left  = get_Cmp_left(cmp);
		right = get_Cmp_right(cmp);
Christoph Mallon's avatar
Christoph Mallon committed
252
		assert(get_irn_mode(left) == get_irn_mode(right));
253

254
		if (get_Proj_proj(projx) == 0) {
Christoph Mallon's avatar
Christoph Mallon committed
255
			pnc = get_negated_pnc(pnc, get_irn_mode(left));
256
		}
257

Christoph Mallon's avatar
Christoph Mallon committed
258
259
260
261
262
263
264
265
#if 0 // TODO implement
		if (is_Const(left) && is_Const(right)) {
			if (!handle_const_const()) {
				n_block--;
				i--;
			}
			continue;
		}
266
#endif
Christoph Mallon's avatar
Christoph Mallon committed
267
268
269
270
271
272
273
274
275
276
277
278
279
280
		cond_block = get_nodes_block(cond);
		if (is_Phi(left) && is_Const(right)) {
			if (get_nodes_block(left) != cond_block) continue;
			handle_phi_const(block, cond_block, left, right, pnc);
			continue;
		}
		if (is_Const(left) && is_Phi(right)) {
			if (get_nodes_block(right) != cond_block) continue;
			handle_phi_const(block, cond_block, right, left, get_inversed_pnc(pnc));
			continue;
		}
#if 0
		if (is_Phi(left) && is_Phi(right)) {
			// TODO implement
281
		}
Christoph Mallon's avatar
Christoph Mallon committed
282
#endif
283
284
285
286
287
288
289
	}
}


void opt_cond_eval(ir_graph* irg)
{
	FIRM_DBG_REGISTER(dbg, "firm.opt.condeval");
Christoph Mallon's avatar
Christoph Mallon committed
290
	firm_dbg_set_mask(dbg, SET_LEVEL_5);
291
292
293

	DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg));

Christoph Mallon's avatar
Christoph Mallon committed
294
295
	remove_critical_cf_edges(irg);

296
297
	irg_block_walk_graph(irg, NULL, cond_eval, NULL);
}