lower_dw.c 74.4 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * 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.
 */

Michael Beck's avatar
Michael Beck committed
20
21
/**
 * @file
yb9976's avatar
yb9976 committed
22
 * @brief   Lower double word operations, i.e. 64bit -> 32bit, 32bit -> 16bit etc.
Michael Beck's avatar
Michael Beck committed
23
24
25
 * @date    8.10.2004
 * @author  Michael Beck
 * @version $Id$
26
 */
Matthias Braun's avatar
Matthias Braun committed
27
#include "config.h"
28

29
#include <string.h>
30
#include <stdlib.h>
31
#include <stdbool.h>
32
33
#include <assert.h>

34
#include "error.h"
35
#include "lowering.h"
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "irgmod.h"
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
#include "firmstat.h"
#include "irgwalk.h"
#include "ircons.h"
#include "irflag.h"
#include "irtools.h"
#include "debug.h"
#include "set.h"
#include "pmap.h"
#include "pdeq.h"
Christian Würdig's avatar
Christian Würdig committed
54
#include "irdump.h"
55
#include "array_t.h"
Michael Beck's avatar
Michael Beck committed
56
#include "irpass_t.h"
57
#include "lower_dw.h"
58

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

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

65
66
67
68
/** A map from a method type to its lowered type. */
static pmap *lowered_type;

/** The types for the binop and unop intrinsics. */
Christian Würdig's avatar
Christian Würdig committed
69
static ir_type *binop_tp_u, *binop_tp_s, *unop_tp_u, *unop_tp_s, *shiftop_tp_u, *shiftop_tp_s, *tp_s, *tp_u;
70
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 */
81
	ir_entity     *ent;   /**< the associated entity of this (op, imode, omode) triple */
82
83
} op_mode_entry_t;

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

93
enum lower_flags {
94
95
	MUST_BE_LOWERED = 1,  /**< graph must be lowered */
	CF_CHANGED      = 2,  /**< control flow was changed */
96
97
98
99
100
};

/**
 * The lower environment.
 */
101
102
typedef struct lower_dw_env_t {
	lower64_entry_t **entries;     /**< entries per node */
103
	ir_graph      *irg;
104
	struct obstack obst;           /**< an obstack holding the temporary data */
Matthias Braun's avatar
Matthias Braun committed
105
	ir_type   *l_mtp;              /**< lowered method type of the current method */
106
107
	ir_tarval *tv_mode_bytes;      /**< a tarval containing the number of bytes in the lowered modes */
	ir_tarval *tv_mode_bits;       /**< a tarval containing the number of bits in the lowered modes */
Matthias Braun's avatar
Matthias Braun committed
108
109
110
111
112
113
114
115
116
	pdeq      *waitq;              /**< a wait queue of all nodes that must be handled later */
	ir_node  **lowered_phis;       /**< list of lowered phis */
	pmap      *proj_2_block;       /**< a map from ProjX to its destination blocks */
	ir_mode   *high_signed;        /**< doubleword signed type */
	ir_mode   *high_unsigned;      /**< doubleword unsigned type */
	ir_mode   *low_signed;         /**< word signed type */
	ir_mode   *low_unsigned;       /**< word unsigned type */
	ident     *first_id;           /**< .l for little and .h for big endian */
	ident     *next_id;            /**< .h for little and .l for big endian */
117
118
119
120
121
	const lwrdw_param_t *params;   /**< transformation parameter */
	unsigned flags;                /**< some flags */
	unsigned n_entries;            /**< number of entries */
	ir_type  *value_param_tp;      /**< the old value param type */
} lower_dw_env_t;
122

123
124
125
126
static lower_dw_env_t *env;

static void lower_node(ir_node *node);
static bool mtp_must_be_lowered(ir_type *mtp);
127

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

	key.imode = imode;
	key.omode = omode;
	key.mtd   = NULL;

140
	entry = (conv_tp_entry_t*)set_insert(conv_types, &key, sizeof(key), HASH_PTR(imode) ^ HASH_PTR(omode));
Michael Beck's avatar
Michael Beck committed
141
142
143
	if (! entry->mtd) {
		int n_param = 1, n_res = 1;

144
		if (imode == env->high_signed || imode == env->high_unsigned)
Michael Beck's avatar
Michael Beck committed
145
			n_param = 2;
146
		if (omode == env->high_signed || omode == env->high_unsigned)
Michael Beck's avatar
Michael Beck committed
147
148
149
			n_res = 2;

		/* create a new one */
150
		mtd = new_type_method(n_param, n_res);
Michael Beck's avatar
Michael Beck committed
151
152
153

		/* set param types and result types */
		n_param = 0;
154
		if (imode == env->high_signed) {
155
			set_method_param_type(mtd, n_param++, tp_u);
Michael Beck's avatar
Michael Beck committed
156
			set_method_param_type(mtd, n_param++, tp_s);
157
		} else if (imode == env->high_unsigned) {
Michael Beck's avatar
Michael Beck committed
158
159
			set_method_param_type(mtd, n_param++, tp_u);
			set_method_param_type(mtd, n_param++, tp_u);
Michael Beck's avatar
BugFix:    
Michael Beck committed
160
		} else {
161
			ir_type *tp = get_type_for_mode(imode);
Michael Beck's avatar
Michael Beck committed
162
			set_method_param_type(mtd, n_param++, tp);
163
		}
Michael Beck's avatar
Michael Beck committed
164
165

		n_res = 0;
166
		if (omode == env->high_signed) {
167
			set_method_res_type(mtd, n_res++, tp_u);
Michael Beck's avatar
Michael Beck committed
168
			set_method_res_type(mtd, n_res++, tp_s);
169
		} else if (omode == env->high_unsigned) {
Michael Beck's avatar
Michael Beck committed
170
171
			set_method_res_type(mtd, n_res++, tp_u);
			set_method_res_type(mtd, n_res++, tp_u);
Michael Beck's avatar
BugFix:    
Michael Beck committed
172
		} else {
173
			ir_type *tp = get_type_for_mode(omode);
Michael Beck's avatar
Michael Beck committed
174
			set_method_res_type(mtd, n_res++, tp);
175
		}
Michael Beck's avatar
Michael Beck committed
176
		entry->mtd = mtd;
Michael Beck's avatar
BugFix:    
Michael Beck committed
177
	} else {
Michael Beck's avatar
Michael Beck committed
178
		mtd = entry->mtd;
179
	}
Michael Beck's avatar
Michael Beck committed
180
	return mtd;
181
}
Michael Beck's avatar
Michael Beck committed
182

183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
/**
 * 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)
{
	int i, arity = get_irn_arity(block);
	ir_node **in, *phi;

	assert(nr < arity);

	NEW_ARR_A(ir_node *, in, arity + 1);
	for (i = 0; i < arity; ++i)
		in[i] = get_irn_n(block, i);
	in[i] = cf;

	set_irn_in(block, i + 1, in);

202
	for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) {
203
204
205
206
		for (i = 0; i < arity; ++i)
			in[i] = get_irn_n(phi, i);
		in[i] = in[nr];
		set_irn_in(phi, i + 1, in);
207
208
	}
}
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223

/**
 * 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)
{
	int i, arity = get_irn_arity(block);
	int nr = 0;

	for (i = 0; i < arity; ++i) {
		if (get_irn_n(block, i) == tmpl) {
			nr = i;
			break;
224
225
		}
	}
226
227
	assert(i < arity);
	add_block_cf_input_nr(block, nr, cf);
228
}
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247

/**
 * 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);
248
249
	}
}
250
251

/**
252
253
 * Walker, prepare the node links and determine which nodes need to be lowered
 * at all.
254
 */
255
static void prepare_links(ir_node *node)
256
{
257
258
259
	ir_mode         *mode = get_irn_op_mode(node);
	lower64_entry_t *link;
	int              i;
260

261
	if (mode == env->high_signed || mode == env->high_unsigned) {
262
		unsigned idx = get_irn_idx(node);
263
		/* ok, found a node that will be lowered */
264
		link = OALLOCZ(&env->obst, lower64_entry_t);
265

266
		if (idx >= env->n_entries) {
Michael Beck's avatar
Michael Beck committed
267
			/* enlarge: this happens only for Rotl nodes which is RARELY */
268
			unsigned old   = env->n_entries;
269
			unsigned n_idx = idx + (idx >> 3);
Michael Beck's avatar
Michael Beck committed
270

271
			ARR_RESIZE(lower64_entry_t *, env->entries, n_idx);
272
273
			memset(&env->entries[old], 0, (n_idx - old) * sizeof(env->entries[0]));
			env->n_entries = n_idx;
Michael Beck's avatar
Michael Beck committed
274
		}
275
276
		env->entries[idx] = link;
		env->flags |= MUST_BE_LOWERED;
277
	} else if (is_Conv(node)) {
278
279
280
281
		/* Conv nodes have two modes */
		ir_node *pred = get_Conv_op(node);
		mode = get_irn_mode(pred);

282
		if (mode == env->high_signed || mode == env->high_unsigned) {
Michael Beck's avatar
BugFix:    
Michael Beck committed
283
			/* must lower this node either but don't need a link */
284
			env->flags |= MUST_BE_LOWERED;
285
		}
286
		return;
287
	}
288
289
290
291
292
293
294
295

	if (is_Proj(node)) {
		/* link all Proj nodes to its predecessor:
		   Note that Tuple Proj's and its Projs are linked either. */
		ir_node *pred = get_Proj_pred(node);

		set_irn_link(node, get_irn_link(pred));
		set_irn_link(pred, node);
Michael Beck's avatar
BugFix:    
Michael Beck committed
296
	} else if (is_Phi(node)) {
297
298
		/* link all Phi nodes to its block */
		ir_node *block = get_nodes_block(node);
299
		add_Block_phi(block, node);
Michael Beck's avatar
BugFix:    
Michael Beck committed
300
	} else if (is_Block(node)) {
301
302
303
304
305
		/* fill the Proj -> Block map */
		for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
			ir_node *pred = get_Block_cfgpred(node, i);

			if (is_Proj(pred))
306
				pmap_insert(env->proj_2_block, pred, node);
307
308
309
		}
	}
}
310

311
lower64_entry_t *get_node_entry(ir_node *node)
312
313
314
315
316
317
{
	unsigned idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	return env->entries[idx];
}

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

325
326
327
/**
 * Translate a Constant: create two.
 */
328
static void lower_Const(ir_node *node, ir_mode *mode)
329
{
Matthias Braun's avatar
Matthias Braun committed
330
331
332
333
334
335
336
337
338
	ir_graph  *irg      = get_irn_irg(node);
	dbg_info  *dbg      = get_irn_dbg_info(node);
	ir_mode   *low_mode = env->low_unsigned;
	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);
	ir_tarval *tv_shrs  = tarval_shrs(tv, env->tv_mode_bits);
	ir_tarval *tv_h     = tarval_convert_to(tv_shrs, mode);
	ir_node   *res_high = new_rd_Const(dbg, irg, tv_h);
339

340
	ir_set_dw_lowered(node, res_low, res_high);
341
}
342
343
344
345

/**
 * Translate a Load: create two.
 */
346
static void lower_Load(ir_node *node, ir_mode *mode)
347
{
348
	ir_mode    *low_mode = env->low_unsigned;
349
	ir_graph   *irg = get_irn_irg(node);
350
351
352
353
354
	ir_node    *adr = get_Load_ptr(node);
	ir_node    *mem = get_Load_mem(node);
	ir_node    *low, *high, *proj;
	dbg_info   *dbg;
	ir_node    *block = get_nodes_block(node);
355
	ir_cons_flags volatility = get_Load_volatility(node) == volatility_is_volatile
356
	                         ? cons_volatile : cons_none;
357
358
359

	if (env->params->little_endian) {
		low  = adr;
360
		high = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
Michael Beck's avatar
BugFix:    
Michael Beck committed
361
	} else {
362
		low  = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
363
		high = adr;
364
	}
365
366
367

	/* create two loads */
	dbg  = get_irn_dbg_info(node);
368
	low  = new_rd_Load(dbg, block, mem,  low,  low_mode, volatility);
369
	proj = new_r_Proj(low, mode_M, pn_Load_M);
370
	high = new_rd_Load(dbg, block, proj, high, mode, volatility);
371

372
	ir_set_dw_lowered(node, low, high);
373

374
375
	for (proj = (ir_node*)get_irn_link(node); proj;
	     proj = (ir_node*)get_irn_link(proj)) {
376
377
378
379
380
381
382
383
384
		switch (get_Proj_proj(proj)) {
		case pn_Load_M:         /* Memory result. */
			/* 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;
385
386
387
		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);
388
			ir_set_dw_lowered(proj, res_low, res_high);
389
			break;
390
		}
391
392
		default:
			assert(0 && "unexpected Proj number");
393
		}
394
395
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
396
		mark_irn_visited(proj);
397
398
	}
}
399
400
401
402

/**
 * Translate a Store: create two.
 */
403
static void lower_Store(ir_node *node, ir_mode *mode)
404
{
405
406
407
408
409
410
	ir_graph              *irg;
	ir_node               *block, *adr, *mem;
	ir_node               *low, *high, *proj;
	dbg_info              *dbg;
	ir_node               *value = get_Store_value(node);
	const lower64_entry_t *entry = get_node_entry(value);
411
	ir_cons_flags volatility = get_Store_volatility(node) == volatility_is_volatile
412
	                           ? cons_volatile : cons_none;
Matthias Braun's avatar
Matthias Braun committed
413
	(void) mode;
414
415
416
417
418
419
420

	assert(entry);

	if (! entry->low_word) {
		/* not ready yet, wait */
		pdeq_putr(env->waitq, node);
		return;
421
	}
422

423
	irg = get_irn_irg(node);
424
425
426
427
428
429
	adr = get_Store_ptr(node);
	mem = get_Store_mem(node);
	block = get_nodes_block(node);

	if (env->params->little_endian) {
		low  = adr;
430
		high = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
Michael Beck's avatar
BugFix:    
Michael Beck committed
431
	} else {
432
		low  = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
433
		high = adr;
434
	}
435
436
437

	/* create two Stores */
	dbg = get_irn_dbg_info(node);
438
	low  = new_rd_Store(dbg, block, mem, low,  entry->low_word, volatility);
439
	proj = new_r_Proj(low, mode_M, pn_Store_M);
440
	high = new_rd_Store(dbg, block, proj, high, entry->high_word, volatility);
441

442
	ir_set_dw_lowered(node, low, high);
443

444
445
	for (proj = (ir_node*)get_irn_link(node); proj;
	     proj = (ir_node*)get_irn_link(proj)) {
446
447
448
449
450
451
452
453
454
455
456
		switch (get_Proj_proj(proj)) {
		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;
		default:
			assert(0 && "unexpected Proj number");
457
		}
458
459
460
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
461
462
	}
}
463
464
465

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

Michael Beck's avatar
Michael Beck committed
480
481
482
483
	key.op    = op;
	key.imode = imode;
	key.omode = omode;
	key.ent   = NULL;
484

485
	entry = (op_mode_entry_t*)set_insert(intrinsic_fkt, &key, sizeof(key),
Michael Beck's avatar
Michael Beck committed
486
				HASH_PTR(op) ^ HASH_PTR(imode) ^ (HASH_PTR(omode) << 8));
487
488
	if (! entry->ent) {
		/* create a new one */
Michael Beck's avatar
Michael Beck committed
489
		ent = env->params->create_intrinsic(method, op, imode, omode, env->params->ctx);
490
491
492

		assert(ent && "Intrinsic creator must return an entity");
		entry->ent = ent;
Michael Beck's avatar
BugFix:    
Michael Beck committed
493
	} else {
494
		ent = entry->ent;
495
	}
496
	sym.entity_p = ent;
497
	return new_r_SymConst(env->irg, mode_P_code, sym, symconst_addr_ent);
498
}
499
500
501
502
503
504

/**
 * Translate a Div.
 *
 * Create an intrinsic Call.
 */
505
static void lower_Div(ir_node *node, ir_mode *mode)
506
{
507
508
509
510
511
512
513
514
515
516
517
518
519
	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);
	ir_node         *addr
	    = get_intrinsic_address(mtp, get_irn_op(node), opmode, opmode);
	ir_node         *in[4];
	ir_node         *call;
	ir_node         *resproj;
	const ir_edge_t *edge;
	const ir_edge_t *next;
520

521
522
523
524
525
526
527
528
529
530
531
532
533
	if (env->params->little_endian) {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
	} else {
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
	}
	call    = new_rd_Call(dbgi, block, get_Div_mem(node), addr, 4, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
534
535
	set_irn_pinned(call, get_irn_pinned(node));

536
537
	for (proj = (ir_node*)get_irn_link(node); proj;
	     proj = (ir_node*)get_irn_link(proj)) {
538
539
540
541
		switch (get_Proj_proj(proj)) {
		case pn_Div_M:         /* Memory result. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
542
			set_Proj_proj(proj, pn_Call_M);
543
544
545
546
547
548
			break;
		case pn_Div_X_except:  /* Execution result if exception occurred. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_except);
			break;
549
550
551
552
553
554
555
556
557
558
		case pn_Div_res:
			if (env->params->little_endian) {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
				ir_node *res_high = new_r_Proj(resproj, mode,              1);
				ir_set_dw_lowered(proj, res_low, res_high);
			} else {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
				ir_node *res_high = new_r_Proj(resproj, mode,              0);
				ir_set_dw_lowered(proj, res_low, res_high);
			}
559
560
561
			break;
		default:
			assert(0 && "unexpected Proj number");
562
		}
563
564
565
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		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
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
	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);
	ir_node         *in[4];
	ir_node         *call;
	ir_node         *resproj;
	const ir_edge_t *edge;
	const ir_edge_t *next;

	if (env->params->little_endian) {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
	} else {
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
	}
	call    = new_rd_Call(dbgi, block, get_Mod_mem(node), addr, 4, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
603
604
	set_irn_pinned(call, get_irn_pinned(node));

605
606
	for (proj = (ir_node*)get_irn_link(node); proj;
	     proj = (ir_node*)get_irn_link(proj)) {
607
608
609
610
		switch (get_Proj_proj(proj)) {
		case pn_Mod_M:         /* Memory result. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
611
			set_Proj_proj(proj, pn_Call_M);
612
613
614
615
616
617
			break;
		case pn_Mod_X_except:  /* Execution result if exception occurred. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_except);
			break;
618
619
620
621
622
623
624
625
626
627
		case pn_Mod_res:
			if (env->params->little_endian) {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
				ir_node *res_high = new_r_Proj(resproj, mode,              1);
				ir_set_dw_lowered(proj, res_low, res_high);
			} else {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
				ir_node *res_high = new_r_Proj(resproj, mode,              0);
				ir_set_dw_lowered(proj, res_low, res_high);
			}
628
629
630
			break;
		default:
			assert(0 && "unexpected Proj number");
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
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
	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);
	ir_node  *in[4];
	ir_node  *call;
	ir_node  *resproj;

	if (env->params->little_endian) {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
	} else {
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
	}
	call    = new_rd_Call(dbgi, block, get_irg_no_mem(irg), addr, 4, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
669
	set_irn_pinned(call, get_irn_pinned(node));
670
671
672
673
674
675
676
677
678
679

	if (env->params->little_endian) {
		ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
		ir_node *res_high = new_r_Proj(resproj, mode,              1);
		ir_set_dw_lowered(node, res_low, res_high);
	} else {
		ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
		ir_node *res_high = new_r_Proj(resproj, mode,              0);
		ir_set_dw_lowered(node, res_low, res_high);
	}
680
}
681

Christian Würdig's avatar
Christian Würdig committed
682
683
684
685
686
/**
 * Translate a Shiftop.
 *
 * Create an intrinsic Call.
 */
687
static void lower_Shiftop(ir_node *node, ir_mode *mode)
688
{
689
690
691
692
693
	ir_node               *block      = get_nodes_block(node);
	ir_node               *left       = get_binop_left(node);
	const lower64_entry_t *left_entry = get_node_entry(left);
	ir_node               *right      = get_binop_right(node);
	ir_node               *in[3]      = {
694
695
696
		left_entry->low_word, left_entry->high_word,
		/* it should be safe to conv to low_unsigned */
		new_r_Conv(block, right, env->low_unsigned)
697
698
699
700
701
702
	};
	dbg_info           *dbgi       = get_irn_dbg_info(node);
	ir_graph           *irg        = get_irn_irg(block);
	ir_type            *mtp
		= mode_is_signed(mode) ? shiftop_tp_s : shiftop_tp_u;
	ir_node            *addr
703
		= get_intrinsic_address(mtp, get_irn_op(node), mode, mode);
704
705
706
707
708
	ir_node            *call
		= new_rd_Call(dbgi, block, get_irg_no_mem(irg), addr, 3, in, mtp);
	ir_node            *resproj  = new_r_Proj(call, mode_T, pn_Call_T_result);
	ir_node            *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
	ir_node            *res_high = new_r_Proj(resproj, mode,              1);
Christian Würdig's avatar
Christian Würdig committed
709

710
	set_irn_pinned(call, get_irn_pinned(node));
711
	ir_set_dw_lowered(node, res_low, res_high);
712
}
Christian Würdig's avatar
Christian Würdig committed
713

Michael Beck's avatar
Michael Beck committed
714
715
716
/**
 * Translate a Shr and handle special cases.
 */
717
static void lower_Shr(ir_node *node, ir_mode *mode)
718
{
719
	ir_graph *irg   = get_irn_irg(node);
720
	ir_node  *right = get_Shr_right(node);
Michael Beck's avatar
Michael Beck committed
721
722

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
Matthias Braun's avatar
Matthias Braun committed
723
		ir_tarval *tv = get_Const_tarval(right);
Michael Beck's avatar
Michael Beck committed
724
725

		if (tarval_is_long(tv) &&
726
		    get_tarval_long(tv) >= (long)get_mode_size_bits(mode)) {
727
728
			ir_node *block        = get_nodes_block(node);
			ir_node *left         = get_Shr_left(node);
729
			ir_mode *low_unsigned = env->low_unsigned;
730
			long shf_cnt = get_tarval_long(tv) - get_mode_size_bits(mode);
731
			const lower64_entry_t *left_entry = get_node_entry(left);
732
733
			ir_node *res_low;
			ir_node *res_high;
Michael Beck's avatar
Michael Beck committed
734

735
			left = left_entry->high_word;
Matthias Braun's avatar
Matthias Braun committed
736

737
738
739
			/* convert high word into low_unsigned mode if necessary */
			if (get_irn_mode(left) != low_unsigned)
				left = new_r_Conv(block, left, low_unsigned);
Michael Beck's avatar
Michael Beck committed
740

741
			if (shf_cnt > 0) {
742
743
				ir_node *c = new_r_Const_long(irg, low_unsigned, shf_cnt);
				res_low = new_r_Shr(block, left, c, low_unsigned);
Michael Beck's avatar
BugFix:    
Michael Beck committed
744
			} else {
745
				res_low = left;
746
			}
747
			res_high = new_r_Const(irg, get_mode_null(mode));
748
			ir_set_dw_lowered(node, res_low, res_high);
Michael Beck's avatar
Michael Beck committed
749
750

			return;
751
752
		}
	}
753
	lower_Shiftop(node, mode);
754
}
Michael Beck's avatar
Michael Beck committed
755
756
757
758

/**
 * Translate a Shl and handle special cases.
 */
759
static void lower_Shl(ir_node *node, ir_mode *mode)
760
{
761
	ir_graph *irg   = get_irn_irg(node);
762
	ir_node  *right = get_Shl_right(node);
Michael Beck's avatar
Michael Beck committed
763
764

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
Matthias Braun's avatar
Matthias Braun committed
765
		ir_tarval *tv = get_Const_tarval(right);
Michael Beck's avatar
Michael Beck committed
766

767
768
769
770
771
772
773
774
775
		if (tarval_is_long(tv)) {
			long value = get_tarval_long(tv);
		    if (value >= (long)get_mode_size_bits(mode)) {
				/* simple case: shift above the lower word */
				ir_mode *mode_l;
				ir_node *block = get_nodes_block(node);
				ir_node *left = get_Shl_left(node);
				ir_node *c;
				long shf_cnt = get_tarval_long(tv) - get_mode_size_bits(mode);
776
				const lower64_entry_t *left_entry = get_node_entry(left);
777
778
779
780
781
782
783
784
785
786
787
788
789
790
				ir_node  *res_low;
				ir_node  *res_high;

				left = left_entry->low_word;
				left = new_r_Conv(block, left, mode);

				mode_l = env->low_unsigned;
				if (shf_cnt > 0) {
					c        = new_r_Const_long(irg, mode_l, shf_cnt);
					res_high = new_r_Shl(block, left, c, mode);
				} else {
					res_high = left;
				}
				res_low = new_r_Const(irg, get_mode_null(mode_l));
791
				ir_set_dw_lowered(node, res_low, res_high);
792
793
794
795
796

				return;
			}
			if (value == 1) {
				/* left << 1 == left + left */
797
798
799
				ir_node               *left        = get_binop_left(node);
				const lower64_entry_t *left_entry  = get_node_entry(left);
				ir_node               *in[4]       = {
800
801
802
803
804
805
806
807
808
					left_entry->low_word, left_entry->high_word,
					left_entry->low_word, left_entry->high_word,
				};
				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
809
					= get_intrinsic_address(mtp, op_Add, mode, mode);
810
811
812
813
814
815
				ir_node            *call
					= new_rd_Call(dbgi, block, get_irg_no_mem(irg), addr, 4, in, mtp);
				ir_node            *resproj  = new_r_Proj(call, mode_T, pn_Call_T_result);
				ir_node            *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
				ir_node            *res_high = new_r_Proj(resproj, mode,              1);
				set_irn_pinned(call, get_irn_pinned(node));
816
				ir_set_dw_lowered(node, res_low, res_high);
817
818

				return;
819
820
821
			}
		}
	}
822
	lower_Shiftop(node, mode);
823
}
Michael Beck's avatar
Michael Beck committed
824
825
826
827

/**
 * Translate a Shrs and handle special cases.
 */
828
static void lower_Shrs(ir_node *node, ir_mode *mode)
829
{
830
	ir_graph *irg   = get_irn_irg(node);
831
	ir_node  *right = get_Shrs_right(node);
Michael Beck's avatar
Michael Beck committed
832
833

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
Matthias Braun's avatar
Matthias Braun committed
834
		ir_tarval *tv = get_Const_tarval(right);
Michael Beck's avatar
Michael Beck committed
835
836

		if (tarval_is_long(tv) &&
837
		    get_tarval_long(tv) >= (long)get_mode_size_bits(mode)) {
838
839
			ir_node *block         = get_nodes_block(node);
			ir_node *left          = get_Shrs_left(node);
840
			ir_mode *low_unsigned  = env->low_unsigned;
841
			long     shf_cnt       = get_tarval_long(tv) - get_mode_size_bits(mode);
842
			const lower64_entry_t *left_entry = get_node_entry(left);
843
			ir_node *left_unsigned = left;
844
845
			ir_node *res_low;
			ir_node *res_high;
Michael Beck's avatar
Michael Beck committed
846
847
			ir_node *c;

848
			left = left_entry->high_word;
Michael Beck's avatar
Michael Beck committed
849

850
851
852
853
			/* convert high word into low_unsigned mode if necessary */
			if (get_irn_mode(left_unsigned) != low_unsigned)
				left_unsigned = new_r_Conv(block, left, low_unsigned);

854
			if (shf_cnt > 0) {
855
856
				c       = new_r_Const_long(irg, low_unsigned, shf_cnt);
				res_low = new_r_Shrs(block, left_unsigned, c, low_unsigned);
Michael Beck's avatar
BugFix:    
Michael Beck committed
857
			} else {
858
				res_low = left_unsigned;
859
			}
Michael Beck's avatar
Michael Beck committed
860

861
862
			c        = new_r_Const(irg, get_mode_all_one(low_unsigned));
			res_high = new_r_Shrs(block, left, c, mode);
863
			ir_set_dw_lowered(node, res_low, res_high);
Michael Beck's avatar
Michael Beck committed
864
			return;
865
866
		}
	}
867
	lower_Shiftop(node, mode);
868
}
Michael Beck's avatar
Michael Beck committed
869
870

/**
Michael Beck's avatar
Michael Beck committed
871
 * Rebuild Rotl nodes into Or(Shl, Shr) and prepare all nodes.
Michael Beck's avatar
Michael Beck committed
872
 */
873
static void prepare_links_and_handle_rotl(ir_node *node, void *data)
874
{
875
	(void) data;
Michael Beck's avatar
Michael Beck committed
876
	if (is_Rotl(node)) {
877
878
		ir_mode  *mode = get_irn_op_mode(node);
		ir_node  *right;
879
		ir_node  *left, *shl, *shr, *ornode, *block, *sub, *c;
880
881
882
883
884
		ir_mode  *omode, *rmode;
		ir_graph *irg;
		dbg_info *dbg;
		optimization_state_t state;

885
886
		if (mode != env->high_signed && mode != env->high_unsigned) {
			prepare_links(node);
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
			return;
		}

		/* replace the Rotl(x,y) by an Or(Shl(x,y), Shr(x,64-y)) */
		right = get_Rotl_right(node);
		irg   = get_irn_irg(node);
		dbg   = get_irn_dbg_info(node);
		omode = get_irn_mode(node);
		left  = get_Rotl_left(node);
		block = get_nodes_block(node);
		shl   = new_rd_Shl(dbg, block, left, right, omode);
		rmode = get_irn_mode(right);
		c     = new_r_Const_long(irg, rmode, get_mode_size_bits(omode));
		sub   = new_rd_Sub(dbg, block, c, right, rmode);
		shr   = new_rd_Shr(dbg, block, left, sub, omode);

		/* switch optimization off here, or we will get the Rotl back */
		save_optimization_state(&state);
		set_opt_algebraic_simplification(0);
906
		ornode = new_rd_Or(dbg, block, shl, shr, omode);
907
908
		restore_optimization_state(&state);

909
		exchange(node, ornode);
910
911

		/* do lowering on the new nodes */
912
913
914
915
916
		prepare_links(shl);
		prepare_links(c);
		prepare_links(sub);
		prepare_links(shr);
		prepare_links(ornode);
917
		return;
Michael Beck's avatar
Michael Beck committed
918
	}
919

920
	prepare_links(node);
Michael Beck's avatar
Michael Beck committed
921
}
Michael Beck's avatar
Michael Beck committed
922

923
924
925
926
927
/**
 * Translate an Unop.
 *
 * Create an intrinsic Call.
 */
928
static void lower_unop(ir_node *node, ir_mode *mode)
929
{
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
	ir_node  *op       = get_unop_op(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) ? unop_tp_s : unop_tp_u;
	ir_op    *irop     = get_irn_op(node);
	ir_node  *addr     = get_intrinsic_address(mtp, irop, mode, mode);
	ir_node  *nomem    = get_irg_no_mem(irg);
	ir_node  *in[2];
	ir_node  *call;
	ir_node  *resproj;

	if (env->params->little_endian) {
		in[0] = get_lowered_low(op);
		in[1] = get_lowered_high(op);
	} else {
		in[0] = get_lowered_high(op);
		in[1] = get_lowered_low(op);
	}
	call    = new_rd_Call(dbgi, block, nomem, addr, 2, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
951
	set_irn_pinned(call, get_irn_pinned(node));
952
953
954
955
956
957
958
959
960
961

	if (env->params->little_endian) {
		ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
		ir_node *res_high = new_r_Proj(resproj, mode,              1);
		ir_set_dw_lowered(node, res_low, res_high);
	} else {
		ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
		ir_node *res_high = new_r_Proj(resproj, mode,              0);
		ir_set_dw_lowered(node, res_low, res_high);
	}
962
}
963
964

/**
965
 * Translate a logical binop.
966
 *
967
 * Create two logical binops.
968
 */
969
static void lower_binop_logical(ir_node *node, ir_mode *mode,
970
971
								ir_node *(*constr_rd)(dbg_info *db, ir_node *block, ir_node *op1, ir_node *op2, ir_mode *mode) )
{
972
973
974
975
976
977
978
	ir_node               *left        = get_binop_left(node);
	ir_node               *right       = get_binop_right(node);
	const lower64_entry_t *left_entry  = get_node_entry(left);
	const lower64_entry_t *right_entry = get_node_entry(right);
	dbg_info              *dbgi        = get_irn_dbg_info(node);
	ir_node               *block       = get_nodes_block(node);
	ir_node               *res_low
979
980
		= constr_rd(dbgi, block, left_entry->low_word, right_entry->low_word,
		            env->low_unsigned);
981
	ir_node               *res_high
982
983
		= constr_rd(dbgi, block, left_entry->high_word, right_entry->high_word,
		            mode);
984
	ir_set_dw_lowered(node, res_low, res_high);
985
}
986

987
static void lower_And(ir_node *node, ir_mode *mode)
988
{
989
	lower_binop_logical(node, mode, new_rd_And);
990
}
991

992
static void lower_Or(ir_node *node, ir_mode *mode)
993
{
994
	lower_binop_logical(node, mode, new_rd_Or);
995