lower_mode_b.c 11.3 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
 *
 * 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
21
22
 * @file
 * @brief       lowers operations with mode_b. The result is a graph which
Matthias Braun's avatar
Matthias Braun committed
23
24
25
 *              might still contains some convs from/to mode_b, but no
 *              operations are performed on them anymore, they are just there
 *              so modes match. A backend can safely skip all mode_b convs.
Matthias Braun's avatar
Matthias Braun committed
26
 * @author      Matthias Braun, Christoph Mallon
27
 * @version     $Id$
Matthias Braun's avatar
Matthias Braun committed
28
29
30
31
32
33
34
 */
#include "config.h"

#include <stdlib.h>

#include "irnode_t.h"
#include "ircons_t.h"
35
#include "irflag.h"
Matthias Braun's avatar
Matthias Braun committed
36
37
#include "irgwalk.h"
#include "irtools.h"
38
#include "iredges.h"
Matthias Braun's avatar
Matthias Braun committed
39
#include "iropt_t.h"
Matthias Braun's avatar
Matthias Braun committed
40
41
42
#include "tv.h"
#include "error.h"
#include "lowering.h"
43
#include "pdeq.h"
Michael Beck's avatar
Michael Beck committed
44
#include "irpass_t.h"
Matthias Braun's avatar
Matthias Braun committed
45

46
47
48
static lower_mode_b_config_t  config;
static ir_type               *lowered_type  = NULL;
static pdeq                  *lowered_nodes = NULL;
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
 * Removes a node if its out-edge count has reached 0.
 * temporary hack until we have proper automatic dead code elimination.
 */
static void maybe_kill_node(ir_node *node)
{
	ir_graph *irg;
	int       i, arity;

	if(get_irn_n_edges(node) != 0)
		return;

	irg = get_irn_irg(node);

	assert(!is_Bad(node));

	arity = get_irn_arity(node);
	for (i = 0; i < arity; ++i) {
		set_irn_n(node, i, new_Bad());
	}
	set_nodes_block(node, new_Bad());

	edges_node_deleted(node, irg);
}
Matthias Braun's avatar
Matthias Braun committed
74
75
76
77

static ir_node *create_not(dbg_info *dbgi, ir_node *node)
{
	ir_node  *block  = get_nodes_block(node);
78
79
	ir_mode  *mode   = config.lowered_mode;
	tarval   *tv_one = get_tarval_one(mode);
80
	ir_node  *one    = new_d_Const(dbgi, tv_one);
Matthias Braun's avatar
Matthias Braun committed
81

82
	return new_rd_Eor(dbgi,	block, node, one, mode);
Matthias Braun's avatar
Matthias Braun committed
83
84
}

85
86
87
static ir_node *create_convb(ir_node *node)
{
	ir_node  *block = get_nodes_block(node);
88
	ir_node  *conv  = new_rd_Conv(NULL, block, node, mode_b);
89
90
91
92

	return conv;
}

93
94
95
96
static ir_type *create_lowered_type(void)
{
	if(lowered_type == NULL) {
		lowered_type = new_type_primitive(new_id_from_str("__lowered_mode_b"),
97
		                                  config.lowered_mode);
98
99
100
101
	}
	return lowered_type;
}

102
103
104
105
106
107
108
109
/**
 * creates a "set" node that produces a 0 or 1 based on a Cmp result
 */
static ir_node *create_set(ir_node *node)
{
	dbg_info *dbgi    = get_irn_dbg_info(node);
	ir_mode  *mode    = config.lowered_set_mode;
	tarval   *tv_one  = get_tarval_one(mode);
110
	ir_node  *one     = new_d_Const(dbgi, tv_one);
111
112
	ir_node  *block   = get_nodes_block(node);
	tarval   *tv_zero = get_tarval_null(mode);
113
	ir_node  *zero    = new_d_Const(dbgi, tv_zero);
114

115
	ir_node *set      = new_rd_Mux(dbgi, block, node, zero, one, mode);
116

117
	if (mode != config.lowered_mode) {
118
		set = new_r_Conv(block, set, config.lowered_mode);
119
120
121
122
123
	}

	return set;
}

124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
static void adjust_method_type(ir_type *method_type)
{
	int i;
	int n_params;
	int n_res;

	n_params = get_method_n_params(method_type);
	for(i = 0; i < n_params; ++i) {
		ir_type *param = get_method_param_type(method_type, i);
		if(get_type_mode(param) == mode_b) {
			set_method_param_type(method_type, i, create_lowered_type());
		}
	}

	n_res = get_method_n_ress(method_type);
	for(i = 0; i < n_res; ++i) {
		ir_type *res_type = get_method_res_type(method_type, i);
		if(get_type_mode(res_type) == mode_b) {
			set_method_res_type(method_type, i, create_lowered_type());
		}
	}
}

Matthias Braun's avatar
Matthias Braun committed
147
148
149
150
static ir_node *lower_node(ir_node *node)
{
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_node  *block = get_nodes_block(node);
151
	ir_mode *mode   = config.lowered_mode;
152
	ir_node  *res;
Matthias Braun's avatar
Matthias Braun committed
153
154
155

	assert(get_irn_mode(node) == mode_b);

156
157
158
159
	res = get_irn_link(node);
	if(res != NULL)
		return res;

Matthias Braun's avatar
Matthias Braun committed
160
	/* TODO: be robust against phi-loops... */
161
162
	switch (get_irn_opcode(node)) {
	case iro_Phi: {
163
164
		int       i, arity;
		ir_node **in;
Michael Beck's avatar
Michael Beck committed
165
		ir_node  *unknown, *new_phi;
166

167
168
		arity   = get_irn_arity(node);
		in      = ALLOCAN(ir_node*, arity);
169
		unknown = new_Unknown(config.lowered_mode);
170
171
172
		for(i = 0; i < arity; ++i) {
			in[i] = unknown;
		}
173
		new_phi = new_r_Phi(block, arity, in, config.lowered_mode);
174
		set_irn_link(node, new_phi);
175
		pdeq_putr(lowered_nodes, node);
176
177
178
179

		for(i = 0; i < arity; ++i) {
			ir_node *in     = get_irn_n(node, i);
			ir_node *low_in = lower_node(in);
Matthias Braun's avatar
Matthias Braun committed
180

181
182
183
184
185
186
			set_irn_n(new_phi, i, low_in);
		}

		return new_phi;
	}

187
188
189
	case iro_And:
	case iro_Or:
	case iro_Eor: {
Matthias Braun's avatar
Matthias Braun committed
190
191
192
193
194
195
196
197
198
199
		int i, arity;
		ir_node *copy = exact_copy(node);

		arity = get_irn_arity(node);
		for(i = 0; i < arity; ++i) {
			ir_node *in     = get_irn_n(node, i);
			ir_node *low_in = lower_node(in);

			set_irn_n(copy, i, low_in);
		}
200
		set_irn_mode(copy, config.lowered_mode);
201

202
		set_irn_link(node, copy);
203
		pdeq_putr(lowered_nodes, node);
Matthias Braun's avatar
Matthias Braun committed
204
205
		return copy;
	}
206
	case iro_Not: {
Matthias Braun's avatar
Matthias Braun committed
207
208
209
		ir_node *op     = get_Not_op(node);
		ir_node *low_op = lower_node(op);

210
211
		res = create_not(dbgi, low_op);
		set_irn_link(node, res);
212
		pdeq_putr(lowered_nodes, node);
213
		return res;
Matthias Braun's avatar
Matthias Braun committed
214
	}
215
216
	case iro_Mux: {
		ir_node *cond        = get_Mux_sel(node);
Matthias Braun's avatar
Matthias Braun committed
217
		ir_node *low_cond    = lower_node(cond);
218
		ir_node *v_true      = get_Mux_true(node);
Matthias Braun's avatar
Matthias Braun committed
219
		ir_node *low_v_true  = lower_node(v_true);
220
		ir_node *v_false     = get_Mux_false(node);
Matthias Braun's avatar
Matthias Braun committed
221
222
		ir_node *low_v_false = lower_node(v_false);

223
		ir_node *and0     = new_rd_And(dbgi, block, low_cond, low_v_true, mode);
Matthias Braun's avatar
Matthias Braun committed
224
		ir_node *not_cond = create_not(dbgi, low_cond);
225
226
		ir_node *and1     = new_rd_And(dbgi, block, not_cond, low_v_false, mode);
		ir_node *or       = new_rd_Or(dbgi, block, and0, and1, mode);
Matthias Braun's avatar
Matthias Braun committed
227

228
		set_irn_link(node, or);
229
		pdeq_putr(lowered_nodes, node);
Matthias Braun's avatar
Matthias Braun committed
230
231
		return or;
	}
232
	case iro_Conv: {
233
234
		ir_node *pred     = get_Conv_op(node);
		ir_mode *mode     = get_irn_mode(pred);
Matthias Braun's avatar
Matthias Braun committed
235
		tarval  *tv_zeroc = get_tarval_null(mode);
236
		ir_node *zero_cmp = new_d_Const(dbgi, tv_zeroc);
237
		ir_node *set;
Matthias Braun's avatar
Matthias Braun committed
238

239
240
		ir_node *cmp      = new_rd_Cmp(dbgi, block, pred, zero_cmp);
		ir_node *proj     = new_rd_Proj(dbgi, block, cmp, mode_b, pn_Cmp_Lg);
241
		set = create_set(proj);
Matthias Braun's avatar
Matthias Braun committed
242

243
		set_irn_link(node, set);
244
		pdeq_putr(lowered_nodes, node);
245
		return set;
Matthias Braun's avatar
Matthias Braun committed
246
	}
247
	case iro_Proj: {
248
		ir_node *pred = get_Proj_pred(node);
Matthias Braun's avatar
Matthias Braun committed
249
250
251
252

		if(is_Cmp(pred)) {
			ir_node *left  = get_Cmp_left(pred);
			ir_node *right = get_Cmp_right(pred);
253
254
			ir_mode *cmp_mode  = get_irn_mode(left);
			ir_node *set;
Matthias Braun's avatar
Matthias Braun committed
255

256
257
258
			if ((mode_is_int(cmp_mode) || mode_is_reference(cmp_mode)) && (
						get_mode_size_bits(cmp_mode) < get_mode_size_bits(mode) ||
						(mode_is_signed(cmp_mode) && is_Const(right) && is_Const_null(right))
259
					)) {
Matthias Braun's avatar
Matthias Braun committed
260
				int      pnc      = get_Proj_proj(node);
261
				int      need_not = 0;
Matthias Braun's avatar
Matthias Braun committed
262
263
264
265
266
267
268
269
				ir_node *a        = NULL;
				ir_node *b        = NULL;

				if(pnc == pn_Cmp_Lt) {
					/* a < b  ->  (a - b) >> 31 */
					a = left;
					b = right;
				} else if(pnc == pn_Cmp_Le) {
Matthias Braun's avatar
Matthias Braun committed
270
					/* a <= b  -> ~(a - b) >> 31 */
Matthias Braun's avatar
Matthias Braun committed
271
272
					a        = right;
					b        = left;
273
					need_not = 1;
Matthias Braun's avatar
Matthias Braun committed
274
275
276
277
278
				} else if(pnc == pn_Cmp_Gt) {
					/* a > b   -> (b - a) >> 31 */
					a = right;
					b = left;
				} else if(pnc == pn_Cmp_Ge) {
Matthias Braun's avatar
Matthias Braun committed
279
					/* a >= b   -> ~(a - b) >> 31 */
Matthias Braun's avatar
Matthias Braun committed
280
281
					a        = left;
					b        = right;
282
					need_not = 1;
Matthias Braun's avatar
Matthias Braun committed
283
284
285
				}

				if(a != NULL) {
286
287
					int      bits      = get_mode_size_bits(mode);
					tarval  *tv        = new_tarval_from_long(bits-1, mode_Iu);
288
					ir_node *shift_cnt = new_d_Const(dbgi, tv);
Matthias Braun's avatar
Matthias Braun committed
289

290
					if(cmp_mode != mode) {
291
292
						a = new_rd_Conv(dbgi, block, a, mode);
						b = new_rd_Conv(dbgi, block, b, mode);
Matthias Braun's avatar
Matthias Braun committed
293
294
					}

295
					res = new_rd_Sub(dbgi, block, a, b, mode);
296
					if(need_not) {
297
						res = new_rd_Not(dbgi, block, res, mode);
Matthias Braun's avatar
Matthias Braun committed
298
					}
299
					res = new_rd_Shr(dbgi, block, res, shift_cnt, mode);
Matthias Braun's avatar
Matthias Braun committed
300

301
					set_irn_link(node, res);
302
					pdeq_putr(lowered_nodes, node);
Matthias Braun's avatar
Matthias Braun committed
303
304
305
306
307
					return res;
				}
			}

			/* synthesize the 0/1 value */
308
309
			set = create_set(node);
			set_irn_link(node, set);
310
			pdeq_putr(lowered_nodes, node);
311
			return set;
312
		} else if(is_Proj(pred) && is_Call(get_Proj_pred(pred))) {
313
314
			ir_type   *type   = get_Call_type(get_Proj_pred(pred));
			adjust_method_type(type);
315
			set_irn_mode(node, mode);
316
			return node;
317
		} else if(is_Proj(pred) && is_Start(get_Proj_pred(pred))) {
318
			ir_entity *entity = get_irg_entity(current_ir_graph);
319
320
			ir_type   *type   = get_entity_type(entity);
			adjust_method_type(type);
321
			set_irn_mode(node, mode);
322
			return node;
Matthias Braun's avatar
Matthias Braun committed
323
324
325
326
		}

		panic("unexpected projb: %+F (pred: %+F)", node, pred);
	}
327
	case iro_Const: {
Matthias Braun's avatar
Matthias Braun committed
328
329
		tarval *tv = get_Const_tarval(node);
		if(tv == get_tarval_b_true()) {
330
			tarval  *tv_one  = get_tarval_one(mode);
331
			res              = new_d_Const(dbgi, tv_one);
Matthias Braun's avatar
Matthias Braun committed
332
		} else if(tv == get_tarval_b_false()) {
333
			tarval  *tv_zero = get_tarval_null(mode);
334
			res              = new_d_Const(dbgi, tv_zero);
Matthias Braun's avatar
Matthias Braun committed
335
336
337
		} else {
			panic("invalid boolean const %+F", node);
		}
338
		set_irn_link(node, res);
339
		pdeq_putr(lowered_nodes, node);
340
		return res;
Matthias Braun's avatar
Matthias Braun committed
341
	}
342
	case iro_Unknown:
343
		return new_Unknown(config.lowered_mode);
344
345
	default:
		panic("didn't expect %+F to have mode_b", node);
346
	}
Matthias Braun's avatar
Matthias Braun committed
347
348
349
350
351
}

static void lower_mode_b_walker(ir_node *node, void *env)
{
	int i, arity;
Matthias Braun's avatar
Matthias Braun committed
352
	int changed = 0;
Matthias Braun's avatar
Matthias Braun committed
353
354
355
356
357
358
359
360
361
	(void) env;

	arity = get_irn_arity(node);
	for(i = 0; i < arity; ++i) {
		ir_node *lowered_in;
		ir_node *in = get_irn_n(node, i);
		if(get_irn_mode(in) != mode_b)
			continue;

362
		if(! config.lower_direct_cmp) {
363
364
			if (is_Cond(node) ||
			    (is_Mux(node) && get_irn_mode(node) != mode_b)) {
Matthias Braun's avatar
Matthias Braun committed
365
366
367
368
369
370
371
372
373
				if(is_Proj(in)) {
					ir_node *pred = get_Proj_pred(in);
					if(is_Cmp(pred))
						continue;
				}
			}
		}

		lowered_in = lower_node(in);
374
375
376
377
378
379
380
381
382
383
384

		if(is_Return(node)) {
			ir_entity *entity = get_irg_entity(current_ir_graph);
			ir_type   *type   = get_entity_type(entity);
			adjust_method_type(type);
		} else if(is_Call(node)) {
			ir_type *type = get_Call_type(node);
			adjust_method_type(type);
		} else {
			lowered_in = create_convb(lowered_in);
		}
Matthias Braun's avatar
Matthias Braun committed
385
		set_irn_n(node, i, lowered_in);
Matthias Braun's avatar
Matthias Braun committed
386
387
388
389
		changed = 1;
	}
	if(changed) {
		add_identities(current_ir_graph->value_table, node);
Matthias Braun's avatar
Matthias Braun committed
390
391
392
	}
}

393
394
395
396
397
398
static void clear_links(ir_node *node, void *env)
{
	(void) env;
	set_irn_link(node, NULL);
}

399
void ir_lower_mode_b(ir_graph *irg, const lower_mode_b_config_t *nconfig)
Matthias Braun's avatar
Matthias Braun committed
400
{
401
402
	config        = *nconfig;
	lowered_nodes = new_pdeq();
403

404
405
406
	/* ensure no optimisation touches muxes anymore */
	set_irg_state(irg, IR_GRAPH_STATE_KEEP_MUX);

407
	ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
408

409
	set_opt_allow_conv_b(0);
410
411
	irg_walk_graph(irg, clear_links, NULL, NULL);
	irg_walk_graph(irg, lower_mode_b_walker, NULL, NULL);
412
413
414
415
416
417
418

	while(!pdeq_empty(lowered_nodes)) {
		ir_node *node = (ir_node*) pdeq_getr(lowered_nodes);
		maybe_kill_node(node);
	}
	del_pdeq(lowered_nodes);

419
	ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Matthias Braun's avatar
Matthias Braun committed
420
}
Michael Beck's avatar
Michael Beck committed
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444

struct pass_t {
	ir_graph_pass_t             pass;
	const lower_mode_b_config_t *config;
};

/**
 * Wrapper to run ir_lower_mode_b() as an ir_graph pass
 */
static int pass_wrapper(ir_graph *irg, void *context) {
	struct pass_t *pass = context;

	ir_lower_mode_b(irg, pass->config);
	return 0;
}

ir_graph_pass_t *ir_lower_mode_b_pass(
	const char *name, const lower_mode_b_config_t *config) {
	struct pass_t *pass = XMALLOCZ(struct pass_t);

	pass->config = config;
	return def_graph_pass_constructor(
		&pass->pass, name ? name : "lower_mode_b", pass_wrapper);
}