lower_dw.c 89.4 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Michael Beck's avatar
Michael Beck committed
6
7
/**
 * @file
Matthias Braun's avatar
Matthias Braun committed
8
 * @brief   Lower double word operations, i.e. 64bit -> 32bit, 32bit -> 16bit
Michael Beck's avatar
Michael Beck committed
9
10
 * @date    8.10.2004
 * @author  Michael Beck
11
 */
12
#include <string.h>
13
#include <stdlib.h>
14
#include <stdbool.h>
15
16
#include <assert.h>

17
#include "array.h"
yb9976's avatar
yb9976 committed
18
#include "be.h"
19
#include "constbits.h"
20
#include "dbginfo_t.h"
21
#include "debug.h"
22
#include "firmstat.h"
23
#include "ircons_t.h"
24
#include "irdump.h"
25
#include "irflag.h"
26
27
28
29
30
31
32
33
#include "irflag_t.h"
#include "irgmod.h"
#include "irgraph_t.h"
#include "irgwalk.h"
#include "irmode_t.h"
#include "irnodeset.h"
#include "irnode_t.h"
#include "iropt_dbg.h"
yb9976's avatar
yb9976 committed
34
#include "iroptimize.h"
35
#include "iropt_t.h"
36
#include "irprog_t.h"
37
#include "lower_dw.h"
38
39
40
41
42
43
44
#include "lowering.h"
#include "panic.h"
#include "pdeq.h"
#include "pmap.h"
#include "set.h"
#include "tv_t.h"
#include "type_t.h"
45

Michael Beck's avatar
Michael Beck committed
46
/** A map from (op, imode, omode) to Intrinsic functions entities. */
47
48
static set *intrinsic_fkt;

Michael Beck's avatar
Michael Beck committed
49
50
51
/** A map from (imode, omode) to conv function types. */
static set *conv_types;

52
53
54
/** A map from a method type to its lowered type. */
static pmap *lowered_type;

yb9976's avatar
yb9976 committed
55
56
57
58
/** A map from a builtin type to its lower and higher type. */
static pmap *lowered_builtin_type_high;
static pmap *lowered_builtin_type_low;

59
/** The types for the binop and unop intrinsics. */
60
61
62
63
64
65
66
67
static ir_type *binop_tp_u;
static ir_type *binop_tp_s;
static ir_type *unop_tp_u;
static ir_type *unop_tp_s;
static ir_type *tp_s;
static ir_type *tp_u;
static ir_type *tp_l_s;
static ir_type *tp_l_u;
68

yb9976's avatar
yb9976 committed
69
70
static ir_nodeset_t created_mux_nodes;

71
72
73
74
/** the debug handle */
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

/**
Michael Beck's avatar
Michael Beck committed
75
 * An entry in the (op, imode, omode) -> entity map.
76
 */
77
typedef struct op_mode_entry {
78
	const ir_op   *op;    /**< the op */
Michael Beck's avatar
Michael Beck committed
79
80
	const ir_mode *imode; /**< the input mode */
	const ir_mode *omode; /**< the output mode */
Matthias Braun's avatar
Matthias Braun committed
81
82
	ir_entity     *ent;   /**< the associated entity of this (op, imode, omode)
	                           triple */
83
84
} op_mode_entry_t;

Michael Beck's avatar
Michael Beck committed
85
86
87
/**
 * An entry in the (imode, omode) -> tp map.
 */
88
typedef struct conv_tp_entry {
Michael Beck's avatar
Michael Beck committed
89
90
	const ir_mode *imode; /**< the input mode */
	const ir_mode *omode; /**< the output mode */
Matthias Braun's avatar
Matthias Braun committed
91
92
	ir_type       *mtd;   /**< the associated method type of this
	                           (imode, omode) pair */
Michael Beck's avatar
Michael Beck committed
93
94
} conv_tp_entry_t;

95
enum lower_flags {
Matthias Braun's avatar
Matthias Braun committed
96
97
	MUST_BE_LOWERED = (1 << 0),  /**< graph must be lowered */
	CF_CHANGED      = (1 << 1),  /**< control flow was changed */
98
99
100
101
102
};

/**
 * The lower environment.
 */
103
typedef struct lower_dw_env_t {
104
105
106
107
108
109
110
111
112
113
114
	lower64_entry_t **entries;       /**< entries per node */
	ir_graph         *irg;
	struct obstack    obst;          /**< obstack for temporary data */
	ir_tarval        *tv_mode_bytes; /**< a tarval containing the number of
	                                      bytes in the lowered modes */
	pdeq             *waitq;         /**< a wait queue of all nodes that must be
	                                      handled later */
	ir_node         **lowered_phis;  /**< list of lowered phis */
	lwrdw_param_t     p;             /**< transformation parameter */
	unsigned          flags;         /**< some flags */
	unsigned          n_entries;     /**< number of entries */
115
} lower_dw_env_t;
116

117
static lower_dw_env_t env;
118
119

static void lower_node(ir_node *node);
120

121
122
static bool needs_lowering(const ir_mode *mode)
{
123
124
	return get_mode_size_bits(mode) == env.p.doubleword_size
	    && get_mode_arithmetic(mode) == irma_twos_complement;
125
126
}

Michael Beck's avatar
Michael Beck committed
127
128
129
/**
 * Create a method type for a Conv emulation from imode to omode.
 */
130
static ir_type *get_conv_type(ir_mode *imode, ir_mode *omode)
131
{
Matthias Braun's avatar
Matthias Braun committed
132
	conv_tp_entry_t key;
Michael Beck's avatar
Michael Beck committed
133
134
135
136
	key.imode = imode;
	key.omode = omode;
	key.mtd   = NULL;

Matthias Braun's avatar
Matthias Braun committed
137
138
139
140
141
142
	unsigned hash = hash_ptr(imode) ^ hash_ptr(omode);
	conv_tp_entry_t *entry
		= set_insert(conv_tp_entry_t, conv_types, &key, sizeof(key), hash);
	ir_type *mtd = entry->mtd;
	if (mtd != NULL)
		return mtd;
Michael Beck's avatar
Michael Beck committed
143

Matthias Braun's avatar
Matthias Braun committed
144
	size_t n_param = 1;
Matthias Braun's avatar
Matthias Braun committed
145
	size_t n_res   = 1;
146
	if (needs_lowering(imode))
Matthias Braun's avatar
Matthias Braun committed
147
		n_param = 2;
148
	if (needs_lowering(omode))
Matthias Braun's avatar
Matthias Braun committed
149
		n_res = 2;
Michael Beck's avatar
Michael Beck committed
150

Matthias Braun's avatar
Matthias Braun committed
151
152
	/* create a new method type */
	mtd = new_type_method(n_param, n_res);
Michael Beck's avatar
Michael Beck committed
153

Matthias Braun's avatar
Matthias Braun committed
154
155
	/* set param types and result types */
	n_param = 0;
156
157
	if (needs_lowering(imode)) {
		if (mode_is_signed(imode)) {
158
			if (env.p.big_endian) {
159
				set_method_param_type(mtd, n_param++, tp_l_s);
Matthias Braun's avatar
Matthias Braun committed
160
				set_method_param_type(mtd, n_param++, tp_u);
161
			} else {
162
				set_method_param_type(mtd, n_param++, tp_l_u);
Matthias Braun's avatar
Matthias Braun committed
163
				set_method_param_type(mtd, n_param++, tp_s);
164
			}
Michael Beck's avatar
BugFix:    
Michael Beck committed
165
		} else {
166
			set_method_param_type(mtd, n_param++, tp_l_u);
Matthias Braun's avatar
Matthias Braun committed
167
			set_method_param_type(mtd, n_param++, tp_u);
168
		}
Matthias Braun's avatar
Matthias Braun committed
169
170
171
172
	} else {
		ir_type *tp = get_type_for_mode(imode);
		set_method_param_type(mtd, n_param++, tp);
	}
Michael Beck's avatar
Michael Beck committed
173

Matthias Braun's avatar
Matthias Braun committed
174
	n_res = 0;
175
176
	if (needs_lowering(omode)) {
		if (mode_is_signed(omode)) {
177
			if (env.p.big_endian) {
178
				set_method_res_type(mtd, n_res++, tp_l_s);
Matthias Braun's avatar
Matthias Braun committed
179
				set_method_res_type(mtd, n_res++, tp_u);
180
			} else {
181
				set_method_res_type(mtd, n_res++, tp_l_u);
Matthias Braun's avatar
Matthias Braun committed
182
				set_method_res_type(mtd, n_res++, tp_s);
183
			}
Michael Beck's avatar
BugFix:    
Michael Beck committed
184
		} else {
185
			set_method_res_type(mtd, n_res++, tp_l_u);
Matthias Braun's avatar
Matthias Braun committed
186
			set_method_res_type(mtd, n_res++, tp_u);
187
		}
Michael Beck's avatar
BugFix:    
Michael Beck committed
188
	} else {
Matthias Braun's avatar
Matthias Braun committed
189
190
		ir_type *tp = get_type_for_mode(omode);
		set_method_res_type(mtd, n_res++, tp);
191
	}
Matthias Braun's avatar
Matthias Braun committed
192
	entry->mtd = mtd;
Michael Beck's avatar
Michael Beck committed
193
	return mtd;
194
}
Michael Beck's avatar
Michael Beck committed
195

196
197
198
199
200
201
202
/**
 * Add an additional control flow input to a block.
 * Patch all Phi nodes. The new Phi inputs are copied from
 * old input number nr.
 */
static void add_block_cf_input_nr(ir_node *block, int nr, ir_node *cf)
{
Matthias Braun's avatar
Matthias Braun committed
203
204
205
206
	int n_cfgpreds = get_Block_n_cfgpreds(block);
	assert(nr < n_cfgpreds);
	ir_node **in = ALLOCAN(ir_node*, n_cfgpreds+1);
	for (int i = 0; i < n_cfgpreds; ++i)
207
		in[i] = get_Block_cfgpred(block, i);
Matthias Braun's avatar
Matthias Braun committed
208
209
	in[n_cfgpreds] = cf;
	set_irn_in(block, n_cfgpreds+1, in);
210

211
212
213
214
215
	foreach_out_edge(block, edge) {
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;

216
217
		foreach_irn_in(phi, i, pred)
			in[i] = pred;
Matthias Braun's avatar
Matthias Braun committed
218
219
		in[n_cfgpreds] = in[nr];
		set_irn_in(phi, n_cfgpreds+1, in);
220
221
	}
}
222
223
224
225
226
227
228
229

/**
 * Add an additional control flow input to a block.
 * Patch all Phi nodes. The new Phi inputs are copied from
 * old input from cf tmpl.
 */
static void add_block_cf_input(ir_node *block, ir_node *tmpl, ir_node *cf)
{
Matthias Braun's avatar
Matthias Braun committed
230
231
232
	int nr = -1;
	for (int i = 0, n_cfgpreds = get_Block_n_cfgpreds(block); i < n_cfgpreds;
	     ++i) {
233
		if (get_Block_cfgpred(block, i) == tmpl) {
234
235
			nr = i;
			break;
236
237
		}
	}
Matthias Braun's avatar
Matthias Braun committed
238
	assert(nr >= 0);
239
	add_block_cf_input_nr(block, nr, cf);
240
}
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259

/**
 * Return the "operational" mode of a Firm node.
 */
static ir_mode *get_irn_op_mode(ir_node *node)
{
	switch (get_irn_opcode(node)) {
	case iro_Load:
		return get_Load_mode(node);
	case iro_Store:
		return get_irn_mode(get_Store_value(node));
	case iro_Div:
		return get_irn_mode(get_Div_left(node));
	case iro_Mod:
		return get_irn_mode(get_Mod_left(node));
	case iro_Cmp:
		return get_irn_mode(get_Cmp_left(node));
	default:
		return get_irn_mode(node);
260
261
	}
}
262
263

/**
264
265
 * Walker, prepare the node links and determine which nodes need to be lowered
 * at all.
266
 */
267
static void prepare_links(ir_node *node, void *data)
268
{
269
	(void)data;
Matthias Braun's avatar
Matthias Braun committed
270
	ir_mode *mode = get_irn_op_mode(node);
271

272
	if (needs_lowering(mode)) {
273
		unsigned idx = get_irn_idx(node);
274
		/* ok, found a node that will be lowered */
275
		lower64_entry_t *link = OALLOCZ(&env.obst, lower64_entry_t);
276

277
278
279
		assert(idx < env.n_entries);
		env.entries[idx] = link;
		env.flags |= MUST_BE_LOWERED;
280
	} else if (is_Conv(node)) {
281
		/* Conv nodes have two modes */
Matthias Braun's avatar
Matthias Braun committed
282
283
		const ir_node *pred = get_Conv_op(node);
		ir_mode *dest_mode = get_irn_mode(pred);
284

285
		if (needs_lowering(dest_mode)) {
Michael Beck's avatar
BugFix:    
Michael Beck committed
286
			/* must lower this node either but don't need a link */
287
			env.flags |= MUST_BE_LOWERED;
288
		}
289
		return;
290
291
292
293
294
295
	} else if (is_Call(node)) {
		/* Special case:  If the result of the Call is never used, we won't
		 * find a Proj with a mode that potentially triggers MUST_BE_LOWERED
		 * to be set.  Thus, if we see a call, we check its result types and
		 * decide whether MUST_BE_LOWERED has to be set.
		 */
Matthias Braun's avatar
Matthias Braun committed
296
297
298
		const ir_type *tp = get_Call_type(node);
		for (size_t i = 0, n_res = get_method_n_ress(tp); i < n_res; ++i) {
			const ir_type *rtp = get_method_res_type(tp, i);
299
300
			if (is_Primitive_type(rtp)) {
				ir_mode *rmode = get_type_mode(rtp);
301
				if (needs_lowering(rmode)) {
302
					env.flags |= MUST_BE_LOWERED;
303
304
305
				}
			}
		}
306
307
	}
}
308

309
lower64_entry_t *get_node_entry(ir_node *node)
310
311
{
	unsigned idx = get_irn_idx(node);
312
313
	assert(idx < env.n_entries);
	return env.entries[idx];
314
315
}

316
void ir_set_dw_lowered(ir_node *old, ir_node *new_low, ir_node *new_high)
317
{
318
	lower64_entry_t *entry = get_node_entry(old);
319
320
321
322
	entry->low_word  = new_low;
	entry->high_word = new_high;
}

323
324
ir_mode *ir_get_low_unsigned_mode(void)
{
325
	return env.p.word_unsigned;
326
327
}

328
329
330
/**
 * Translate a Constant: create two.
 */
331
static void lower_Const(ir_node *node, ir_mode *mode)
332
{
Matthias Braun's avatar
Matthias Braun committed
333
334
	ir_graph  *irg      = get_irn_irg(node);
	dbg_info  *dbg      = get_irn_dbg_info(node);
335
	ir_mode   *low_mode = env.p.word_unsigned;
Matthias Braun's avatar
Matthias Braun committed
336
337
338
	ir_tarval *tv       = get_Const_tarval(node);
	ir_tarval *tv_l     = tarval_convert_to(tv, low_mode);
	ir_node   *res_low  = new_rd_Const(dbg, irg, tv_l);
339
	ir_tarval *tv_shrs  = tarval_shrs_unsigned(tv, get_mode_size_bits(low_mode));
Matthias Braun's avatar
Matthias Braun committed
340
341
	ir_tarval *tv_h     = tarval_convert_to(tv_shrs, mode);
	ir_node   *res_high = new_rd_Const(dbg, irg, tv_h);
342

343
	ir_set_dw_lowered(node, res_low, res_high);
344
}
345
346
347
348

/**
 * Translate a Load: create two.
 */
349
static void lower_Load(ir_node *node, ir_mode *mode)
350
{
351
	ir_mode  *low_mode = env.p.word_unsigned;
Matthias Braun's avatar
Matthias Braun committed
352
353
354
	ir_graph *irg      = get_irn_irg(node);
	ir_node  *adr      = get_Load_ptr(node);
	ir_node  *mem      = get_Load_mem(node);
355
	ir_type  *type     = get_Load_type(node);
356
	ir_node  *cnst     = new_r_Const(irg, env.tv_mode_bytes);
Matthias Braun's avatar
Matthias Braun committed
357
358
359
360
	ir_mode  *adr_mode = get_irn_mode(adr);
	ir_node  *block    = get_nodes_block(node);
	ir_node *low;
	ir_node *high;
361
	if (env.p.big_endian) {
Matthias Braun's avatar
Matthias Braun committed
362
		low  = new_r_Add(block, adr, cnst, adr_mode);
363
		high = adr;
Matthias Braun's avatar
Matthias Braun committed
364
365
366
	} else {
		low  = adr;
		high = new_r_Add(block, adr, cnst, adr_mode);
367
	}
368
369

	/* create two loads */
Matthias Braun's avatar
Matthias Braun committed
370
371
372
373
	ir_cons_flags volatility
		= get_Load_volatility(node) == volatility_is_volatile ? cons_volatile
		                                                      : cons_none;
	dbg_info *dbg   = get_irn_dbg_info(node);
374
	low             = new_rd_Load(dbg, block, mem,    low,  low_mode, type, volatility);
Matthias Braun's avatar
Matthias Braun committed
375
	ir_node *proj_m = new_r_Proj(low, mode_M, pn_Load_M);
376
	high            = new_rd_Load(dbg, block, proj_m, high, mode,     type, volatility);
377

378
	foreach_out_edge_safe(node, edge) {
379
380
381
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;
382

383
		switch ((pn_Load)get_Proj_num(proj)) {
Matthias Braun's avatar
Matthias Braun committed
384
		case pn_Load_M:
385
386
387
388
389
390
391
			/* put it to the second one */
			set_Proj_pred(proj, high);
			break;
		case pn_Load_X_except:  /* Execution result if exception occurred. */
			/* put it to the first one */
			set_Proj_pred(proj, low);
			break;
Matthias Braun's avatar
Matthias Braun committed
392
393
394
		case pn_Load_X_regular:
			set_Proj_pred(proj, high);
			break;
395
396
397
		case pn_Load_res: {       /* Result of load operation. */
			ir_node *res_low  = new_r_Proj(low,  low_mode, pn_Load_res);
			ir_node *res_high = new_r_Proj(high, mode,     pn_Load_res);
398
			ir_set_dw_lowered(proj, res_low, res_high);
399
			break;
400
		}
401
		}
402
403
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
404
		mark_irn_visited(proj);
405
406
	}
}
407
408
409
410

/**
 * Translate a Store: create two.
 */
411
static void lower_Store(ir_node *node, ir_mode *mode)
412
{
Matthias Braun's avatar
Matthias Braun committed
413
	(void)mode;
414
415
	ir_node               *value = get_Store_value(node);
	const lower64_entry_t *entry = get_node_entry(value);
416

Matthias Braun's avatar
Matthias Braun committed
417
418
419
	ir_graph *irg      = get_irn_irg(node);
	ir_node  *adr      = get_Store_ptr(node);
	ir_node  *mem      = get_Store_mem(node);
420
	ir_type  *type     = get_Store_type(node);
Matthias Braun's avatar
Matthias Braun committed
421
	ir_node  *block    = get_nodes_block(node);
422
	ir_node  *cnst     = new_r_Const(irg, env.tv_mode_bytes);
Matthias Braun's avatar
Matthias Braun committed
423
424
425
	ir_mode  *adr_mode = get_irn_mode(adr);
	ir_node  *low;
	ir_node  *high;
426
	if (env.p.big_endian) {
Matthias Braun's avatar
Matthias Braun committed
427
		low  = new_r_Add(block, adr, cnst, adr_mode);
428
		high = adr;
Matthias Braun's avatar
Matthias Braun committed
429
430
431
	} else {
		low  = adr;
		high = new_r_Add(block, adr, cnst, adr_mode);
432
	}
433
434

	/* create two Stores */
Matthias Braun's avatar
Matthias Braun committed
435
436
437
438
	ir_cons_flags volatility
		= get_Store_volatility(node) == volatility_is_volatile ? cons_volatile
		                                                       : cons_none;
	dbg_info *dbg   = get_irn_dbg_info(node);
439
	low = new_rd_Store(dbg, block, mem, low,  entry->low_word, type, volatility);
Matthias Braun's avatar
Matthias Braun committed
440
	ir_node *proj_m = new_r_Proj(low, mode_M, pn_Store_M);
441
	high = new_rd_Store(dbg, block, proj_m, high, entry->high_word, type, volatility);
442

443
	foreach_out_edge_safe(node, edge) {
444
445
446
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;
447

448
		switch ((pn_Store)get_Proj_num(proj)) {
449
450
451
452
453
454
455
456
		case pn_Store_M:         /* Memory result. */
			/* put it to the second one */
			set_Proj_pred(proj, high);
			break;
		case pn_Store_X_except:  /* Execution result if exception occurred. */
			/* put it to the first one */
			set_Proj_pred(proj, low);
			break;
Matthias Braun's avatar
Matthias Braun committed
457
458
459
		case pn_Store_X_regular:
			set_Proj_pred(proj, high);
			break;
460
		}
Matthias Braun's avatar
Matthias Braun committed
461
462
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
463
		mark_irn_visited(proj);
464
465
	}
}
466
467
468

/**
 * Return a node containing the address of the intrinsic emulation function.
Michael Beck's avatar
Michael Beck committed
469
470
471
472
473
474
 *
 * @param method  the method type of the emulation function
 * @param op      the emulated ir_op
 * @param imode   the input mode of the emulated opcode
 * @param omode   the output mode of the emulated opcode
 * @param env     the lower environment
475
 */
Michael Beck's avatar
Michael Beck committed
476
static ir_node *get_intrinsic_address(ir_type *method, ir_op *op,
477
                                      ir_mode *imode, ir_mode *omode)
478
{
Matthias Braun's avatar
Matthias Braun committed
479
	op_mode_entry_t key;
Michael Beck's avatar
Michael Beck committed
480
481
482
483
	key.op    = op;
	key.imode = imode;
	key.omode = omode;
	key.ent   = NULL;
484

Matthias Braun's avatar
Matthias Braun committed
485
486
487
488
489
	unsigned hash = hash_ptr(op) ^ hash_ptr(imode) ^ (hash_ptr(omode) << 8);
	op_mode_entry_t *entry
		= set_insert(op_mode_entry_t, intrinsic_fkt, &key, sizeof(key), hash);
	ir_entity *ent = entry->ent;
	if (ent == NULL) {
490
		/* create a new one */
491
		ent = env.p.create_intrinsic(method, op, imode, omode, env.p.ctx);
492
493
494

		assert(ent && "Intrinsic creator must return an entity");
		entry->ent = ent;
495
	}
496
	return new_r_Address(env.irg, ent);
497
}
498
499
500
501
502
503

/**
 * Translate a Div.
 *
 * Create an intrinsic Call.
 */
504
static void lower_Div(ir_node *node, ir_mode *mode)
505
{
506
507
508
509
510
511
	ir_node  *left   = get_Div_left(node);
	ir_node  *right  = get_Div_right(node);
	ir_node  *block  = get_nodes_block(node);
	dbg_info *dbgi   = get_irn_dbg_info(node);
	ir_type  *mtp    = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	ir_mode  *opmode = get_irn_op_mode(node);
Matthias Braun's avatar
Matthias Braun committed
512
513
	ir_node  *addr   = get_intrinsic_address(mtp, get_irn_op(node), opmode,
	                                         opmode);
514

Matthias Braun's avatar
Matthias Braun committed
515
	ir_node  *in[4];
516
	if (env.p.big_endian) {
517
518
519
520
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
Matthias Braun's avatar
Matthias Braun committed
521
522
523
524
525
	} else {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
526
	}
Matthias Braun's avatar
Matthias Braun committed
527
528
529
	ir_node *mem     = get_Div_mem(node);
	ir_node *call    = new_rd_Call(dbgi, block, mem, addr, 4, in, mtp);
	ir_node *resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
530
531
	set_irn_pinned(call, get_irn_pinned(node));

532
	foreach_out_edge_safe(node, edge) {
533
534
535
536
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;

537
		switch ((pn_Div)get_Proj_num(proj)) {
Matthias Braun's avatar
Matthias Braun committed
538
		case pn_Div_M:
539
540
			/* reroute to the call */
			set_Proj_pred(proj, call);
541
			set_Proj_num(proj, pn_Call_M);
542
			break;
543
544
		case pn_Div_X_regular:
			set_Proj_pred(proj, call);
545
			set_Proj_num(proj, pn_Call_X_regular);
546
547
			break;
		case pn_Div_X_except:
548
			set_Proj_pred(proj, call);
549
			set_Proj_num(proj, pn_Call_X_except);
550
			break;
551
		case pn_Div_res:
552
			if (env.p.big_endian) {
553
554
				ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 1);
				ir_node *res_high = new_r_Proj(resproj, mode,                0);
555
				ir_set_dw_lowered(proj, res_low, res_high);
Matthias Braun's avatar
Matthias Braun committed
556
			} else {
557
558
				ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 0);
				ir_node *res_high = new_r_Proj(resproj, mode,                1);
Matthias Braun's avatar
Matthias Braun committed
559
				ir_set_dw_lowered(proj, res_low, res_high);
560
			}
561
			break;
562
		}
Matthias Braun's avatar
Matthias Braun committed
563
564
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
565
		mark_irn_visited(proj);
566
567
	}
}
568
569
570
571
572
573

/**
 * Translate a Mod.
 *
 * Create an intrinsic Call.
 */
574
static void lower_Mod(ir_node *node, ir_mode *mode)
575
{
576
577
578
579
580
581
582
	ir_node  *left   = get_Mod_left(node);
	ir_node  *right  = get_Mod_right(node);
	dbg_info *dbgi   = get_irn_dbg_info(node);
	ir_node  *block  = get_nodes_block(node);
	ir_type  *mtp    = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	ir_mode  *opmode = get_irn_op_mode(node);
	ir_node  *addr   = get_intrinsic_address(mtp, get_irn_op(node), opmode, opmode);
583

Matthias Braun's avatar
Matthias Braun committed
584
	ir_node *in[4];
585
	if (env.p.big_endian) {
586
587
588
589
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
Matthias Braun's avatar
Matthias Braun committed
590
591
592
593
594
	} else {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
595
	}
Matthias Braun's avatar
Matthias Braun committed
596
597
598
	ir_node *mem     = get_Mod_mem(node);
	ir_node *call    = new_rd_Call(dbgi, block, mem, addr, 4, in, mtp);
	ir_node *resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
599
600
	set_irn_pinned(call, get_irn_pinned(node));

601
	foreach_out_edge_safe(node, edge) {
602
603
604
605
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;

606
		switch ((pn_Mod)get_Proj_num(proj)) {
Matthias Braun's avatar
Matthias Braun committed
607
		case pn_Mod_M:
608
609
			/* reroute to the call */
			set_Proj_pred(proj, call);
610
			set_Proj_num(proj, pn_Call_M);
611
			break;
Matthias Braun's avatar
Matthias Braun committed
612
		case pn_Mod_X_regular:
613
			set_Proj_pred(proj, call);
614
			set_Proj_num(proj, pn_Call_X_regular);
615
616
			break;
		case pn_Mod_X_except:
617
			set_Proj_pred(proj, call);
618
			set_Proj_num(proj, pn_Call_X_except);
619
			break;
620
		case pn_Mod_res:
621
			if (env.p.big_endian) {
622
623
				ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 1);
				ir_node *res_high = new_r_Proj(resproj, mode,                0);
624
				ir_set_dw_lowered(proj, res_low, res_high);
Matthias Braun's avatar
Matthias Braun committed
625
			} else {
626
627
				ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 0);
				ir_node *res_high = new_r_Proj(resproj, mode,                1);
Matthias Braun's avatar
Matthias Braun committed
628
				ir_set_dw_lowered(proj, res_low, res_high);
629
			}
630
			break;
631
		}
632
633
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
634
		mark_irn_visited(proj);
635
636
	}
}
637
638

/**
639
 * Translate a binop.
640
641
642
 *
 * Create an intrinsic Call.
 */
643
static void lower_binop(ir_node *node, ir_mode *mode)
644
{
645
646
647
648
649
650
651
652
	ir_node  *left  = get_binop_left(node);
	ir_node  *right = get_binop_right(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_node  *block = get_nodes_block(node);
	ir_graph *irg   = get_irn_irg(block);
	ir_type  *mtp   = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	ir_node  *addr  = get_intrinsic_address(mtp, get_irn_op(node), mode, mode);

Matthias Braun's avatar
Matthias Braun committed
653
	ir_node  *in[4];
654
	if (env.p.big_endian) {
655
656
657
658
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
Matthias Braun's avatar
Matthias Braun committed
659
660
661
662
663
	} else {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
664
	}
Matthias Braun's avatar
Matthias Braun committed
665
666
667
	ir_node *mem     = get_irg_no_mem(irg);
	ir_node *call    = new_rd_Call(dbgi, block, mem, addr, 4, in, mtp);
	ir_node *resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
668
	set_irn_pinned(call, get_irn_pinned(node));
669

670
	if (env.p.big_endian) {
671
672
		ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 1);
		ir_node *res_high = new_r_Proj(resproj, mode,                0);
673
		ir_set_dw_lowered(node, res_low, res_high);
Matthias Braun's avatar
Matthias Braun committed
674
	} else {
675
676
		ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 0);
		ir_node *res_high = new_r_Proj(resproj, mode,                1);
Matthias Braun's avatar
Matthias Braun committed
677
		ir_set_dw_lowered(node, res_low, res_high);
678
	}
679
}
680

681
static ir_node *create_conv(ir_node *block, ir_node *node, ir_mode *dest_mode)
682
{
683
684
685
	if (get_irn_mode(node) == dest_mode)
		return node;
	return new_r_Conv(block, node, dest_mode);
686
}
Christian Würdig's avatar
Christian Würdig committed
687

688
689
690
691
692
693
694
695
696
697
698
699
700
static void move_node(ir_node *node, ir_node *to_bl)
{
	set_nodes_block(node, to_bl);
	if (get_irn_mode(node) != mode_T)
		return;
	foreach_out_edge(node, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;
		move_node(proj, to_bl);
	}
}

Michael Beck's avatar
Michael Beck committed
701
/**
702
703
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
Michael Beck's avatar
Michael Beck committed
704
 */
705
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
706
{
707
	move_node(node, to_bl);
Michael Beck's avatar
Michael Beck committed
708

709
710
	/* We must not move predecessors of Phi nodes, even if they are in
	 * from_bl. (because these are values from an earlier loop iteration
711
	 * which are not predecessors of node here) */
712
713
714
715
	if (is_Phi(node))
		return;

	/* recursion ... */
716
	foreach_irn_in(node, i, pred) {
717
718
719
		ir_mode *pred_mode = get_irn_mode(pred);
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
720
		if (needs_lowering(pred_mode)) {
721
722
723
724
725
726
			ir_node *pred_low  = get_lowered_low(pred);
			ir_node *pred_high = get_lowered_high(pred);
			if (get_nodes_block(pred_low) == from_bl)
				move(pred_low, from_bl, to_bl);
			if (pred_high != NULL && get_nodes_block(pred_high) == from_bl)
				move(pred_high, from_bl, to_bl);
727
728
729
		}
	}
}
Michael Beck's avatar
Michael Beck committed
730

Matthias Braun's avatar
Matthias Braun committed
731
ir_node *part_block_dw(ir_node *node)
732
{
733
734
735
736
737
	ir_graph *irg        = get_irn_irg(node);
	ir_node  *old_block  = get_nodes_block(node);
	int       n_cfgpreds = get_Block_n_cfgpreds(old_block);
	ir_node **cfgpreds   = get_Block_cfgpred_arr(old_block);
	ir_node  *new_block  = new_r_Block(irg, n_cfgpreds, cfgpreds);
738

739
740
741
742
743
744
	/* old_block has no predecessors anymore for now */
	set_irn_in(old_block, 0, NULL);

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

745
	/* move Phi nodes and constants to new_block */
746
	foreach_out_edge_safe(old_block, edge) {
747
		ir_node *blnode = get_edge_src_irn(edge);
748
749
		if (is_Phi(blnode) || is_irn_start_block_placed(blnode))
			move_node(blnode, new_block);
750
	}
751
752
	if (old_block == get_irg_start_block(irg))
		set_irg_start_block(irg, new_block);
753
	return old_block;
754
}
Michael Beck's avatar
Michael Beck committed
755

756
757
void set_dw_control_flow_changed(void)
{
758
	env.flags |= CF_CHANGED;
759
760
}

761
762
763
764
765
766
typedef ir_node* (*new_rd_shr_func)(dbg_info *dbgi, ir_node *block,
                                    ir_node *left, ir_node *right,
                                    ir_mode *mode);

static void lower_shr_helper(ir_node *node, ir_mode *mode,
                             new_rd_shr_func new_rd_shrs)
767
{
768
769
770
771
	ir_node  *right         = get_binop_right(node);
	ir_node  *left          = get_binop_left(node);
	ir_mode  *shr_mode      = get_irn_mode(node);
	unsigned  modulo_shift  = get_mode_modulo_shift(shr_mode);
772
	ir_mode  *low_unsigned  = env.p.word_unsigned;
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
	unsigned  modulo_shift2 = get_mode_modulo_shift(mode);
	ir_graph *irg           = get_irn_irg(node);
	ir_node  *left_low      = get_lowered_low(left);
	ir_node  *left_high     = get_lowered_high(left);
	dbg_info *dbgi          = get_irn_dbg_info(node);

	/* this version is optimized for modulo shift architectures
	 * (and can't handle anything else) */
	if (modulo_shift != get_mode_size_bits(shr_mode)
			|| modulo_shift2<<1 != modulo_shift) {
		panic("Shr lowering only implemented for modulo shift shr operations");
	}
	if (!is_po2(modulo_shift) || !is_po2(modulo_shift2)) {
		panic("Shr lowering only implemented for power-of-2 modes");
	}
	/* without 2-complement the -x instead of (bit_width-x) trick won't work */
	if (get_mode_arithmetic(shr_mode) != irma_twos_complement) {
		panic("Shr lowering only implemented for two-complement modes");
	}

Matthias Braun's avatar
Matthias Braun committed
793
	ir_node *block = get_nodes_block(node);
794

795
796
	/* if the right operand is a 64bit value, we're only interested in the
	 * lower word */
797
798
	assert(!mode_is_signed(get_irn_mode(right)));
	if (needs_lowering(get_irn_mode(right))) {
799
800
801
802
803
		right = get_lowered_low(right);
	} else {
		/* shift should never have signed mode on the right */
		right = create_conv(block, right, low_unsigned);
	}
Michael Beck's avatar
Michael Beck committed
804

Matthias Braun's avatar
Matthias Braun committed
805
	ir_node *lower_block = part_block_dw(node);
806
	env.flags |= CF_CHANGED;
807
808
	block = get_nodes_block(node);

Michael Beck's avatar
Michael Beck committed
809
	/* add a Cmp to test if highest bit is set <=> whether we shift more
810
	 * than half the word width */
Matthias Braun's avatar
Matthias Braun committed
811
812
	ir_node *cnst  = new_r_Const_long(irg, low_unsigned, modulo_shift2);
	ir_node *andn  = new_r_And(block, right, cnst, low_unsigned);
813
	ir_node *cnst2 = new_r_Const_null(irg, low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
814
815
816
817
	ir_node *cmp   = new_rd_Cmp(dbgi, block, andn, cnst2, ir_relation_equal);
	ir_node *cond       = new_rd_Cond(dbgi, block, cmp);
	ir_node *proj_true  = new_r_Proj(cond, mode_X, pn_Cond_true);
	ir_node *proj_false = new_r_Proj(cond, mode_X, pn_Cond_false);
818
819

	/* the true block => shift_width < 1word */
Matthias Braun's avatar
Matthias Braun committed
820
821
822
823
824
825
826
827
828
	/* In theory the low value (for 64bit shifts) is:
	 *    Or(High << (32-x)), Low >> x)
	 * In practice High << 32-x will fail when x is zero (since we have
	 * modulo shift and 32 will be 0). So instead we use:
	 *    Or(High<<1<<~x, Low >> x)
	 */
	ir_node *true_in[1]   = { proj_true };
	ir_node *block_true   = new_r_Block(irg, ARRAY_SIZE(true_in), true_in);
	ir_node *tres_high    = new_rd_shrs(dbgi, block_true, left_high,
yb9976's avatar
yb9976 committed
829
	                                    right, mode);
Matthias Braun's avatar
Matthias Braun committed
830
	ir_node *shift_low    = new_rd_Shr(dbgi, block_true, left_low, right,
yb9976's avatar
yb9976 committed
831
	                                   low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
832
	ir_node *not_shiftval = new_rd_Not(dbgi, block_true, right,
yb9976's avatar
yb9976 committed
833
	                                   low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
834
	ir_node *tconv        = create_conv(block_true, left_high,
yb9976's avatar
yb9976 committed
835
	                                    low_unsigned);
836
	ir_node *one          = new_r_Const_one(irg, low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
837
	ir_node *carry0       = new_rd_Shl(dbgi, block_true, tconv, one,
yb9976's avatar
yb9976 committed
838
	                                   low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
839
	ir_node *carry1       = new_rd_Shl(dbgi, block_true, carry0,
yb9976's avatar
yb9976 committed
840
	                                   not_shiftval, low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
841
	ir_node *tres_low     = new_rd_Or(dbgi, block_true, shift_low, carry1,
yb9976's avatar
yb9976 committed
842
	                                  low_unsigned);
843
844

	/* false block => shift_width > 1word */
Matthias Braun's avatar
Matthias Braun committed
845
846
847
848
	ir_node *false_in[1] = { proj_false };
	ir_node *block_false = new_r_Block(irg, ARRAY_SIZE(false_in), false_in);
	ir_node *fconv       = create_conv(block_false, left_high, low_unsigned);
	ir_node *fres_low    = new_rd_shrs(dbgi, block_false, fconv, right,
yb9976's avatar
yb9976 committed
849
	                                   low_unsigned);
yb9976's avatar
yb9976 committed
850
	int      cnsti       = modulo_shift2 - 1;
Matthias Braun's avatar
Matthias Braun committed
851
852
853
854
855
	ir_node *cnst3       = new_r_Const_long(irg, low_unsigned, cnsti);
	ir_node *fres_high;
	if (new_rd_shrs == new_rd_Shrs) {
		fres_high = new_rd_shrs(dbgi, block_false, left_high, cnst3, mode);
	} else {
856
		fres_high = new_r_Const_null(irg, mode);
857
858
859
	}

	/* patch lower block */
yb9976's avatar
yb9976 committed
860
861
862
	ir_node *lower_in[]    = { new_r_Jmp(block_true), new_r_Jmp(block_false) };
	ir_node *phi_low_in[]  = { tres_low,  fres_low };
	ir_node *phi_high_in[] = { tres_high, fres_high };
863
	set_irn_in(lower_block, ARRAY_SIZE(lower_in), lower_in);
Matthias Braun's avatar
Matthias Braun committed
864
865
866
867
	ir_node *phi_low  = new_r_Phi(lower_block, ARRAY_SIZE(phi_low_in),
	                              phi_low_in, low_unsigned);
	ir_node *phi_high = new_r_Phi(lower_block, ARRAY_SIZE(phi_high_in),
	                              phi_high_in, mode);
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
	ir_set_dw_lowered(node, phi_low, phi_high);
}

static void lower_Shr(ir_node *node, ir_mode *mode)
{
	lower_shr_helper(node, mode, new_rd_Shr);
}

static void lower_Shrs(ir_node *node, ir_mode *mode)
{
	lower_shr_helper(node, mode, new_rd_Shrs);
}

static void lower_Shl(ir_node *node, ir_mode *mode)
{
	ir_node  *right         = get_binop_right(node);
	ir_node  *left          = get_binop_left(node);
	ir_mode  *shr_mode      = get_irn_mode(node);
	unsigned  modulo_shift  = get_mode_modulo_shift(shr_mode);
887
	ir_mode  *low_unsigned  = env.p.word_unsigned;
888
889
890
891
892
893
894
895