convopt.c 6.87 KB
Newer Older
Matthias Braun's avatar
Matthias Braun committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Matthias Braun's avatar
Matthias Braun committed
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 */

/**
 * @file
 * @brief   conv node optimisation
 * @author  Matthias Braun, Christoph Mallon
 *
 * 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
20
21
22
 *
 * TODO: * try to optimize cmp modes
 *       * decide when it is useful to move the convs through phis
Matthias Braun's avatar
Matthias Braun committed
23
24
25
 */
#include "config.h"

26
27
#include "iroptimize.h"

28
#include <stdbool.h>
Matthias Braun's avatar
Matthias Braun committed
29
30
31
#include "debug.h"
#include "ircons.h"
#include "irgmod.h"
32
#include "irgopt.h"
Matthias Braun's avatar
Matthias Braun committed
33
#include "irnode_t.h"
34
#include "iropt_t.h"
Matthias Braun's avatar
Matthias Braun committed
35
36
#include "iredges_t.h"
#include "irgwalk.h"
37
#include "irpass_t.h"
38
39
#include "tv.h"
#include "vrp.h"
Matthias Braun's avatar
Matthias Braun committed
40

41
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
Matthias Braun's avatar
Matthias Braun committed
42

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

45
static bool is_optimizable_node(const ir_node *node, ir_mode *dest_mode)
Matthias Braun's avatar
Matthias Braun committed
46
{
47
	switch (get_irn_opcode(node)) {
48
49
	case iro_Minus:
	case iro_Phi:
50
51
52
	case iro_And:
	case iro_Eor:
	case iro_Or:
53
54
55
56
	case iro_Not:
		return true;
	case iro_Add:
	case iro_Mul:
57
	case iro_Sub:
58
59
		if (mode_is_float(get_irn_mode(node)))
			return false;
60
		return true;
61
62
63
64
65
66
67
68
69
	case iro_Shl: {
		int modulo_shift = get_mode_modulo_shift(dest_mode);
		int old_shift    = get_mode_modulo_shift(get_irn_mode(node));
		/* bail out if modulo shift changes */
		if (modulo_shift != old_shift)
			return false;
		return true;
	}

70
71
	default:
		return false;
72
	}
73
74
}

Matthias Braun's avatar
Matthias Braun committed
75
static ir_tarval* conv_const_tv(const ir_node* cnst, ir_mode* dest_mode)
76
77
{
	return tarval_convert_to(get_Const_tarval(cnst), dest_mode);
Matthias Braun's avatar
Matthias Braun committed
78
79
}

80
static bool is_downconv(ir_mode *src_mode, ir_mode *dest_mode)
81
{
82
83
84
	return ((mode_is_int(src_mode) && mode_is_int(dest_mode))
		|| (mode_is_float(src_mode) && mode_is_float(dest_mode)))
		&& get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
85
86
}

87
static int get_conv_costs(const ir_node *node, ir_mode *dest_mode)
Matthias Braun's avatar
Matthias Braun committed
88
89
{
	ir_mode *mode = get_irn_mode(node);
90
91
	int arity;
	int i;
92
	int costs;
Matthias Braun's avatar
Matthias Braun committed
93

94
	if (mode == dest_mode)
Matthias Braun's avatar
Matthias Braun committed
95
96
		return 0;

97
98
99
100
	if (is_Const(node)) {
		return conv_const_tv(node, dest_mode) == tarval_bad ? 1 : 0;
	}

101
	if (is_Conv(node) &&
102
			is_downconv(mode, dest_mode) &&
103
104
105
106
			get_irn_mode(get_Conv_op(node)) == dest_mode) {
		return -1;
	}

107
	if (get_irn_n_edges(node) > 1) {
Matthias Braun's avatar
Matthias Braun committed
108
109
110
111
		DB((dbg, LEVEL_3, "multi outs at %+F\n", node));
		return 1;
	}

112
113
114
115
	if (ir_zero_when_converted(node, dest_mode)) {
		return -1;
	}

Matthias Braun's avatar
Matthias Braun committed
116
	/* TODO: Phi nodes */
117

118
119
120
121
122
	if (!is_downconv(mode, dest_mode)) {
		return 1;
	}

	if (is_Conv(node)) {
yb9976's avatar
yb9976 committed
123
124
125
		ir_node *pred      = get_Conv_op(node);
		ir_mode *pred_mode = get_irn_mode(pred);

126
127
128
129
130
131
		if (smaller_mode(pred_mode, dest_mode)) {
			return get_conv_costs(get_Conv_op(node), dest_mode) - 1;
		}
		if (may_leave_out_middle_conv(pred_mode, mode, dest_mode)) {
			return 0;
		} else {
yb9976's avatar
yb9976 committed
132
133
			return 1;
		}
134
135
	}

136
	if (!is_optimizable_node(node, dest_mode)) {
137
138
		return 1;
	}
Matthias Braun's avatar
Matthias Braun committed
139

140
	costs = 0;
141
142
	// The shift count does not participate in the conv optimisation
	arity = is_Shl(node) ? 1 : get_irn_arity(node);
143
144
	for (i = 0; i < arity; ++i) {
		ir_node *pred = get_irn_n(node, i);
145
		costs += imin(get_conv_costs(pred, dest_mode), 1);
Matthias Braun's avatar
Matthias Braun committed
146
147
	}

148
149
150
151
152
153
	return costs;
}

static ir_node *place_conv(ir_node *node, ir_mode *dest_mode)
{
	ir_node *block = get_nodes_block(node);
154
	ir_node *conv = new_r_Conv(block, node, dest_mode);
155
	return conv;
Matthias Braun's avatar
Matthias Braun committed
156
157
}

158
static ir_node *conv_transform(ir_node *node, ir_mode *dest_mode)
Matthias Braun's avatar
Matthias Braun committed
159
{
160
	ir_mode  *mode = get_irn_mode(node);
161
	ir_graph *irg  = get_irn_irg(node);
162
163
164
	int       arity;
	int       conv_arity;
	int       i;
165
	ir_node  *new_node;
166
	ir_node **ins;
Matthias Braun's avatar
Matthias Braun committed
167

168
	if (mode == dest_mode)
Matthias Braun's avatar
Matthias Braun committed
169
170
171
		return node;

	if (is_Const(node)) {
Matthias Braun's avatar
Matthias Braun committed
172
		ir_tarval *tv = conv_const_tv(node, dest_mode);
173
174
175
		if (tv == tarval_bad) {
			return place_conv(node, dest_mode);
		} else {
176
			return new_r_Const(irg, tv);
177
178
179
		}
	}

180
	if (is_Conv(node) &&
181
			is_downconv(mode, dest_mode) &&
182
183
184
185
			get_irn_mode(get_Conv_op(node)) == dest_mode) {
		return get_Conv_op(node);
	}

186
187
	if (get_irn_n_edges(node) > 1) {
		return place_conv(node, dest_mode);
Matthias Braun's avatar
Matthias Braun committed
188
189
	}

190
191
192
193
194
	if (!is_downconv(mode, dest_mode)) {
		return place_conv(node, dest_mode);
	}

	if (is_Conv(node)) {
yb9976's avatar
yb9976 committed
195
196
197
		ir_node *pred      = get_Conv_op(node);
		ir_mode *pred_mode = get_irn_mode(pred);

198
199
		if (smaller_mode(pred_mode, dest_mode)) {
			return conv_transform(get_Conv_op(node), dest_mode);
yb9976's avatar
yb9976 committed
200
		}
201
		return place_conv(node, dest_mode);
Christoph Mallon's avatar
Christoph Mallon committed
202
203
	}

204
	if (!is_optimizable_node(node, dest_mode)) {
205
		return place_conv(node, dest_mode);
Matthias Braun's avatar
Matthias Braun committed
206
207
	}

208
209
210
	// We want to create a new node with the right mode
	arity = get_irn_arity(node);
	ins = ALLOCAN(ir_node *, arity);
211

212
	// The shift count does not participate in the conv optimisation
213
214
215
	conv_arity = is_Shl(node) ? 1 : arity;
	for (i = 0; i < conv_arity; i++) {
		ir_node *pred = get_irn_n(node, i);
216
217
218
219
220
221
		ir_node *transformed;
		if (get_conv_costs(pred, dest_mode) > 0) {
			transformed = place_conv(pred, dest_mode);
		} else {
			transformed = conv_transform(pred, dest_mode);
		}
222
223
224
225
226
		ins[i] = transformed;
	}

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

229
230
231
232
233
234
235
236
237
	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);

238
	return new_node;
Matthias Braun's avatar
Matthias Braun committed
239
240
}

241
static void conv_opt_walker(ir_node *node, void *data)
Matthias Braun's avatar
Matthias Braun committed
242
243
244
245
246
247
{
	ir_node *transformed;
	ir_node *pred;
	ir_mode *pred_mode;
	ir_mode *mode;
	int costs;
248
	bool *changed = (bool*)data;
Matthias Braun's avatar
Matthias Braun committed
249

250
	if (!is_Conv(node))
Matthias Braun's avatar
Matthias Braun committed
251
252
253
254
255
256
		return;

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

257
258
259
	if (mode_is_reference(mode) || mode_is_reference(pred_mode))
		return;

Christoph Mallon's avatar
Christoph Mallon committed
260
	if (!is_Phi(pred) && !is_downconv(pred_mode, mode))
Matthias Braun's avatar
Matthias Braun committed
261
262
		return;

263
264
	/* - 1 for the initial conv */
	costs = get_conv_costs(pred, mode) - 1;
Matthias Braun's avatar
Matthias Braun committed
265
	DB((dbg, LEVEL_2, "Costs for %+F -> %+F: %d\n", node, pred, costs));
266
267
	if (costs > 0)
		return;
Matthias Braun's avatar
Matthias Braun committed
268
269

	transformed = conv_transform(pred, mode);
270
271
	if (node != transformed) {
		exchange(node, transformed);
272
		*changed = true;
273
	}
Matthias Braun's avatar
Matthias Braun committed
274
275
}

276
void conv_opt(ir_graph *irg)
Matthias Braun's avatar
Matthias Braun committed
277
{
278
	bool global_changed = false;
279
	bool changed;
Matthias Braun's avatar
Matthias Braun committed
280
281
	FIRM_DBG_REGISTER(dbg, "firm.opt.conv");

282
283
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);

Matthias Braun's avatar
Matthias Braun committed
284
285
	DB((dbg, LEVEL_1, "===> Performing conversion optimization on %+F\n", irg));

Christoph Mallon's avatar
Christoph Mallon committed
286
	do {
287
		changed = false;
288
		irg_walk_graph(irg, NULL, conv_opt_walker, &changed);
Christoph Mallon's avatar
Christoph Mallon committed
289
		local_optimize_graph(irg);
290
		global_changed |= changed;
Christoph Mallon's avatar
Christoph Mallon committed
291
	} while (changed);
292

293
294
	confirm_irg_properties(irg,
		global_changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
Matthias Braun's avatar
Matthias Braun committed
295
}
296
297

/* Creates an ir_graph pass for conv_opt. */
298
ir_graph_pass_t *conv_opt_pass(const char *name)
299
{
300
	ir_graph_pass_t *path = def_graph_pass(name ? name : "conv_opt", conv_opt);
301

302
303
	/* safe to run parallel on all irgs */
	ir_graph_pass_set_parallel(path, 1);
304
305

	return path;
306
}