convopt.c 8.06 KB
Newer Older
Matthias Braun's avatar
Matthias Braun committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 *
 * 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.
 */

/**
 * @file
 * @brief   conv node optimisation
 * @author  Matthias Braun, Christoph Mallon
24
 * @version $Id$
Matthias Braun's avatar
Matthias Braun committed
25
26
27
28
29
30
31
32
33
34
 *
 * Try to minimize the number of conv nodes by changing modes of operations.
 * The typical example is the following structure:
 *    (some node mode_Hs)
 *            |                                       (some node_Hs)
 *         Conv Is                                          |
 *            |                                          Add Hs
 *          Add Is            gets transformed to           |
 *            |
 *         Conv Hs
Matthias Braun's avatar
Matthias Braun committed
35
36
37
 *
 * TODO: * try to optimize cmp modes
 *       * decide when it is useful to move the convs through phis
Matthias Braun's avatar
Matthias Braun committed
38
39
40
 */
#include "config.h"

41
42
#include "iroptimize.h"

Matthias Braun's avatar
Matthias Braun committed
43
#include <assert.h>
44
#include <stdbool.h>
Matthias Braun's avatar
Matthias Braun committed
45
46
47
#include "debug.h"
#include "ircons.h"
#include "irgmod.h"
48
#include "irgopt.h"
Matthias Braun's avatar
Matthias Braun committed
49
50
51
52
#include "irnode_t.h"
#include "iredges_t.h"
#include "irgwalk.h"
#include "irprintf.h"
53
#include "irpass_t.h"
54
55
#include "tv.h"
#include "vrp.h"
Matthias Braun's avatar
Matthias Braun committed
56
57
58

DEBUG_ONLY(static firm_dbg_module_t *dbg);

59
static inline int imin(int a, int b) { return a < b ? a : b; }
60

61
static bool is_optimizable_node(const ir_node *node)
Matthias Braun's avatar
Matthias Braun committed
62
{
63
	switch (get_irn_opcode(node)) {
64
65
66
67
68
69
70
71
72
73
74
75
76
	case iro_Add:
	case iro_And:
	case iro_Eor:
	case iro_Minus:
	case iro_Mul:
	case iro_Not:
	case iro_Or:
	case iro_Phi:
	case iro_Shl:
	case iro_Sub:
		return true;
	default:
		return false;
77
	}
78
79
80
81
82
}

static tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
{
	return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
Matthias Braun's avatar
Matthias Braun committed
83
84
}

85
static int is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
86
87
88
89
{
	return
		mode_is_int(src_mode) &&
		mode_is_int(dest_mode) &&
90
		get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
91
92
}

93
static int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
Matthias Braun's avatar
Matthias Braun committed
94
95
{
	ir_mode *mode = get_irn_mode(node);
96
97
98
	size_t arity;
	size_t i;
	int costs;
Matthias Braun's avatar
Matthias Braun committed
99

100
	if (mode == dest_mode)
Matthias Braun's avatar
Matthias Braun committed
101
102
		return 0;

103
104
105
106
107
	if (is_Const(node)) {
		/* TODO tarval module is incomplete and can't convert floats to ints */
		return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
	}

108
	if (is_Conv(node) &&
109
			is_downconv(mode, dest_mode) &&
110
111
112
113
			get_irn_mode(get_Conv_op(node)) == dest_mode) {
		return -1;
	}

114
	if (get_irn_n_edges(node) > 1) {
Matthias Braun's avatar
Matthias Braun committed
115
116
117
118
		DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
		return 1;
	}

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#if 0 // TODO
	/* Take the minimum of the conversion costs for Phi predecessors as only one
	 * branch is actually executed at a time */
	if (is_Phi(node)) {
		size_t i;
		size_t arity = get_Phi_n_preds(node);
		int costs;

		costs = get_conv_costs(get_Phi_pred(node, 0), dest_mode);
		for (i = 1; i < arity; ++i) {
			ir_node *pred = get_Phi_pred(node, i);
			int c = get_conv_costs(pred, dest_mode);
			if (c < costs) costs = c;
		}

		return costs;
	}
#endif

138
139
140
141
142
	if (!is_downconv(mode, dest_mode)) {
		return 1;
	}

	if (is_Conv(node)) {
yb9976's avatar
yb9976 committed
143
144
145
146
147
148
		ir_node *pred      = get_Conv_op(node);
		ir_mode *pred_mode = get_irn_mode(pred);

		if (!values_in_mode(dest_mode, pred_mode)) {
			return 1;
		}
149
150
151
152
		return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
	}

	if (!is_optimizable_node(node)) {
153
154
		return 1;
	}
Matthias Braun's avatar
Matthias Braun committed
155

156
	costs = 0;
157
158
	// The shift count does not participate in the conv optimisation
	arity = is_Shl(node) ? 1 : get_irn_arity(node);
159
160
	for (i = 0; i < arity; ++i) {
		ir_node *pred = get_irn_n(node, i);
161
		costs += imin(get_conv_costs(pred, dest_mode), 1);
Matthias Braun's avatar
Matthias Braun committed
162
163
	}

164
165
166
167
168
169
	return costs;
}

static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
{
	ir_node *block = get_nodes_block(node);
170
	ir_node *conv = new_r_Conv(block, node, dest_mode);
171
	return conv;
Matthias Braun's avatar
Matthias Braun committed
172
173
}

174
static ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
Matthias Braun's avatar
Matthias Braun committed
175
{
176
177
	ir_mode  *mode = get_irn_mode(node);
	size_t    arity;
178
	size_t    conv_arity;
179
180
	size_t    i;
	ir_node  *new_node;
181
182
	ir_graph *irg;
	ir_node **ins;
Matthias Braun's avatar
Matthias Braun committed
183

184
	if (mode == dest_mode)
Matthias Braun's avatar
Matthias Braun committed
185
186
187
		return node;

	if (is_Const(node)) {
188
189
190
191
192
		/* TODO tarval module is incomplete and can't convert floats to ints */
		tarval *tv = conv_const_tv(node, dest_mode);
		if (tv == tarval_bad) {
			return place_conv(node, dest_mode);
		} else {
193
			return new_Const(tv);
194
195
196
		}
	}

197
	if (is_Conv(node) &&
198
			is_downconv(mode, dest_mode) &&
199
200
201
202
			get_irn_mode(get_Conv_op(node)) == dest_mode) {
		return get_Conv_op(node);
	}

203
204
	if (get_irn_n_edges(node) > 1) {
		return place_conv(node, dest_mode);
Matthias Braun's avatar
Matthias Braun committed
205
206
	}

207
208
209
210
211
	if (!is_downconv(mode, dest_mode)) {
		return place_conv(node, dest_mode);
	}

	if (is_Conv(node)) {
yb9976's avatar
yb9976 committed
212
213
214
215
216
217
		ir_node *pred      = get_Conv_op(node);
		ir_mode *pred_mode = get_irn_mode(pred);

		if (!values_in_mode(dest_mode, pred_mode)) {
			return place_conv(node, dest_mode);
		}
Christoph Mallon's avatar
Christoph Mallon committed
218
219
220
		return conv_transform(get_Conv_op(node), dest_mode);
	}

221
	if (!is_optimizable_node(node)) {
222
		return place_conv(node, dest_mode);
Matthias Braun's avatar
Matthias Braun committed
223
224
	}

225
226
227
228
	// We want to create a new node with the right mode
	arity = get_irn_arity(node);
	irg = get_irn_irg(node);
	ins = ALLOCAN(ir_node *, arity);
229

230
	// The shift count does not participate in the conv optimisation
231
232
233
	conv_arity = is_Shl(node) ? 1 : arity;
	for (i = 0; i < conv_arity; i++) {
		ir_node *pred = get_irn_n(node, i);
234
235
236
237
238
239
		ir_node *transformed;
		if (get_conv_costs(pred, dest_mode) > 0) {
			transformed = place_conv(pred, dest_mode);
		} else {
			transformed = conv_transform(pred, dest_mode);
		}
240
241
242
243
244
		ins[i] = transformed;
	}

	for (i = conv_arity; i < arity; i++) {
		ins[i] = get_irn_n(node, i);
Matthias Braun's avatar
Matthias Braun committed
245
	}
246

247
248
249
250
251
252
253
254
255
	new_node = new_ir_node(get_irn_dbg_info(node),
				irg,
				get_nodes_block(node),
				get_irn_op(node),
				dest_mode,
				arity,
				ins);
	copy_node_attr(irg, node, new_node);

256
	return new_node;
Matthias Braun's avatar
Matthias Braun committed
257
258
}

259
/* TODO, backends (at least ia32) can't handle it at the moment,
Matthias Braun's avatar
Matthias Braun committed
260
   and it's probably not more efficient on most archs */
Matthias Braun's avatar
Matthias Braun committed
261
#if 0
262
static void try_optimize_cmp(ir_node *node)
Matthias Braun's avatar
Matthias Braun committed
263
264
265
266
267
{
	ir_node *left  = get_Cmp_left(node);
	ir_node *right = get_Cmp_right(node);
	ir_node *conv  = NULL;

268
	if (is_downconv
Matthias Braun's avatar
Matthias Braun committed
269
270
271
}
#endif

272
static void conv_opt_walker(ir_node *node, void *data)
Matthias Braun's avatar
Matthias Braun committed
273
274
275
276
277
278
{
	ir_node *transformed;
	ir_node *pred;
	ir_mode *pred_mode;
	ir_mode *mode;
	int costs;
279
	bool *changed = data;
Matthias Braun's avatar
Matthias Braun committed
280
281

#if 0
282
	if (is_Cmp(node)) {
Matthias Braun's avatar
Matthias Braun committed
283
284
285
286
287
		try_optimize_cmp(node);
		return;
	}
#endif

288
	if (!is_Conv(node))
Matthias Braun's avatar
Matthias Braun committed
289
290
291
292
293
294
		return;

	pred      = get_Conv_op(node);
	mode      = get_irn_mode(node);
	pred_mode = get_irn_mode(pred);

295
296
297
	if (mode_is_reference(mode) || mode_is_reference(pred_mode))
		return;

Christoph Mallon's avatar
Christoph Mallon committed
298
	if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
Matthias Braun's avatar
Matthias Braun committed
299
300
		return;

301
302
	/* - 1 for the initial conv */
	costs = get_conv_costs(pred, mode) - 1;
Matthias Braun's avatar
Matthias Braun committed
303
	DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
304
305
	if (costs > 0)
		return;
Matthias Braun's avatar
Matthias Braun committed
306
307

	transformed = conv_transform(pred, mode);
308
	if (node != transformed) {
Michael Beck's avatar
Michael Beck committed
309
310
		vrp_attr *vrp;

311
		exchange(node, transformed);
Michael Beck's avatar
Michael Beck committed
312
		vrp = vrp_get_info(transformed);
313
314
315
316
317
318
		if (vrp && vrp->valid) {
			vrp->range_type = VRP_VARYING;
			vrp->bits_set = tarval_convert_to(vrp->bits_set, mode);
			vrp->bits_not_set = tarval_convert_to(vrp->bits_not_set, mode);
		}

319
		*changed = true;
320
	}
Matthias Braun's avatar
Matthias Braun committed
321
322
}

323
int conv_opt(ir_graph *irg)
Matthias Braun's avatar
Matthias Braun committed
324
{
325
326
	bool changed;
	bool invalidate = false;
Matthias Braun's avatar
Matthias Braun committed
327
328
329
330
331
	FIRM_DBG_REGISTER(dbg, "firm.opt.conv");

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

	edges_assure(irg);
Christoph Mallon's avatar
Christoph Mallon committed
332
	do {
333
		changed = false;
334
		irg_walk_graph(irg, NULL, conv_opt_walker, &changed);
Christoph Mallon's avatar
Christoph Mallon committed
335
		local_optimize_graph(irg);
Michael Beck's avatar
Michael Beck committed
336
		invalidate |= changed;
Christoph Mallon's avatar
Christoph Mallon committed
337
	} while (changed);
338

Michael Beck's avatar
Michael Beck committed
339
	if (invalidate) {
340
341
		set_irg_outs_inconsistent(irg);
	}
342
	return invalidate;
Matthias Braun's avatar
Matthias Braun committed
343
}
344
345

/* Creates an ir_graph pass for conv_opt. */
346
ir_graph_pass_t *conv_opt_pass(const char *name)
347
{
348
349
	ir_graph_pass_t *path = def_graph_pass_ret(name ? name : "conv_opt", conv_opt);

350
351
	/* safe to run parallel on all irgs */
	ir_graph_pass_set_parallel(path, 1);
352
353

	return path;
354
}