lower_dw.c 82.7 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"
18
#include "be.h"
19
#include "constbits.h"
20
#include "dbginfo_t.h"
21
#include "debug.h"
22
#include "ircons_t.h"
23
#include "irdump.h"
24
#include "iredges_t.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"
34
#include "iroptimize.h"
35
#include "iropt_t.h"
36
#include "irprog_t.h"
37
#include "lower_dw.h"
38
39
#include "lowering.h"
#include "panic.h"
Matthias Braun's avatar
Matthias Braun committed
40
#include "pdeq.h"
41
42
43
44
#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;

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

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
	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 */
Matthias Braun's avatar
Matthias Braun committed
109
	deq_t             waitq;         /**< a wait queue of all nodes that must be
110
111
112
113
114
	                                      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
	/* create a new method type */
152
	mtd = new_type_method(n_param, n_res, false, cc_cdecl_set, mtp_no_property);
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
	ir_node  *block    = get_nodes_block(node);
	ir_node *low;
	ir_node *high;
360
	if (env.p.big_endian) {
361
		low  = new_r_Add(block, adr, cnst);
362
		high = adr;
Matthias Braun's avatar
Matthias Braun committed
363
364
	} else {
		low  = adr;
365
		high = new_r_Add(block, adr, cnst);
366
	}
367
368

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

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

382
		switch ((pn_Load)get_Proj_num(proj)) {
Matthias Braun's avatar
Matthias Braun committed
383
		case pn_Load_M:
384
385
386
387
388
389
390
			/* 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
391
392
393
		case pn_Load_X_regular:
			set_Proj_pred(proj, high);
			break;
394
395
396
		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);
397
			ir_set_dw_lowered(proj, res_low, res_high);
398
			break;
399
		}
400
		}
401
402
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
403
		mark_irn_visited(proj);
404
405
	}
}
406
407
408
409

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

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

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

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

446
		switch ((pn_Store)get_Proj_num(proj)) {
447
448
449
450
451
452
453
454
		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
455
456
457
		case pn_Store_X_regular:
			set_Proj_pred(proj, high);
			break;
458
		}
Matthias Braun's avatar
Matthias Braun committed
459
460
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
461
		mark_irn_visited(proj);
462
463
	}
}
464
465
466

/**
 * Return a node containing the address of the intrinsic emulation function.
Michael Beck's avatar
Michael Beck committed
467
468
469
470
471
472
 *
 * @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
473
 */
Michael Beck's avatar
Michael Beck committed
474
static ir_node *get_intrinsic_address(ir_type *method, ir_op *op,
475
                                      ir_mode *imode, ir_mode *omode)
476
{
Matthias Braun's avatar
Matthias Braun committed
477
	op_mode_entry_t key;
Michael Beck's avatar
Michael Beck committed
478
479
480
481
	key.op    = op;
	key.imode = imode;
	key.omode = omode;
	key.ent   = NULL;
482

Matthias Braun's avatar
Matthias Braun committed
483
484
485
486
487
	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) {
488
		/* create a new one */
489
		ent = env.p.create_intrinsic(method, op, imode, omode, env.p.ctx);
490
491
492

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

/**
 * Translate a Div.
 *
 * Create an intrinsic Call.
 */
502
static void lower_Div(ir_node *node, ir_mode *mode)
503
{
504
505
506
507
508
509
	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
510
511
	ir_node  *addr   = get_intrinsic_address(mtp, get_irn_op(node), opmode,
	                                         opmode);
512

Matthias Braun's avatar
Matthias Braun committed
513
	ir_node  *in[4];
514
	if (env.p.big_endian) {
515
516
517
518
		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
519
520
521
522
523
	} 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);
524
	}
Matthias Braun's avatar
Matthias Braun committed
525
526
527
	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);
528
529
	set_irn_pinned(call, get_irn_pinned(node));

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

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

/**
 * Translate a Mod.
 *
 * Create an intrinsic Call.
 */
572
static void lower_Mod(ir_node *node, ir_mode *mode)
573
{
574
575
576
577
578
579
580
	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);
581

Matthias Braun's avatar
Matthias Braun committed
582
	ir_node *in[4];
583
	if (env.p.big_endian) {
584
585
586
587
		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
588
589
590
591
592
	} 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);
593
	}
Matthias Braun's avatar
Matthias Braun committed
594
595
596
	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);
597
598
	set_irn_pinned(call, get_irn_pinned(node));

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

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

/**
637
 * Translate a binop.
638
639
640
 *
 * Create an intrinsic Call.
 */
641
static void lower_binop(ir_node *node, ir_mode *mode)
642
{
643
644
645
646
647
648
649
650
	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
651
	ir_node  *in[4];
652
	if (env.p.big_endian) {
653
654
655
656
		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
657
658
659
660
661
	} 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);
662
	}
Matthias Braun's avatar
Matthias Braun committed
663
664
665
	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);
666
	set_irn_pinned(call, get_irn_pinned(node));
667

668
	if (env.p.big_endian) {
669
670
		ir_node *res_low  = new_r_Proj(resproj, env.p.word_unsigned, 1);
		ir_node *res_high = new_r_Proj(resproj, mode,                0);
671
		ir_set_dw_lowered(node, res_low, res_high);
Matthias Braun's avatar
Matthias Braun committed
672
	} else {
673
674
		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
675
		ir_set_dw_lowered(node, res_low, res_high);
676
	}
677
}
678

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

686
687
688
689
690
691
692
693
694
695
696
697
698
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
699
/**
700
701
 * 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
702
 */
703
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
704
{
705
	move_node(node, to_bl);
Michael Beck's avatar
Michael Beck committed
706

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

	/* recursion ... */
714
	foreach_irn_in(node, i, pred) {
715
716
717
		ir_mode *pred_mode = get_irn_mode(pred);
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
718
		if (needs_lowering(pred_mode)) {
719
720
721
722
723
724
			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);
725
726
727
		}
	}
}
Michael Beck's avatar
Michael Beck committed
728

Matthias Braun's avatar
Matthias Braun committed
729
ir_node *part_block_dw(ir_node *node)
730
{
731
732
733
734
735
	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);
736

737
738
739
740
741
742
	/* 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);

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

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

760
typedef ir_node* (*new_rd_shr_func)(dbg_info *dbgi, ir_node *block,
761
                                    ir_node *left, ir_node *right);
762
763
764

static void lower_shr_helper(ir_node *node, ir_mode *mode,
                             new_rd_shr_func new_rd_shrs)
765
{
766
767
768
769
	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);
770
	ir_mode  *low_unsigned  = env.p.word_unsigned;
771
772
773
774
775
776
777
778
779
	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)
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
780
	    || modulo_shift2 << 1 != modulo_shift) {
781
782
		panic("Shr lowering only implemented for modulo shift shr operations");
	}
783
	if (!is_po2_or_zero(modulo_shift) || !is_po2_or_zero(modulo_shift2)) {
784
785
786
787
788
789
790
		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
791
	ir_node *block = get_nodes_block(node);
792

793
794
	/* if the right operand is a 64bit value, we're only interested in the
	 * lower word */
795
796
	assert(!mode_is_signed(get_irn_mode(right)));
	if (needs_lowering(get_irn_mode(right))) {
797
798
799
800
801
		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
802

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

Michael Beck's avatar
Michael Beck committed
807
	/* add a Cmp to test if highest bit is set <=> whether we shift more
808
	 * than half the word width */
Matthias Braun's avatar
Matthias Braun committed
809
	ir_node *cnst  = new_r_Const_long(irg, low_unsigned, modulo_shift2);
810
	ir_node *andn  = new_r_And(block, right, cnst);
811
	ir_node *cnst2 = new_r_Const_null(irg, low_unsigned);
Matthias Braun's avatar
Matthias Braun committed
812
813
814
815
	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);
816
817

	/* the true block => shift_width < 1word */
Matthias Braun's avatar
Matthias Braun committed
818
819
820
821
822
823
824
825
	/* 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);
826
827
	ir_node *tres_high    = new_rd_shrs(dbgi, block_true, left_high, right);
	ir_node *shift_low    = new_rd_Shr(dbgi, block_true, left_low, right);
828
	ir_node *not_shiftval = new_rd_Not(dbgi, block_true, right);
Matthias Braun's avatar
Matthias Braun committed
829
	ir_node *tconv        = create_conv(block_true, left_high,
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
830
	                                    low_unsigned);
831
	ir_node *one          = new_r_Const_one(irg, low_unsigned);
832
833
	ir_node *carry0       = new_rd_Shl(dbgi, block_true, tconv, one);
	ir_node *carry1       = new_rd_Shl(dbgi, block_true, carry0, not_shiftval);
834
	ir_node *tres_low     = new_rd_Or(dbgi, block_true, shift_low, carry1);
835
836

	/* false block => shift_width > 1word */
Matthias Braun's avatar
Matthias Braun committed
837
838
839
	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);
840
	ir_node *fres_low    = new_rd_shrs(dbgi, block_false, fconv, right);
841
	int      cnsti       = modulo_shift2 - 1;
Matthias Braun's avatar
Matthias Braun committed
842
843
844
	ir_node *cnst3       = new_r_Const_long(irg, low_unsigned, cnsti);
	ir_node *fres_high;
	if (new_rd_shrs == new_rd_Shrs) {
845
		fres_high = new_rd_shrs(dbgi, block_false, left_high, cnst3);
Matthias Braun's avatar
Matthias Braun committed
846
	} else {
847
		fres_high = new_r_Const_null(irg, mode);
848
849
850
	}

	/* patch lower block */
851
852
853
	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 };
854
	set_irn_in(lower_block, ARRAY_SIZE(lower_in), lower_in);
Matthias Braun's avatar
Matthias Braun committed
855
856
857
858
	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);
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
	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);
878
	ir_mode  *low_unsigned  = env.p.word_unsigned;
879
880
881
882
883
884
885
886
887
888
	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);
	ir_node  *lower_block   = get_nodes_block(node);

	/* this version is optimized for modulo shift architectures
	 * (and can't handle anything else) */
	if (modulo_shift != get_mode_size_bits(shr_mode)