ia32_optimize.c 22.5 KB
Newer Older
1
2
3
4
5
6
7
8
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "irnode.h"
#include "irprog_t.h"
#include "ircons.h"
#include "firm_types.h"
Christian Würdig's avatar
Christian Würdig committed
9
10
11
12
#include "iredges.h"
#include "tv.h"
#include "irgmod.h"

Christian Würdig's avatar
Christian Würdig committed
13
14
#include "../be_t.h"
#include "../beabi.h"
15
16
17

#include "ia32_new_nodes.h"
#include "bearch_ia32_t.h"
Christian Würdig's avatar
Christian Würdig committed
18
#include "gen_ia32_regalloc_if.h"     /* the generated interface (register type and class defenitions) */
19

Christian Würdig's avatar
Christian Würdig committed
20
21
22
#undef is_NoMem
#define is_NoMem(irn) (get_irn_op(irn) == op_NoMem)

Christian Würdig's avatar
Christian Würdig committed
23
24
25
26
27
28
29
30
31
32
static int be_is_NoReg(be_abi_irg_t *babi, const ir_node *irn) {
	if (be_abi_get_callee_save_irn(babi, &ia32_gp_regs[REG_XXX]) == irn ||
		be_abi_get_callee_save_irn(babi, &ia32_fp_regs[REG_XXXX]) == irn)
	{
		return 1;
	}

	return 0;
}

33
34
35
36
37
38
39
40
/**
 * creates a unique ident by adding a number to a tag
 *
 * @param tag   the tag string, must contain a %d if a number
 *              should be added
 */
static ident *unique_id(const char *tag)
{
41
42
	static unsigned id = 0;
	char str[256];
43

44
45
	snprintf(str, sizeof(str), tag, ++id);
	return new_id_from_str(str);
46
47
48
49
50
51
52
53
54
55
56
57
58
59
}



/**
 * Transforms a SymConst.
 *
 * @param mod     the debug module
 * @param block   the block the new node should belong to
 * @param node    the ir SymConst node
 * @param mode    mode of the SymConst
 * @return the created ia32 Const node
 */
static ir_node *gen_SymConst(ia32_transform_env_t *env) {
Christian Würdig's avatar
Christian Würdig committed
60
61
62
63
64
	ir_node  *cnst;
	dbg_info *dbg   = env->dbg;
	ir_mode  *mode  = env->mode;
	ir_graph *irg   = env->irg;
	ir_node  *block = env->block;
65

66
67
68
69
	cnst = new_rd_ia32_Const(dbg, irg, block, mode);
	set_ia32_Const_attr(cnst, env->irn);
	return cnst;
}
70

71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * Get a primitive type for a mode.
 */
static ir_type *get_prim_type(pmap *types, ir_mode *mode)
{
	pmap_entry *e = pmap_find(types, mode);
	ir_type *res;

	if (! e) {
		char buf[64];
		snprintf(buf, sizeof(buf), "prim_type_%s", get_mode_name(mode));
		res = new_type_primitive(new_id_from_str(buf), mode);
		pmap_insert(types, mode, res);
84
	}
85
86
87
88
	else
		res = e->value;
	return res;
}
89

90
91
92
93
94
95
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
/**
 * Get an entity that is initialized with a tarval
 */
static entity *get_entity_for_tv(ia32_code_gen_t *cg, ir_node *cnst)
{
	tarval *tv    = get_Const_tarval(cnst);
	pmap_entry *e = pmap_find(cg->tv_ent, tv);
	entity *res;
	ir_graph *rem;

	if (! e) {
		ir_mode *mode = get_irn_mode(cnst);
		ir_type *tp = get_Const_type(cnst);
		if (tp == firm_unknown_type)
			tp = get_prim_type(cg->types, mode);

		res = new_entity(get_glob_type(), unique_id("ia32FloatCnst_%u"), tp);

		set_entity_ld_ident(res, get_entity_ident(res));
		set_entity_visibility(res, visibility_local);
		set_entity_variability(res, variability_constant);
		set_entity_allocation(res, allocation_static);

		 /* we create a new entity here: It's initialization must resist on the
		    const code irg */
		rem = current_ir_graph;
		current_ir_graph = get_const_code_irg();
		set_atomic_ent_value(res, new_Const_type(tv, tp));
		current_ir_graph = rem;
	}
	else
		res = e->value;
	return res;
123
124
125
126
127
128
129
130
131
132
133
134
135
136
}

/**
 * Transforms a Const.
 *
 * @param mod     the debug module
 * @param block   the block the new node should belong to
 * @param node    the ir Const node
 * @param mode    mode of the Const
 * @return the created ia32 Const node
 */
static ir_node *gen_Const(ia32_transform_env_t *env) {
	ir_node *cnst;
	symconst_symbol sym;
Christian Würdig's avatar
Christian Würdig committed
137
138
139
	ir_graph *irg   = env->irg;
	ir_node  *block = env->block;
	ir_node  *node  = env->irn;
140
141
	dbg_info *dbg   = env->dbg;
	ir_mode  *mode  = env->mode;
142
143

	if (mode_is_float(mode)) {
144
		sym.entity_p = get_entity_for_tv(env->cg, node);
145
146
147
148
149
150

		cnst = new_rd_SymConst(dbg, irg, block, sym, symconst_addr_ent);
		env->irn = cnst;
		cnst = gen_SymConst(env);
	}
	else {
151
		cnst = new_rd_ia32_Const(dbg, irg, block, get_irn_mode(node));
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
		set_ia32_Const_attr(cnst, node);
	}
	return cnst;
}



/**
 * Transforms (all) Const's into ia32_Const and places them in the
 * block where they are used (or in the cfg-pred Block in case of Phi's)
 */
void ia32_place_consts(ir_node *irn, void *env) {
	ia32_code_gen_t      *cg = env;
	ia32_transform_env_t  tenv;
	ir_mode              *mode;
	ir_node              *pred, *cnst;
	int                   i;
	opcode                opc;

	if (is_Block(irn))
		return;

	mode = get_irn_mode(irn);

	tenv.block    = get_nodes_block(irn);
	tenv.cg       = cg;
	tenv.irg      = cg->irg;
Christian Würdig's avatar
Christian Würdig committed
179
	tenv.mod      = cg->mod;
180
181

	/* Loop over all predecessors and check for Sym/Const nodes */
182
	for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
		pred      = get_irn_n(irn, i);
		cnst      = NULL;
		opc       = get_irn_opcode(pred);
		tenv.irn  = pred;
		tenv.mode = get_irn_mode(pred);
		tenv.dbg  = get_irn_dbg_info(pred);

		/* If it's a Phi, then we need to create the */
		/* new Const in it's predecessor block       */
		if (is_Phi(irn)) {
			tenv.block = get_Block_cfgpred_block(get_nodes_block(irn), i);
		}

		switch (opc) {
			case iro_Const:
				cnst = gen_Const(&tenv);
				break;
			case iro_SymConst:
				cnst = gen_SymConst(&tenv);
				break;
			default:
				break;
		}

		/* if we found a const, then set it */
		if (cnst) {
			set_irn_n(irn, i, cnst);
		}
	}
}
Christian Würdig's avatar
Christian Würdig committed
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247


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

static int node_is_comm(const ir_node *irn) {
	if (is_ia32_Add(irn)  ||
		is_ia32_fAdd(irn) ||
		is_ia32_Mul(irn)  ||
		is_ia32_Mulh(irn) ||
		is_ia32_fMul(irn) ||
		is_ia32_And(irn)  ||
		is_ia32_fAnd(irn) ||
		is_ia32_Or(irn)   ||
		is_ia32_fOr(irn)  ||
		is_ia32_Eor(irn)  ||
		is_ia32_fEor(irn) ||
		is_ia32_Min(irn)  ||
		is_ia32_fMin(irn) ||
		is_ia32_Max(irn)  ||
		is_ia32_fMax(irn))
	{
		return 1;
	}

	return 0;
}

248
249
250
251
252
253
254
255
256
257
258
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
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
/**
 * Returns the first mode_M Proj connected to irn.
 */
static ir_node *get_mem_proj(const ir_node *irn) {
	const ir_edge_t *edge;
	ir_node         *src;

	assert(get_irn_mode(irn) == mode_T && "expected mode_T node");

	foreach_out_edge(irn, edge) {
		src = get_edge_src_irn(edge);

		assert(is_Proj(src) && "Proj expected");

		if (get_irn_mode(src) == mode_M)
			return src;
	}

	return NULL;
}

Christian Würdig's avatar
Christian Würdig committed
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
/**
 * Returns the Proj with number 0 connected to irn.
 */
static ir_node *get_res_proj(const ir_node *irn) {
	const ir_edge_t *edge;
	ir_node         *src;

	assert(get_irn_mode(irn) == mode_T && "expected mode_T node");

	foreach_out_edge(irn, edge) {
		src = get_edge_src_irn(edge);

		assert(is_Proj(src) && "Proj expected");

		if (get_Proj_proj(src) == 0)
			return src;
	}

	return NULL;
}

Christian Würdig's avatar
Christian Würdig committed
301
/**
Christian Würdig's avatar
Christian Würdig committed
302
303
304
305
306
 * 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
307
 */
Christian Würdig's avatar
Christian Würdig committed
308
309
static int pred_is_specific_node(const ir_node *pred, int (*is_op_func)(const ir_node *n)) {
	if (is_Proj(pred) && is_op_func(get_Proj_pred(pred))) {
Christian Würdig's avatar
Christian Würdig committed
310
311
312
313
314
315
		return 1;
	}

	return 0;
}

Christian Würdig's avatar
Christian Würdig committed
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
/**
 * 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;
}

Christian Würdig's avatar
Christian Würdig committed
338
339
340
/**
 * Folds Add or Sub to LEA if possible
 */
Christian Würdig's avatar
Christian Würdig committed
341
static ir_node *fold_addr(be_abi_irg_t *babi, ir_node *irn, firm_dbg_module_t *mod, ir_node *noreg) {
Christian Würdig's avatar
Christian Würdig committed
342
343
344
345
346
347
348
349
350
351
352
	ir_graph *irg       = get_irn_irg(irn);
	ir_mode  *mode      = get_irn_mode(irn);
	dbg_info *dbg       = get_irn_dbg_info(irn);
	ir_node  *block     = get_nodes_block(irn);
	ir_node  *res       = irn;
	char     *offs      = NULL;
	char     *offs_cnst = NULL;
	char     *offs_lea  = NULL;
	int       scale     = 0;
	int       isadd     = 0;
	int       dolea     = 0;
Christian Würdig's avatar
Christian Würdig committed
353
354
355
356
357
358
359
360
361
362
	ir_node  *left, *right, *temp;
	ir_node  *base, *index;
	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
363
364
365
366
367
368
369
	base    = left;
	index   = noreg;
	offs    = NULL;
	scale   = 0;
	am_flav = 0;

	/* "normalize" arguments in case of add with two operands */
Christian Würdig's avatar
Christian Würdig committed
370
	if  (isadd && ! be_is_NoReg(babi, right)) {
Christian Würdig's avatar
Christian Würdig committed
371
372
		/* 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
373
374
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
375
376
377
378
379
380
381
			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
382
383
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
384
385
386
387
388
			temp  = left;
			left  = right;
			right = temp;
		}

Christian Würdig's avatar
Christian Würdig committed
389
390
		/* 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
391
392
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
393
394
395
396
397
398
			temp  = left;
			left  = right;
			right = temp;
		}
	}

Christian Würdig's avatar
Christian Würdig committed
399
400
401
	/* check if operand is either const */
	if (get_ia32_cnst(irn)) {
		DBG((mod, LEVEL_1, "\tfound op with imm"));
Christian Würdig's avatar
Christian Würdig committed
402

Christian Würdig's avatar
Christian Würdig committed
403
404
		offs_cnst = get_ia32_cnst(irn);
		dolea     = 1;
Christian Würdig's avatar
Christian Würdig committed
405
406
	}

Christian Würdig's avatar
Christian Würdig committed
407
	/* determine the operand which needs to be checked */
Christian Würdig's avatar
Christian Würdig committed
408
	if (be_is_NoReg(babi, right)) {
Christian Würdig's avatar
Christian Würdig committed
409
		temp = left;
Christian Würdig's avatar
Christian Würdig committed
410
	}
Christian Würdig's avatar
Christian Würdig committed
411
412
	else {
		temp = right;
Christian Würdig's avatar
Christian Würdig committed
413
	}
Christian Würdig's avatar
Christian Würdig committed
414
415
416

	/* check if right operand is AMConst (LEA with ia32_am_O) */
	if (is_ia32_Lea(temp) && get_ia32_am_flavour(temp) == ia32_am_O) {
Christian Würdig's avatar
Christian Würdig committed
417
418
		DBG((mod, LEVEL_1, "\tgot op with LEA am_O"));

Christian Würdig's avatar
Christian Würdig committed
419
		offs_lea = get_ia32_am_offs(temp);
Christian Würdig's avatar
Christian Würdig committed
420
421
		dolea    = 1;
	}
Christian Würdig's avatar
Christian Würdig committed
422
423

	if (isadd) {
Christian Würdig's avatar
Christian Würdig committed
424
425
426
427
428
		/* default for add -> make right operand to index */
		index = right;
		dolea = 1;

		DBG((mod, LEVEL_1, "\tgot LEA candidate with index %+F\n", index));
Christian Würdig's avatar
Christian Würdig committed
429
430
431
432
433
434
435

		/* determine the operand which needs to be checked */
		temp = left;
		if (is_ia32_Lea(left)) {
			temp = right;
		}

Christian Würdig's avatar
Christian Würdig committed
436
		/* check for SHL 1,2,3 */
Christian Würdig's avatar
Christian Würdig committed
437
438
		if (pred_is_specific_node(temp, is_ia32_Shl)) {
			temp = get_Proj_pred(temp);
Christian Würdig's avatar
Christian Würdig committed
439
440
441
442
443
444
445
446
447
448
449

			if (get_ia32_Immop_tarval(temp)) {
				scale = get_tarval_long(get_ia32_Immop_tarval(temp));

				if (scale <= 3) {
					index = get_irn_n(temp, 2);

					DBG((mod, LEVEL_1, "\tgot scaled index %+F\n", index));
				}
			}
		}
Christian Würdig's avatar
Christian Würdig committed
450
451

		/* fix base */
Christian Würdig's avatar
Christian Würdig committed
452
		if (! be_is_NoReg(babi, index)) {
Christian Würdig's avatar
Christian Würdig committed
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
			/* if we have index, but left == right -> no base */
			if (left == right) {
				base = noreg;
			}
			else if (! is_ia32_Lea(left) && (index != right)) {
				/* index != right -> we found a good Shl           */
				/* left  != LEA   -> this Shl was the left operand */
				/* -> base is right operand                        */
				base = right;
			}
		}
	}

	/* Try to assimilate a LEA as left operand */
	if (is_ia32_Lea(left) && (get_ia32_am_flavour(left) != ia32_am_O)) {
		am_flav = get_ia32_am_flavour(left);

		/* If we have an Add with a real right operand (not NoReg) and  */
		/* the LEA contains already an index calculation then we create */
		/* a new LEA.                                                   */
Christian Würdig's avatar
Christian Würdig committed
473
		if (isadd && !be_is_NoReg(babi, index) && (am_flav & ia32_am_I)) {
Christian Würdig's avatar
Christian Würdig committed
474
475
476
477
478
479
480
481
482
			DBG((mod, LEVEL_1, "\tleave old LEA, creating new one\n"));
		}
		else {
			DBG((mod, LEVEL_1, "\tgot LEA as left operand ... assimilating\n"));
			offs  = get_ia32_am_offs(left);
			base  = get_irn_n(left, 0);
			index = get_irn_n(left, 1);
			scale = get_ia32_am_scale(left);
		}
Christian Würdig's avatar
Christian Würdig committed
483
484
485
486
	}

	/* ok, we can create a new LEA */
	if (dolea) {
Christian Würdig's avatar
Christian Würdig committed
487
		res = new_rd_ia32_Lea(dbg, irg, block, base, index, mode_Is);
Christian Würdig's avatar
Christian Würdig committed
488
489
490
491
492
493
494
495

		/* add the old offset of a previous LEA */
		if (offs) {
			add_ia32_am_offs(res, offs);
		}

		/* add the new offset */
		if (isadd) {
Christian Würdig's avatar
Christian Würdig committed
496
497
498
499
500
			if (offs_cnst) {
				add_ia32_am_offs(res, offs_cnst);
			}
			if (offs_lea) {
				add_ia32_am_offs(res, offs_lea);
Christian Würdig's avatar
Christian Würdig committed
501
502
503
			}
		}
		else {
Christian Würdig's avatar
Christian Würdig committed
504
505
506
507
508
509
510
511
512
513
514
			/* either lea_O-cnst, -cnst or -lea_O  */
			if (offs_cnst) {
				if (offs_lea) {
					add_ia32_am_offs(res, offs_lea);
				}

				sub_ia32_am_offs(res, offs_cnst);
			}
			else {
				sub_ia32_am_offs(res, offs_lea);
			}
Christian Würdig's avatar
Christian Würdig committed
515
516
517
518
519
520
521
		}

		/* set scale */
		set_ia32_am_scale(res, scale);

		am_flav = ia32_am_N;
		/* determine new am flavour */
Christian Würdig's avatar
Christian Würdig committed
522
		if (offs || offs_cnst || offs_lea) {
Christian Würdig's avatar
Christian Würdig committed
523
524
			am_flav |= ia32_O;
		}
Christian Würdig's avatar
Christian Würdig committed
525
		if (! be_is_NoReg(babi, base)) {
Christian Würdig's avatar
Christian Würdig committed
526
527
			am_flav |= ia32_B;
		}
Christian Würdig's avatar
Christian Würdig committed
528
		if (! be_is_NoReg(babi, index)) {
Christian Würdig's avatar
Christian Würdig committed
529
530
531
532
533
534
535
536
537
538
539
			am_flav |= ia32_I;
		}
		if (scale > 0) {
			am_flav |= ia32_S;
		}
		set_ia32_am_flavour(res, am_flav);

		set_ia32_op_type(res, ia32_AddrModeS);

		DBG((mod, LEVEL_1, "\tLEA [%+F + %+F * %d + %s]\n", base, index, scale, get_ia32_am_offs(res)));

Christian Würdig's avatar
Christian Würdig committed
540
541
542
543
544
		/* get the result Proj of the Add/Sub */
		irn = get_res_proj(irn);

		assert(irn && "Couldn't find result proj");

Christian Würdig's avatar
Christian Würdig committed
545
546
547
548
549
550
551
552
553
554
555
		/* exchange the old op with the new LEA */
		exchange(irn, res);
	}

	return res;
}

/**
 * Optimizes a pattern around irn to address mode if possible.
 */
void ia32_optimize_am(ir_node *irn, void *env) {
Christian Würdig's avatar
Christian Würdig committed
556
557
558
559
560
	ia32_code_gen_t   *cg   = env;
	ir_graph          *irg  = cg->irg;
	firm_dbg_module_t *mod  = cg->mod;
	ir_node           *res  = irn;
	be_abi_irg_t      *babi = cg->birg->abi;
Christian Würdig's avatar
Christian Würdig committed
561
562
563
564
	dbg_info          *dbg;
	ir_mode           *mode;
	ir_node           *block, *noreg_gp, *noreg_fp;
	ir_node           *left, *right, *temp;
Christian Würdig's avatar
Christian Würdig committed
565
	ir_node           *store, *load, *mem_proj;
Christian Würdig's avatar
Christian Würdig committed
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
	ir_node           *succ, *addr_b, *addr_i;
	int                check_am_src = 0;

	if (! is_ia32_irn(irn))
		return;

	dbg      = get_irn_dbg_info(irn);
	mode     = get_irn_mode(irn);
	block    = get_nodes_block(irn);
	noreg_gp = ia32_new_NoReg_gp(cg);
	noreg_fp = ia32_new_NoReg_fp(cg);

	DBG((mod, LEVEL_1, "checking for AM\n"));

	/* 1st part: check for address calculations and transform the into Lea */

Christian Würdig's avatar
Christian Würdig committed
582
583
	/* Following cases can occur:                                  */
	/* - Sub (l, imm) -> LEA [base - offset]                       */
Christian Würdig's avatar
Christian Würdig committed
584
	/* - Sub (l, r == LEA with ia32_am_O)   -> LEA [base - offset] */
Christian Würdig's avatar
Christian Würdig committed
585
586
587
588
589
	/* - Add (l, imm) -> LEA [base + offset]                       */
	/* - Add (l, r == LEA with ia32_am_O)  -> LEA [base + offset]  */
	/* - Add (l == LEA with ia32_am_O, r)  -> LEA [base + offset]  */
	/* - Add (l, r) -> LEA [base + index * scale]                  */
	/*              with scale > 1 iff l/r == shl (1,2,3)          */
Christian Würdig's avatar
Christian Würdig committed
590
591
592
593
594
595

	if (is_ia32_Sub(irn) || is_ia32_Add(irn)) {
		left  = get_irn_n(irn, 2);
		right = get_irn_n(irn, 3);

	    /* Do not try to create a LEA if one of the operands is a Load. */
Christian Würdig's avatar
Christian Würdig committed
596
597
		if (! pred_is_specific_nodeblock(block, left,  is_ia32_Load)  &&
			! pred_is_specific_nodeblock(block, right, is_ia32_Load))
Christian Würdig's avatar
Christian Würdig committed
598
		{
Christian Würdig's avatar
Christian Würdig committed
599
			res = fold_addr(babi, irn, mod, noreg_gp);
Christian Würdig's avatar
Christian Würdig committed
600
601
602
		}
	}

Christian Würdig's avatar
Christian Würdig committed
603
	/* 2nd part: fold following patterns:                                               */
Christian Würdig's avatar
Christian Würdig committed
604
605
	/* - Load  -> LEA into Load  } TODO: If the LEA is used by more than one Load/Store */
	/* - Store -> LEA into Store }       it might be better to keep the LEA             */
Christian Würdig's avatar
Christian Würdig committed
606
607
608
609
610
611
612
613
614
615
616
617
	/* - op -> Load into AMop with am_Source                                            */
	/*   conditions:                                                                    */
	/*     - op is am_Source capable AND                                                */
	/*     - the Load is only used by this op AND                                       */
	/*     - the Load is in the same block                                              */
	/* - Store -> op -> Load  into AMop with am_Dest                                    */
	/*   conditions:                                                                    */
	/*     - op is am_Dest capable AND                                                  */
	/*     - the Store uses the same address as the Load AND                            */
	/*     - the Load is only used by this op AND                                       */
	/*     - the Load and Store are in the same block AND                               */
	/*     - nobody else uses the result of the op                                      */
Christian Würdig's avatar
Christian Würdig committed
618
619
620

	if ((res == irn) && (get_ia32_am_support(irn) != ia32_am_None) && !is_ia32_Lea(irn)) {
		/* 1st: check for Load/Store -> LEA   */
Christian Würdig's avatar
Christian Würdig committed
621
		if (is_ia32_Ld(irn) || is_ia32_St(irn)) {
Christian Würdig's avatar
Christian Würdig committed
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
			left = get_irn_n(irn, 0);

			if (is_ia32_Lea(left)) {
				/* get the AM attributes from the LEA */
				add_ia32_am_offs(irn, get_ia32_am_offs(left));
				set_ia32_am_scale(irn, get_ia32_am_scale(left));
				set_ia32_am_flavour(irn, get_ia32_am_flavour(left));
				set_ia32_op_type(irn, get_ia32_op_type(left));

				/* set base and index */
				set_irn_n(irn, 0, get_irn_n(left, 0));
				set_irn_n(irn, 1, get_irn_n(left, 1));
			}
		}
		/* check if at least one operand is a Load */
Christian Würdig's avatar
Christian Würdig committed
637
638
		else if (pred_is_specific_nodeblock(block, get_irn_n(irn, 2), is_ia32_Ld) ||
				 pred_is_specific_nodeblock(block, get_irn_n(irn, 3), is_ia32_Ld))
Christian Würdig's avatar
Christian Würdig committed
639
		{
Christian Würdig's avatar
Christian Würdig committed
640
641
642
643
644
645
646
647
			left  = get_irn_n(irn, 2);
			if (get_irn_arity(irn) == 4) {
				/* it's an "unary" operation */
				right = left;
			}
			else {
				right = get_irn_n(irn, 3);
			}
Christian Würdig's avatar
Christian Würdig committed
648
649
650

			/* normalize commutative ops */
			if (node_is_comm(irn)) {
Christian Würdig's avatar
Christian Würdig committed
651
652
653
				/* Assure that right operand is always a Load if there is one    */
				/* because non-commutative ops can only use Dest AM if the right */
				/* operand is a load, so we only need to check right operand.    */
Christian Würdig's avatar
Christian Würdig committed
654
				if (pred_is_specific_nodeblock(block, left, is_ia32_Ld))
Christian Würdig's avatar
Christian Würdig committed
655
656
657
658
659
660
661
662
663
664
665
666
667
				{
					set_irn_n(irn, 2, right);
					set_irn_n(irn, 3, left);

					temp  = left;
					left  = right;
					right = temp;
				}
			}

			/* check for Store -> op -> Load */

			/* Store -> op -> Load optimization is only possible if supported by op */
Christian Würdig's avatar
Christian Würdig committed
668
			/* and if right operand is a Load                                       */
Christian Würdig's avatar
Christian Würdig committed
669
670
			if ((get_ia32_am_support(irn) & ia32_am_Dest) &&
				 pred_is_specific_nodeblock(block, right, is_ia32_Ld))
Christian Würdig's avatar
Christian Würdig committed
671
			{
Christian Würdig's avatar
Christian Würdig committed
672
673
674
675
676
677

				/* An address mode capable op always has a result Proj.                  */
				/* If this Proj is used by more than one other node, we don't need to    */
				/* check further, otherwise we check for Store and remember the address, */
				/* the Store points to. */

Christian Würdig's avatar
Christian Würdig committed
678
679
				succ = get_res_proj(irn);
				assert(succ && "Couldn't find result proj");
Christian Würdig's avatar
Christian Würdig committed
680
681
682
683
684
685

				addr_b = NULL;
				addr_i = NULL;
				store  = NULL;

				/* now check for users and Store */
686
				if (ia32_get_irn_n_edges(succ) == 1) {
Christian Würdig's avatar
Christian Würdig committed
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
					succ = get_edge_src_irn(get_irn_out_edge_first(succ));

					if (is_ia32_fStore(succ) || is_ia32_Store(succ)) {
						store  = succ;
						addr_b = get_irn_n(store, 0);

						/* Could be that the Store is connected to the address    */
						/* calculating LEA while the Load is already transformed. */
						if (is_ia32_Lea(addr_b)) {
							succ   = addr_b;
							addr_b = get_irn_n(succ, 0);
							addr_i = get_irn_n(succ, 1);
						}
						else {
							addr_i = noreg_gp;
						}
					}
				}

				if (store) {
					/* we found a Store as single user: Now check for Load */

Christian Würdig's avatar
Christian Würdig committed
709
710
					/* Extra check for commutative ops with two Loads */
					/* -> put the interesting Load right              */
Christian Würdig's avatar
Christian Würdig committed
711
					if (node_is_comm(irn) &&
Christian Würdig's avatar
Christian Würdig committed
712
						pred_is_specific_nodeblock(block, left, is_ia32_Ld))
Christian Würdig's avatar
Christian Würdig committed
713
					{
Christian Würdig's avatar
Christian Würdig committed
714
715
						if ((addr_b == get_irn_n(get_Proj_pred(left), 0)) &&
							(addr_i == get_irn_n(get_Proj_pred(left), 1)))
Christian Würdig's avatar
Christian Würdig committed
716
717
718
719
720
721
722
723
724
725
726
727
728
						{
							/* We exchange left and right, so it's easier to kill     */
							/* the correct Load later and to handle unary operations. */
							set_irn_n(irn, 2, right);
							set_irn_n(irn, 3, left);

							temp  = left;
							left  = right;
							right = temp;
						}
					}

					/* skip the Proj for easier access */
Christian Würdig's avatar
Christian Würdig committed
729
					load = get_Proj_pred(right);
Christian Würdig's avatar
Christian Würdig committed
730
731

					/* Compare Load and Store address */
Christian Würdig's avatar
Christian Würdig committed
732
					if ((addr_b == get_irn_n(load, 0)) && (addr_i == get_irn_n(load, 1)))
Christian Würdig's avatar
Christian Würdig committed
733
					{
Christian Würdig's avatar
Christian Würdig committed
734
						/* Right Load is from same address, so we can */
Christian Würdig's avatar
Christian Würdig committed
735
736
737
738
739
						/* disconnect the Load and Store here        */

						/* set new base, index and attributes */
						set_irn_n(irn, 0, addr_b);
						set_irn_n(irn, 1, addr_i);
Christian Würdig's avatar
Christian Würdig committed
740
741
742
						add_ia32_am_offs(irn, get_ia32_am_offs(load));
						set_ia32_am_scale(irn, get_ia32_am_scale(load));
						set_ia32_am_flavour(irn, get_ia32_am_flavour(load));
Christian Würdig's avatar
Christian Würdig committed
743
744
						set_ia32_op_type(irn, ia32_AddrModeD);

Christian Würdig's avatar
Christian Würdig committed
745
						/* connect to Load memory and disconnect Load */
Christian Würdig's avatar
Christian Würdig committed
746
747
						if (get_irn_arity(irn) == 5) {
							/* binary AMop */
Christian Würdig's avatar
Christian Würdig committed
748
749
							set_irn_n(irn, 4, get_irn_n(load, 2));
							set_irn_n(irn, 3, noreg_gp);
Christian Würdig's avatar
Christian Würdig committed
750
751
752
						}
						else {
							/* unary AMop */
Christian Würdig's avatar
Christian Würdig committed
753
754
							set_irn_n(irn, 3, get_irn_n(load, 2));
							set_irn_n(irn, 2, noreg_gp);
Christian Würdig's avatar
Christian Würdig committed
755
756
757
758
759
760
761
762
763
764
765
766
767
						}

						/* connect the memory Proj of the Store to the op */
						mem_proj = get_mem_proj(store);
						set_Proj_pred(mem_proj, irn);
						set_Proj_proj(mem_proj, 1);
					}
				} /* if (store) */
				else if (get_ia32_am_support(irn) & ia32_am_Source) {
					/* There was no store, check if we still can optimize for source address mode */
					check_am_src = 1;
				}
			} /* if (support AM Dest) */
Christian Würdig's avatar
Christian Würdig committed
768
			else if (get_ia32_am_support(irn) & ia32_am_Source) {
Christian Würdig's avatar
Christian Würdig committed
769
770
771
772
				/* op doesn't support am AM Dest -> check for AM Source */
				check_am_src = 1;
			}

Christian Würdig's avatar
Christian Würdig committed
773
774
775
776
777
778
			/* normalize commutative ops */
			if (node_is_comm(irn)) {
				/* Assure that left operand is always a Load if there is one */
				/* because non-commutative ops can only use Source AM if the */
				/* left operand is a Load, so we only need to check the left */
				/* operand afterwards.                                       */
Christian Würdig's avatar
Christian Würdig committed
779
				if (pred_is_specific_nodeblock(block, right, is_ia32_Ld))	{
Christian Würdig's avatar
Christian Würdig committed
780
781
					set_irn_n(irn, 2, right);
					set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
782

Christian Würdig's avatar
Christian Würdig committed
783
784
785
786
787
					temp  = left;
					left  = right;
					right = temp;
				}
			}
Christian Würdig's avatar
Christian Würdig committed
788

Christian Würdig's avatar
Christian Würdig committed
789
790
			/* optimize op -> Load iff Load is only used by this op   */
			/* and left operand is a Load which only used by this irn */
Christian Würdig's avatar
Christian Würdig committed
791
792
			if (check_am_src                                        &&
				pred_is_specific_nodeblock(block, left, is_ia32_Ld) &&
Christian Würdig's avatar
Christian Würdig committed
793
794
795
796
797
798
799
800
801
802
803
804
805
806
				(ia32_get_irn_n_edges(left) == 1))
			{
				left = get_Proj_pred(left);

				addr_b = get_irn_n(left, 0);
				addr_i = get_irn_n(left, 1);

				/* set new base, index and attributes */
				set_irn_n(irn, 0, addr_b);
				set_irn_n(irn, 1, addr_i);
				add_ia32_am_offs(irn, get_ia32_am_offs(left));
				set_ia32_am_scale(irn, get_ia32_am_scale(left));
				set_ia32_am_flavour(irn, get_ia32_am_flavour(left));
				set_ia32_op_type(irn, ia32_AddrModeS);
Christian Würdig's avatar
Christian Würdig committed
807

Christian Würdig's avatar
Christian Würdig committed
808
809
810
811
812
813
814
815
816
				/* connect to Load memory */
				if (get_irn_arity(irn) == 5) {
					/* binary AMop */
					set_irn_n(irn, 4, get_irn_n(left, 2));
				}
				else {
					/* unary AMop */
					set_irn_n(irn, 3, get_irn_n(left, 2));
				}
Christian Würdig's avatar
Christian Würdig committed
817

Christian Würdig's avatar
Christian Würdig committed
818
819
				/* disconnect from Load */
				set_irn_n(irn, 2, noreg_gp);
Christian Würdig's avatar
Christian Würdig committed
820

Christian Würdig's avatar
Christian Würdig committed
821
822
823
824
825
				/* If Load has a memory Proj, connect it to the op */
				mem_proj = get_mem_proj(left);
				if (mem_proj) {
					set_Proj_pred(mem_proj, irn);
					set_Proj_proj(mem_proj, 1);
Christian Würdig's avatar
Christian Würdig committed
826
827
828
829
830
				}
			}
		}
	}
}