ia32_optimize.c 41.4 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/**
Christian Würdig's avatar
Christian Würdig committed
2
3
4
5
6
 * Project:     libFIRM
 * File name:   ir/be/ia32/ia32_optimize.c
 * Purpose:     Implements several optimizations for IA32
 * Author:      Christian Wuerdig
 * CVS-ID:      $Id$
7
 * Copyright:   (c) 2006 Universitaet Karlsruhe
Christian Würdig's avatar
Christian Würdig committed
8
9
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */
10
#ifdef HAVE_CONFIG_H
11
#include "config.h"
12
13
14
15
16
17
#endif

#include "irnode.h"
#include "irprog_t.h"
#include "ircons.h"
#include "firm_types.h"
Christian Würdig's avatar
Christian Würdig committed
18
19
20
#include "iredges.h"
#include "tv.h"
#include "irgmod.h"
21
#include "irgwalk.h"
Christian Würdig's avatar
Christian Würdig committed
22
#include "height.h"
23
#include "irbitset.h"
Christian Würdig's avatar
Christian Würdig committed
24

Christian Würdig's avatar
Christian Würdig committed
25
26
#include "../be_t.h"
#include "../beabi.h"
Christian Würdig's avatar
Christian Würdig committed
27
28
#include "../benode_t.h"
#include "../besched_t.h"
29
30
31

#include "ia32_new_nodes.h"
#include "bearch_ia32_t.h"
Christian Würdig's avatar
Christian Würdig committed
32
#include "gen_ia32_regalloc_if.h"     /* the generated interface (register type and class defenitions) */
Christian Würdig's avatar
Christian Würdig committed
33
#include "ia32_transform.h"
Christian Würdig's avatar
Christian Würdig committed
34
#include "ia32_dbg_stat.h"
Christian Würdig's avatar
Christian Würdig committed
35
#include "ia32_util.h"
36

37
38
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

39
40
#define AGGRESSIVE_AM

Christian Würdig's avatar
Christian Würdig committed
41
typedef enum {
42
43
44
45
	IA32_AM_CAND_NONE  = 0,  /**< no addressmode possible with irn inputs */
	IA32_AM_CAND_LEFT  = 1,  /**< addressmode possible with left input */
	IA32_AM_CAND_RIGHT = 2,  /**< addressmode possible with right input */
	IA32_AM_CAND_BOTH  = 3   /**< addressmode possible with both inputs */
Christian Würdig's avatar
Christian Würdig committed
46
47
} ia32_am_cand_t;

48
typedef int is_op_func_t(const ir_node *n);
49
typedef ir_node *load_func_t(dbg_info *db, ir_graph *irg, ir_node *block, ir_node *base, ir_node *index, ir_node *mem);
50

Michael Beck's avatar
Michael Beck committed
51
52
53
/**
 * checks if a node represents the NOREG value
 */
54
55
static INLINE int be_is_NoReg(ia32_code_gen_t *cg, const ir_node *irn) {
	return irn == cg->noreg_gp || irn == cg->noreg_xmm || irn == cg->noreg_vfp;
56
57
}

58
59
60
61
62
63
void ia32_pre_transform_phase(ia32_code_gen_t *cg) {
	/*
		We need to transform the consts twice:
		- the psi condition tree transformer needs existing constants to be ia32 constants
		- the psi condition tree transformer inserts new firm constants which need to be transformed
	*/
64
65
66
	//ia32_transform_all_firm_consts(cg);
	irg_walk_graph(cg->irg, NULL, ia32_transform_psi_cond_tree, cg);
	//ia32_transform_all_firm_consts(cg);
67
}
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/********************************************************************************************************
 *  _____                _           _         ____        _   _           _          _   _
 * |  __ \              | |         | |       / __ \      | | (_)         (_)        | | (_)
 * | |__) |__  ___ _ __ | |__   ___ | | ___  | |  | |_ __ | |_ _ _ __ ___  _ ______ _| |_ _  ___  _ __
 * |  ___/ _ \/ _ \ '_ \| '_ \ / _ \| |/ _ \ | |  | | '_ \| __| | '_ ` _ \| |_  / _` | __| |/ _ \| '_ \
 * | |  |  __/  __/ |_) | | | | (_) | |  __/ | |__| | |_) | |_| | | | | | | |/ / (_| | |_| | (_) | | | |
 * |_|   \___|\___| .__/|_| |_|\___/|_|\___|  \____/| .__/ \__|_|_| |_| |_|_/___\__,_|\__|_|\___/|_| |_|
 *                | |                               | |
 *                |_|                               |_|
 ********************************************************************************************************/

/**
 * NOTE: THESE PEEPHOLE OPTIMIZATIONS MUST BE CALLED AFTER SCHEDULING AND REGISTER ALLOCATION.
 */

84
85
86
87
88
89
90
91
92
93
94
95
static int ia32_const_equal(const ir_node *n1, const ir_node *n2) {
	if(get_ia32_immop_type(n1) != get_ia32_immop_type(n2))
		return 0;

	if(get_ia32_immop_type(n1) == ia32_ImmConst) {
		return get_ia32_Immop_tarval(n1) == get_ia32_Immop_tarval(n2);
	} else if(get_ia32_immop_type(n1) == ia32_ImmSymConst) {
		return get_ia32_Immop_symconst(n1) == get_ia32_Immop_symconst(n2);
	}

	assert(get_ia32_immop_type(n1) == ia32_ImmNone);
	return 1;
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
}

/**
 * Checks for potential CJmp/CJmpAM optimization candidates.
 */
static ir_node *ia32_determine_cjmp_cand(ir_node *irn, is_op_func_t *is_op_func) {
	ir_node *cand = NULL;
	ir_node *prev = sched_prev(irn);

	if (is_Block(prev)) {
		if (get_Block_n_cfgpreds(prev) == 1)
			prev = get_Block_cfgpred(prev, 0);
		else
			prev = NULL;
	}

	/* The predecessor must be a ProjX. */
	if (prev && is_Proj(prev) && get_irn_mode(prev) == mode_X) {
		prev = get_Proj_pred(prev);

		if (is_op_func(prev))
			cand = prev;
	}

	return cand;
}

static int is_TestJmp_cand(const ir_node *irn) {
	return is_ia32_TestJmp(irn) || is_ia32_And(irn);
}

/**
 * Checks if two consecutive arguments of cand matches
 * the two arguments of irn (TestJmp).
 */
static int is_TestJmp_replacement(ir_node *cand, ir_node *irn) {
	ir_node *in1       = get_irn_n(irn, 0);
	ir_node *in2       = get_irn_n(irn, 1);
	int      i, n      = get_irn_arity(cand);
	int      same_args = 0;

	for (i = 0; i < n - 1; i++) {
		if (get_irn_n(cand, i)     == in1 &&
			get_irn_n(cand, i + 1) == in2)
		{
			same_args = 1;
			break;
		}
	}

146
147
	if (!same_args)
		return 0;
148

149
	return ia32_const_equal(cand, irn);
150
151
152
153
154
155
156
157
158
159
160
161
162
}

/**
 * Tries to replace a TestJmp by a CJmp or CJmpAM (in case of And)
 */
static void ia32_optimize_TestJmp(ir_node *irn, ia32_code_gen_t *cg) {
	ir_node *cand    = ia32_determine_cjmp_cand(irn, is_TestJmp_cand);
	int      replace = 0;

	/* we found a possible candidate */
	replace = cand ? is_TestJmp_replacement(cand, irn) : 0;

	if (replace) {
163
		DBG((dbg, LEVEL_1, "replacing %+F by ", irn));
164
165
166
167
168
169

		if (is_ia32_And(cand))
			set_irn_op(irn, op_ia32_CJmpAM);
		else
			set_irn_op(irn, op_ia32_CJmp);

170
		DB((dbg, LEVEL_1, "%+F\n", irn));
171
172
173
174
175
176
177
178
179
180
181
	}
}

static int is_CondJmp_cand(const ir_node *irn) {
	return is_ia32_CondJmp(irn) || is_ia32_Sub(irn);
}

/**
 * Checks if the arguments of cand are the same of irn.
 */
static int is_CondJmp_replacement(ir_node *cand, ir_node *irn) {
182
	int i, arity;
183

184
185
	arity = get_irn_arity(cand);
	for (i = 0; i < arity; i++) {
Michael Beck's avatar
Michael Beck committed
186
		if (get_irn_n(cand, i) != get_irn_n(irn, i)) {
187
			return 0;
188
189
190
		}
	}

191
	return ia32_const_equal(cand, irn);
192
193
194
195
196
197
198
199
200
201
202
203
204
}

/**
 * Tries to replace a CondJmp by a CJmpAM
 */
static void ia32_optimize_CondJmp(ir_node *irn, ia32_code_gen_t *cg) {
	ir_node *cand    = ia32_determine_cjmp_cand(irn, is_CondJmp_cand);
	int      replace = 0;

	/* we found a possible candidate */
	replace = cand ? is_CondJmp_replacement(cand, irn) : 0;

	if (replace) {
205
		DBG((dbg, LEVEL_1, "replacing %+F by ", irn));
Christian Würdig's avatar
Christian Würdig committed
206
		DBG_OPT_CJMP(irn);
207

Michael Beck's avatar
Michael Beck committed
208
		set_irn_op(irn, op_ia32_CJmpAM);
209

210
		DB((dbg, LEVEL_1, "%+F\n", irn));
211
212
213
	}
}

214
215
// only optimize up to 48 stores behind IncSPs
#define MAXPUSH_OPTIMIZE	48
216
217

/**
218
 * Tries to create pushs from IncSP,Store combinations
219
 */
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
static void ia32_create_Pushs(ir_node *irn, ia32_code_gen_t *cg) {
	int i;
	int offset;
	ir_node *node;
	ir_node *stores[MAXPUSH_OPTIMIZE];
	ir_node *block = get_nodes_block(irn);
	ir_graph *irg = cg->irg;
	ir_node *curr_sp;
	ir_mode *spmode = get_irn_mode(irn);

	memset(stores, 0, sizeof(stores));

	assert(be_is_IncSP(irn));

	offset = be_get_IncSP_offset(irn);
Matthias Braun's avatar
bugfix    
Matthias Braun committed
235
	if(offset < 4)
236
237
238
239
240
241
242
243
244
245
		return;

	/*
	 * We first walk the schedule after the IncSP node as long as we find
	 * suitable stores that could be transformed to a push.
	 * We save them into the stores array which is sorted by the frame offset/4
	 * attached to the node
	 */
	for(node = sched_next(irn); !sched_is_end(node); node = sched_next(node)) {
		ir_node *mem;
246
		int offset;
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
		int storeslot;

		// it has to be a store
		if(!is_ia32_Store(node))
			break;

		// it has to use our sp value
		if(get_irn_n(node, 0) != irn)
			continue;
		// store has to be attached to NoMem
		mem = get_irn_n(node, 3);
		if(!is_NoMem(mem)) {
			continue;
		}

		if( (get_ia32_am_flavour(node) & ia32_am_IS) != 0)
			break;

265
		offset = get_ia32_am_offs_int(node);
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284

		storeslot = offset / 4;
		if(storeslot >= MAXPUSH_OPTIMIZE)
			continue;

		// storing into the same slot twice is bad (and shouldn't happen...)
		if(stores[storeslot] != NULL)
			break;

		// storing at half-slots is bad
		if(offset % 4 != 0)
			break;

		stores[storeslot] = node;
	}

	curr_sp = get_irn_n(irn, 0);

	// walk the stores in inverse order and create pushs for them
Matthias Braun's avatar
bugfix    
Matthias Braun committed
285
286
287
288
289
290
	i = (offset / 4) - 1;
	if(i >= MAXPUSH_OPTIMIZE) {
		i = MAXPUSH_OPTIMIZE - 1;
	}

	for( ; i >= 0; --i) {
291
292
		const arch_register_t *spreg;
		ir_node *push;
293
		ir_node *val, *mem, *mem_proj;
294
		ir_node *store = stores[i];
295
		ir_node *noreg = ia32_new_NoReg_gp(cg);
296

Matthias Braun's avatar
bugfix    
Matthias Braun committed
297
298
299
		if(store == NULL || is_Bad(store))
			break;

300
301
302
303
304
		val = get_irn_n(store, 2);
		mem = get_irn_n(store, 3);
		spreg = arch_get_irn_register(cg->arch_env, curr_sp);

		// create a push
305
		push = new_rd_ia32_Push(NULL, irg, block, noreg, noreg, val, curr_sp, mem);
306
307
308
309

		set_ia32_am_support(push, ia32_am_Source);
		copy_ia32_Immop_attr(push, store);

310
311
312
313
314
315
316
		sched_add_before(irn, push);

		// create stackpointer proj
		curr_sp = new_r_Proj(irg, block, push, spmode, pn_ia32_Push_stack);
		arch_set_irn_register(cg->arch_env, curr_sp, spreg);
		sched_add_before(irn, curr_sp);

317
318
319
320
321
322
		// create memory proj
		mem_proj = new_r_Proj(irg, block, push, mode_M, pn_ia32_Push_M);
		sched_add_before(irn, mem_proj);

		// use the memproj now
		exchange(store, mem_proj);
323

324
		// we can remove the store now
325
		sched_remove(store);
Matthias Braun's avatar
bugfix    
Matthias Braun committed
326
327

		offset -= 4;
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
	}

	be_set_IncSP_offset(irn, offset);

	// can we remove the IncSP now?
	if(offset == 0) {
		const ir_edge_t *edge, *next;

		foreach_out_edge_safe(irn, edge, next) {
			ir_node *arg = get_edge_src_irn(edge);
			int pos = get_edge_src_pos(edge);

			set_irn_n(arg, pos, curr_sp);
		}

		set_irn_n(irn, 0, new_Bad());
344
		sched_remove(irn);
345
346
347
	} else {
		set_irn_n(irn, 0, curr_sp);
	}
348
349
}

350
#if 0
351
/**
352
 * Tries to optimize two following IncSP.
353
 */
354
355
356
357
358
359
static void ia32_optimize_IncSP(ir_node *irn, ia32_code_gen_t *cg) {
	ir_node *prev = be_get_IncSP_pred(irn);
	int real_uses = get_irn_n_edges(prev);

	if (be_is_IncSP(prev) && real_uses == 1) {
		/* first IncSP has only one IncSP user, kill the first one */
360
361
		int prev_offs = be_get_IncSP_offset(prev);
		int curr_offs = be_get_IncSP_offset(irn);
362

363
		be_set_IncSP_offset(prev, prev_offs + curr_offs);
Christian Würdig's avatar
Christian Würdig committed
364
365
366

		/* Omit the optimized IncSP */
		be_set_IncSP_pred(irn, be_get_IncSP_pred(prev));
367
368

		set_irn_n(prev, 0, new_Bad());
369
		sched_remove(prev);
370
	}
371
}
372
#endif
373
374
375
376

/**
 * Performs Peephole Optimizations.
 */
377
static void ia32_peephole_optimize_node(ir_node *irn, void *env) {
378
379
	ia32_code_gen_t *cg = env;

380
381
382
383
384
385
386
	/* AMD CPUs want explicit compare before conditional jump  */
	if (! ARCH_AMD(cg->opt_arch)) {
		if (is_ia32_TestJmp(irn))
			ia32_optimize_TestJmp(irn, cg);
		else if (is_ia32_CondJmp(irn))
			ia32_optimize_CondJmp(irn, cg);
	}
387
388
389
390

	if (be_is_IncSP(irn)) {
		// optimize_IncSP doesn't respect dependency edges yet...
		//ia32_optimize_IncSP(irn, cg);
391

392
393
		if (cg->opt & IA32_OPT_PUSHARGS)
			ia32_create_Pushs(irn, cg);
394
	}
395
396
}

397
398
399
void ia32_peephole_optimization(ir_graph *irg, ia32_code_gen_t *cg) {
	irg_walk_graph(irg, ia32_peephole_optimize_node, NULL, cg);
}
400

Christian Würdig's avatar
Christian Würdig committed
401
402
403
404
405
406
407
408
409
410
/******************************************************************
 *              _     _                   __  __           _
 *     /\      | |   | |                 |  \/  |         | |
 *    /  \   __| | __| |_ __ ___  ___ ___| \  / | ___   __| | ___
 *   / /\ \ / _` |/ _` | '__/ _ \/ __/ __| |\/| |/ _ \ / _` |/ _ \
 *  / ____ \ (_| | (_| | | |  __/\__ \__ \ |  | | (_) | (_| |  __/
 * /_/    \_\__,_|\__,_|_|  \___||___/___/_|  |_|\___/ \__,_|\___|
 *
 ******************************************************************/

Christian Würdig's avatar
Christian Würdig committed
411
412
413
414
415
typedef struct {
	ia32_code_gen_t *cg;
	heights_t       *h;
} ia32_am_opt_env_t;

416
static int node_is_ia32_comm(const ir_node *irn) {
Christian Würdig's avatar
Christian Würdig committed
417
	return is_ia32_irn(irn) ? is_ia32_commutative(irn) : 0;
Christian Würdig's avatar
Christian Würdig committed
418
419
}

420
421
422
423
424
425
426
427
428
429
430
static int ia32_get_irn_n_edges(const ir_node *irn) {
	const ir_edge_t *edge;
	int cnt = 0;

	foreach_out_edge(irn, edge) {
		cnt++;
	}

	return cnt;
}

Christian Würdig's avatar
Christian Würdig committed
431
/**
Christian Würdig's avatar
Christian Würdig committed
432
433
434
435
436
 * Determines if pred is a Proj and if is_op_func returns true for it's predecessor.
 *
 * @param pred       The node to be checked
 * @param is_op_func The check-function
 * @return 1 if conditions are fulfilled, 0 otherwise
Christian Würdig's avatar
Christian Würdig committed
437
 */
438
static int pred_is_specific_node(const ir_node *pred, is_op_func_t *is_op_func) {
439
	return is_op_func(pred);
Christian Würdig's avatar
Christian Würdig committed
440
441
}

Christian Würdig's avatar
Christian Würdig committed
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
/**
 * Determines if pred is a Proj and if is_op_func returns true for it's predecessor
 * and if the predecessor is in block bl.
 *
 * @param bl         The block
 * @param pred       The node to be checked
 * @param is_op_func The check-function
 * @return 1 if conditions are fulfilled, 0 otherwise
 */
static int pred_is_specific_nodeblock(const ir_node *bl, const ir_node *pred,
	int (*is_op_func)(const ir_node *n))
{
	if (is_Proj(pred)) {
		pred = get_Proj_pred(pred);
		if ((bl == get_nodes_block(pred)) && is_op_func(pred)) {
			return 1;
		}
	}

	return 0;
}

464
/**
465
466
467
 * Checks if irn is a candidate for address calculation. We avoid transforming
 * adds to leas if they have a load as pred, because then we can use AM mode
 * for the add later.
468
469
470
471
 *
 * - none of the operand must be a Load  within the same block OR
 * - all Loads must have more than one user                    OR
 *
Christian Würdig's avatar
Christian Würdig committed
472
473
474
475
 * @param block   The block the Loads must/mustnot be in
 * @param irn     The irn to check
 * return 1 if irn is a candidate, 0 otherwise
 */
Matthias Braun's avatar
fix    
Matthias Braun committed
476
static int is_addr_candidate(const ir_node *irn) {
477
#ifndef AGGRESSIVE_AM
Matthias Braun's avatar
fix    
Matthias Braun committed
478
	const ir_node *block = get_nodes_block(irn);
479
480
	ir_node *left, *right;
	int      n;
Christian Würdig's avatar
Christian Würdig committed
481
482
483
484

	left  = get_irn_n(irn, 2);
	right = get_irn_n(irn, 3);

485
486
487
488
489
	if (pred_is_specific_nodeblock(block, left, is_ia32_Ld)) {
		n         = ia32_get_irn_n_edges(left);
		/* load with only one user: don't create LEA */
		if(n == 1)
			return 0;
Christian Würdig's avatar
Christian Würdig committed
490
491
	}

492
493
494
495
	if (pred_is_specific_nodeblock(block, right, is_ia32_Ld)) {
		n         = ia32_get_irn_n_edges(right);
		if(n == 1)
			return 0;
Christian Würdig's avatar
Christian Würdig committed
496
	}
497
#endif
Christian Würdig's avatar
Christian Würdig committed
498

499
	return 1;
Christian Würdig's avatar
Christian Würdig committed
500
501
502
503
504
}

/**
 * Checks if irn is a candidate for address mode.
 *
505
506
507
508
509
 * address mode (AM):
 * - at least one operand has to be a Load within the same block AND
 * - the load must not have other users than the irn             AND
 * - the irn must not have a frame entity set
 *
510
 * @param cg          The ia32 code generator
Christian Würdig's avatar
Christian Würdig committed
511
512
 * @param h           The height information of the irg
 * @param block       The block the Loads must/mustnot be in
513
 * @param irn         The irn to check
Christian Würdig's avatar
Christian Würdig committed
514
 * return 0 if irn is no candidate, 1 if left load can be used, 2 if right one, 3 for both
515
 */
516
static ia32_am_cand_t is_am_candidate(ia32_code_gen_t *cg, heights_t *h, const ir_node *block, ir_node *irn) {
Christian Würdig's avatar
Christian Würdig committed
517
	ir_node *in, *load, *other, *left, *right;
Matthias Braun's avatar
Matthias Braun committed
518
	int      is_cand = 0, cand;
519
	int arity;
520

521
	if (is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn) || is_ia32_vfild(irn) || is_ia32_vfist(irn) ||
522
		is_ia32_GetST0(irn) || is_ia32_SetST0(irn) || is_ia32_xStoreSimple(irn))
Christian Würdig's avatar
Christian Würdig committed
523
524
525
		return 0;

	left  = get_irn_n(irn, 2);
526
527
528
	arity = get_irn_arity(irn);
	assert(arity == 5 || arity == 4);
	if(arity == 5) {
529
530
531
532
533
534
		/* binary op */
		right = get_irn_n(irn, 3);
	} else {
		/* unary op */
		right = left;
	}
Christian Würdig's avatar
Christian Würdig committed
535
536

	in = left;
Christian Würdig's avatar
Christian Würdig committed
537

538
	if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
539
#ifndef AGGRESSIVE_AM
Matthias Braun's avatar
Matthias Braun committed
540
		int n;
Christian Würdig's avatar
Christian Würdig committed
541
		n         = ia32_get_irn_n_edges(in);
Christian Würdig's avatar
Christian Würdig committed
542
		is_cand   = (n == 1) ? 1 : is_cand;  /* load with more than one user: no AM */
543
544
#else
		is_cand   = 1;
545
#endif
Christian Würdig's avatar
Christian Würdig committed
546
547
548
549

		load  = get_Proj_pred(in);
		other = right;

550
551
552
553
		/* 8bit Loads are not supported (for binary ops),
		 * they cannot be used with every register */
		if (get_irn_arity(irn) != 4 && get_mode_size_bits(get_ia32_ls_mode(load)) < 16) {
			assert(get_irn_arity(irn) == 5);
554
			is_cand = 0;
555
		}
556

Christian Würdig's avatar
Christian Würdig committed
557
		/* If there is a data dependency of other irn from load: cannot use AM */
558
		if (is_cand && get_nodes_block(other) == block) {
559
560
			other   = skip_Proj(other);
			is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
561
562
			/* this could happen in loops */
			is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
563
		}
564
565
	}

Christian Würdig's avatar
Christian Würdig committed
566
567
568
	cand    = is_cand ? IA32_AM_CAND_LEFT : IA32_AM_CAND_NONE;
	in      = right;
	is_cand = 0;
Christian Würdig's avatar
Christian Würdig committed
569

570
	if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
571
#ifndef AGGRESSIVE_AM
Matthias Braun's avatar
Matthias Braun committed
572
		int n;
Christian Würdig's avatar
Christian Würdig committed
573
		n         = ia32_get_irn_n_edges(in);
Christian Würdig's avatar
Christian Würdig committed
574
		is_cand   = (n == 1) ? 1 : is_cand;  /* load with more than one user: no AM */
575
576
#else
		is_cand = 1;
577
#endif
Christian Würdig's avatar
Christian Würdig committed
578
579
580
581

		load  = get_Proj_pred(in);
		other = left;

582
583
584
585
		/* 8bit Loads are not supported, they cannot be used with every register */
		if (get_mode_size_bits(get_ia32_ls_mode(load)) < 16)
			is_cand = 0;

Christian Würdig's avatar
Christian Würdig committed
586
		/* If there is a data dependency of other irn from load: cannot use load */
587
		if (is_cand && get_nodes_block(other) == block) {
588
589
			other   = skip_Proj(other);
			is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
590
591
			/* this could happen in loops */
			is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
592
		}
593
594
	}

Christian Würdig's avatar
Christian Würdig committed
595
	cand = is_cand ? (cand | IA32_AM_CAND_RIGHT) : cand;
596

Christian Würdig's avatar
Christian Würdig committed
597
598
	/* if the irn has a frame entity: we do not use address mode */
	return get_ia32_frame_ent(irn) ? IA32_AM_CAND_NONE : cand;
599
600
601
602
603
604
605
606
607
}

/**
 * Compares the base and index addr and the load/store entities
 * and returns 1 if they are equal.
 */
static int load_store_addr_is_equal(const ir_node *load, const ir_node *store,
									const ir_node *addr_b, const ir_node *addr_i)
{
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
	if(get_irn_n(load, 0) != addr_b)
		return 0;
	if(get_irn_n(load, 1) != addr_i)
		return 0;

	if(get_ia32_frame_ent(load) != get_ia32_frame_ent(store))
		return 0;

	if(get_ia32_am_sc(load) != get_ia32_am_sc(store))
		return 0;
	if(is_ia32_am_sc_sign(load) != is_ia32_am_sc_sign(store))
		return 0;
	if(get_ia32_am_offs_int(load) != get_ia32_am_offs_int(store))
		return 0;
	if(get_ia32_ls_mode(load) != get_ia32_ls_mode(store))
		return 0;

	return 1;
626
627
}

Christian Würdig's avatar
Christian Würdig committed
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
typedef enum _ia32_take_lea_attr {
	IA32_LEA_ATTR_NONE  = 0,
	IA32_LEA_ATTR_BASE  = (1 << 0),
	IA32_LEA_ATTR_INDEX = (1 << 1),
	IA32_LEA_ATTR_OFFS  = (1 << 2),
	IA32_LEA_ATTR_SCALE = (1 << 3),
	IA32_LEA_ATTR_AMSC  = (1 << 4),
	IA32_LEA_ATTR_FENT  = (1 << 5)
} ia32_take_lea_attr;

/**
 * Decides if we have to keep the LEA operand or if we can assimilate it.
 */
static int do_new_lea(ir_node *irn, ir_node *base, ir_node *index, ir_node *lea,
		int have_am_sc, ia32_code_gen_t *cg)
{
644
645
646
647
648
	ir_entity *irn_ent  = get_ia32_frame_ent(irn);
	ir_entity *lea_ent  = get_ia32_frame_ent(lea);
	int        ret_val  = 0;
	int        is_noreg_base  = be_is_NoReg(cg, base);
	int        is_noreg_index = be_is_NoReg(cg, index);
Christian Würdig's avatar
Christian Würdig committed
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
	ia32_am_flavour_t am_flav = get_ia32_am_flavour(lea);

	/* If the Add and the LEA both have a different frame entity set: keep */
	if (irn_ent && lea_ent && (irn_ent != lea_ent))
		return IA32_LEA_ATTR_NONE;
	else if (! irn_ent && lea_ent)
		ret_val |= IA32_LEA_ATTR_FENT;

	/* If the Add and the LEA both have already an address mode symconst: keep */
	if (have_am_sc && get_ia32_am_sc(lea))
		return IA32_LEA_ATTR_NONE;
	else if (get_ia32_am_sc(lea))
		ret_val |= IA32_LEA_ATTR_AMSC;

	/* Check the different base-index combinations */

	if (! is_noreg_base && ! is_noreg_index) {
		/* Assimilate if base is the lea and the LEA is just a Base + Offset calculation */
		if ((base == lea) && ! (am_flav & ia32_I ? 1 : 0)) {
			if (am_flav & ia32_O)
				ret_val |= IA32_LEA_ATTR_OFFS;

			ret_val |= IA32_LEA_ATTR_BASE;
		}
		else
			return IA32_LEA_ATTR_NONE;
	}
	else if (! is_noreg_base && is_noreg_index) {
		/* Base is set but index not */
		if (base == lea) {
			/* Base points to LEA: assimilate everything */
			if (am_flav & ia32_O)
				ret_val |= IA32_LEA_ATTR_OFFS;
			if (am_flav & ia32_S)
				ret_val |= IA32_LEA_ATTR_SCALE;
			if (am_flav & ia32_I)
				ret_val |= IA32_LEA_ATTR_INDEX;

			ret_val |= IA32_LEA_ATTR_BASE;
		}
		else if (am_flav & ia32_B ? 0 : 1) {
			/* Base is not the LEA but the LEA is an index only calculation: assimilate */
			if (am_flav & ia32_O)
				ret_val |= IA32_LEA_ATTR_OFFS;
			if (am_flav & ia32_S)
				ret_val |= IA32_LEA_ATTR_SCALE;

			ret_val |= IA32_LEA_ATTR_INDEX;
		}
		else
			return IA32_LEA_ATTR_NONE;
	}
	else if (is_noreg_base && ! is_noreg_index) {
		/* Index is set but not base */
		if (index == lea) {
			/* Index points to LEA: assimilate everything */
			if (am_flav & ia32_O)
				ret_val |= IA32_LEA_ATTR_OFFS;
			if (am_flav & ia32_S)
				ret_val |= IA32_LEA_ATTR_SCALE;
			if (am_flav & ia32_B)
				ret_val |= IA32_LEA_ATTR_BASE;

			ret_val |= IA32_LEA_ATTR_INDEX;
		}
		else if (am_flav & ia32_I ? 0 : 1) {
			/* Index is not the LEA but the LEA is a base only calculation: assimilate */
			if (am_flav & ia32_O)
				ret_val |= IA32_LEA_ATTR_OFFS;
			if (am_flav & ia32_S)
				ret_val |= IA32_LEA_ATTR_SCALE;

			ret_val |= IA32_LEA_ATTR_BASE;
		}
		else
			return IA32_LEA_ATTR_NONE;
	}
	else {
		assert(0 && "There must have been set base or index");
	}

	return ret_val;
}
Christian Würdig's avatar
Christian Würdig committed
732

733
734
735
736
737
738
739
740
741
742
743
/**
 * Adds res before irn into schedule if irn was scheduled.
 * @param irn  The schedule point
 * @param res  The node to be scheduled
 */
static INLINE void try_add_to_sched(ir_node *irn, ir_node *res) {
	if (sched_is_scheduled(irn))
		sched_add_before(irn, res);
}

/**
744
 * Removes node from schedule if it is not used anymore. If irn is a mode_T node
745
746
747
 * all it's Projs are removed as well.
 * @param irn  The irn to be removed from schedule
 */
748
static INLINE void try_remove_from_sched(ir_node *node) {
749
750
	int i, arity;

751
752
753
754
755
	if(get_irn_mode(node) == mode_T) {
		const ir_edge_t *edge;
		foreach_out_edge(node, edge) {
			ir_node *proj = get_edge_src_irn(edge);
			try_remove_from_sched(proj);
756
		}
757
	}
758

759
760
761
762
763
764
765
766
767
768
	if(get_irn_n_edges(node) != 0)
		return;

	if (sched_is_scheduled(node)) {
		sched_remove(node);
	}

	arity = get_irn_arity(node);
	for(i = 0; i < arity; ++i) {
		set_irn_n(node, i, new_Bad());
769
770
	}
}
Christian Würdig's avatar
Christian Würdig committed
771

Christian Würdig's avatar
Christian Würdig committed
772
773
774
/**
 * Folds Add or Sub to LEA if possible
 */
775
static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn) {
776
	ir_graph   *irg        = get_irn_irg(irn);
777
	dbg_info   *dbg_info   = get_irn_dbg_info(irn);
778
779
	ir_node    *block      = get_nodes_block(irn);
	ir_node    *res        = irn;
Christian Würdig's avatar
Christian Würdig committed
780
781
782
	ir_node    *shift      = NULL;
	ir_node    *lea_o      = NULL;
	ir_node    *lea        = NULL;
783
784
785
	long        offs       = 0;
	long        offs_cnst  = 0;
	long        offs_lea   = 0;
786
787
788
789
790
	int         scale      = 0;
	int         isadd      = 0;
	int         dolea      = 0;
	int         have_am_sc = 0;
	int         am_sc_sign = 0;
791
	ir_entity  *am_sc      = NULL;
792
	ir_entity  *lea_ent    = NULL;
793
	ir_node    *noreg      = ia32_new_NoReg_gp(cg);
794
	ir_node    *left, *right, *temp;
Christian Würdig's avatar
Christian Würdig committed
795
	ir_node    *base, *index;
Christian Würdig's avatar
Christian Würdig committed
796
	int consumed_left_shift;
Christian Würdig's avatar
Christian Würdig committed
797
798
799
800
801
802
803
804
	ia32_am_flavour_t am_flav;

	if (is_ia32_Add(irn))
		isadd = 1;

	left  = get_irn_n(irn, 2);
	right = get_irn_n(irn, 3);

Christian Würdig's avatar
Christian Würdig committed
805
	/* "normalize" arguments in case of add with two operands */
Michael Beck's avatar
Michael Beck committed
806
	if  (isadd && ! be_is_NoReg(cg, right)) {
Christian Würdig's avatar
Christian Würdig committed
807
808
		/* put LEA == ia32_am_O as right operand */
		if (is_ia32_Lea(left) && get_ia32_am_flavour(left) == ia32_am_O) {
Christian Würdig's avatar
Christian Würdig committed
809
810
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
811
812
813
814
815
816
817
			temp  = left;
			left  = right;
			right = temp;
		}

		/* put LEA != ia32_am_O as left operand */
		if (is_ia32_Lea(right) && get_ia32_am_flavour(right) != ia32_am_O) {
Christian Würdig's avatar
Christian Würdig committed
818
819
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
820
821
822
823
824
			temp  = left;
			left  = right;
			right = temp;
		}

Christian Würdig's avatar
Christian Würdig committed
825
826
		/* put SHL as left operand iff left is NOT a LEA */
		if (! is_ia32_Lea(left) && pred_is_specific_node(right, is_ia32_Shl)) {
Christian Würdig's avatar
Christian Würdig committed
827
828
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
829
830
831
832
833
834
			temp  = left;
			left  = right;
			right = temp;
		}
	}

Christian Würdig's avatar
Christian Würdig committed
835
836
	base    = left;
	index   = noreg;
837
	offs    = 0;
Christian Würdig's avatar
Christian Würdig committed
838
839
840
	scale   = 0;
	am_flav = 0;

841
842
	/* check for operation with immediate */
	if (is_ia32_ImmConst(irn)) {
843
844
		tarval *tv = get_ia32_Immop_tarval(irn);

845
		DBG((dbg, LEVEL_1, "\tfound op with imm const"));
Christian Würdig's avatar
Christian Würdig committed
846

847
		offs_cnst = get_tarval_long(tv);
Christian Würdig's avatar
Christian Würdig committed
848
		dolea     = 1;
Christian Würdig's avatar
Christian Würdig committed
849
	}
850
	else if (isadd && is_ia32_ImmSymConst(irn)) {
851
		DBG((dbg, LEVEL_1, "\tfound op with imm symconst"));
852
853
854

		have_am_sc = 1;
		dolea      = 1;
855
		am_sc      = get_ia32_Immop_symconst(irn);
856
857
		am_sc_sign = is_ia32_am_sc_sign(irn);
	}
Christian Würdig's avatar
Christian Würdig committed
858

Christian Würdig's avatar
Christian Würdig committed
859
	/* determine the operand which needs to be checked */
860
	temp = be_is_NoReg(cg, right) ? left : right;
Christian Würdig's avatar
Christian Würdig committed
861

862
863
864
865
	/* check if right operand is AMConst (LEA with ia32_am_O)  */
	/* but we can only eat it up if there is no other symconst */
	/* because the linker won't accept two symconsts           */
	if (! have_am_sc && is_ia32_Lea(temp) && get_ia32_am_flavour(temp) == ia32_am_O) {
866
		DBG((dbg, LEVEL_1, "\tgot op with LEA am_O"));
Christian Würdig's avatar
Christian Würdig committed
867

868
		offs_lea   = get_ia32_am_offs_int(temp);
869
870
871
872
		am_sc      = get_ia32_am_sc(temp);
		am_sc_sign = is_ia32_am_sc_sign(temp);
		have_am_sc = 1;
		dolea      = 1;
Christian Würdig's avatar
Christian Würdig committed
873
		lea_o      = temp;
874
875
876

		if (temp == base)
			base = noreg;
Christian Würdig's avatar
Christian Würdig committed
877
878
		else if (temp == right)
			right = noreg;
Christian Würdig's avatar
Christian Würdig committed
879
	}
Christian Würdig's avatar
Christian Würdig committed
880
881

	if (isadd) {
Christian Würdig's avatar
Christian Würdig committed
882
		/* default for add -> make right operand to index */
Christian Würdig's avatar
Christian Würdig committed
883
884
		index               = right;
		dolea               = 1;
Christian Würdig's avatar
Christian Würdig committed
885
		consumed_left_shift = -1;
Christian Würdig's avatar
Christian Würdig committed
886

887
		DBG((dbg, LEVEL_1, "\tgot LEA candidate with index %+F\n", index));
Christian Würdig's avatar
Christian Würdig committed
888
889
890
891

		/* determine the operand which needs to be checked */
		temp = left;
		if (is_ia32_Lea(left)) {
Christian Würdig's avatar
Christian Würdig committed
892
			temp = right;
Christian Würdig's avatar
Christian Würdig committed
893
			consumed_left_shift = 0;
Christian Würdig's avatar
Christian Würdig committed
894
895
		}

Christian Würdig's avatar
Christian Würdig committed
896
		/* check for SHL 1,2,3 */
Christian Würdig's avatar
Christian Würdig committed
897
		if (pred_is_specific_node(temp, is_ia32_Shl)) {
Christian Würdig's avatar
Christian Würdig committed
898

899
			if (is_ia32_ImmConst(temp)) {
900
				long shiftval = get_tarval_long(get_ia32_Immop_tarval(temp));
Christian Würdig's avatar
Christian Würdig committed
901

902
				if (shiftval <= 3) {
Christian Würdig's avatar
Christian Würdig committed
903
904
					index               = get_irn_n(temp, 2);
					consumed_left_shift = consumed_left_shift < 0 ? 1 : 0;
905
906
					shift = temp;
					scale = shiftval;
Christian Würdig's avatar
Christian Würdig committed
907

908
					DBG((dbg, LEVEL_1, "\tgot scaled index %+F\n", index));
Christian Würdig's avatar
Christian Würdig committed
909
910
911
				}
			}
		}
Christian Würdig's avatar
Christian Würdig committed
912
913

		/* fix base */
Michael Beck's avatar
Michael Beck committed
914
		if (! be_is_NoReg(cg, index)) {
Christian Würdig's avatar
Christian Würdig committed
915
916
917
918
			/* if we have index, but left == right -> no base */
			if (left == right) {
				base = noreg;
			}
Christian Würdig's avatar
Christian Würdig committed
919
			else if (consumed_left_shift == 1) {
Christian Würdig's avatar
Christian Würdig committed
920
				/* -> base is right operand  */
921
				base = (right == lea_o) ? noreg : right;
Christian Würdig's avatar
Christian Würdig committed
922
923
924
925
926
927
			}
		}
	}

	/* Try to assimilate a LEA as left operand */
	if (is_ia32_Lea(left) && (get_ia32_am_flavour(left) != ia32_am_O)) {
Christian Würdig's avatar
Christian Würdig committed
928
929
930
931
		/* check if we can assimilate the LEA */
		int take_attr = do_new_lea(irn, base, index, left, have_am_sc, cg);

		if (take_attr == IA32_LEA_ATTR_NONE) {
932
			DBG((dbg, LEVEL_1, "\tleave old LEA, creating new one\n"));
Christian Würdig's avatar
Christian Würdig committed
933
934
		}
		else {
935
			DBG((dbg, LEVEL_1, "\tgot LEA as left operand ... assimilating\n"));
Christian Würdig's avatar
Christian Würdig committed
936
937
938
			lea = left; /* for statistics */

			if (take_attr & IA32_LEA_ATTR_OFFS)
939
				offs = get_ia32_am_offs_int(left);
Christian Würdig's avatar
Christian Würdig committed
940
941
942
943
944

			if (take_attr & IA32_LEA_ATTR_AMSC) {
				am_sc      = get_ia32_am_sc(left);
				have_am_sc = 1;
				am_sc_sign = is_ia32_am_sc_sign(left);
Christian Würdig's avatar
Christian Würdig committed
945
			}
Christian Würdig's avatar
Christian Würdig committed
946
947
948
949
950
951
952
953
954
955
956
957

			if (take_attr & IA32_LEA_ATTR_SCALE)
				scale = get_ia32_am_scale(left);

			if (take_attr & IA32_LEA_ATTR_BASE)
				base = get_irn_n(left, 0);

			if (take_attr & IA32_LEA_ATTR_INDEX)
				index = get_irn_n(left, 1);

			if (take_attr & IA32_LEA_ATTR_FENT)
				lea_ent = get_ia32_frame_ent(left);
Christian Würdig's avatar
Christian Würdig committed
958
		}
Christian Würdig's avatar
Christian Würdig committed
959
960
961
962
	}

	/* ok, we can create a new LEA */
	if (dolea) {
963
		res = new_rd_ia32_Lea(dbg_info, irg, block, base, index);
Christian Würdig's avatar
Christian Würdig committed
964
965

		/* add the old offset of a previous LEA */
966
		add_ia32_am_offs_int(res, offs);
Christian Würdig's avatar
Christian Würdig committed
967
968
969

		/* add the new offset */
		if (isadd) {
970
971
972
			add_ia32_am_offs_int(res, offs_cnst);
			add_ia32_am_offs_int(res, offs_lea);
		} else {
Christian Würdig's avatar
Christian Würdig committed
973
			/* either lea_O-cnst, -cnst or -lea_O  */
974
975
976
977
978
			if (offs_cnst != 0) {
				add_ia32_am_offs_int(res, offs_lea);
				add_ia32_am_offs_int(res, -offs_cnst);
			} else {
				add_ia32_am_offs_int(res, offs_lea);
Christian Würdig's avatar
Christian Würdig committed
979
			}
Christian Würdig's avatar
Christian Würdig committed
980
981
		}

982
983
984
985
986
987
988
		/* set the address mode symconst */
		if (have_am_sc) {
			set_ia32_am_sc(res, am_sc);
			if (am_sc_sign)
				set_ia32_am_sc_sign(res);
		}

989
990
		/* copy the frame entity (could be set in case of Add */
		/* which was a FrameAddr) */
991
		if (lea_ent != NULL) {
Christian Würdig's avatar
Christian Würdig committed
992
			set_ia32_frame_ent(res, lea_ent);
993
			set_ia32_use_frame(res);
994
995
996
997
998
		} else {
			set_ia32_frame_ent(res, get_ia32_frame_ent(irn));
			if(is_ia32_use_frame(irn))
				set_ia32_use_frame(res);
		}
999

Christian Würdig's avatar
Christian Würdig committed
1000
		/* set scale */