ia32_optimize.c 41.2 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
#define AGGRESSIVE_AM

Christian Würdig's avatar
Christian Würdig committed
39
typedef enum {
40
41
42
43
	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
44
45
} ia32_am_cand_t;

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

Michael Beck's avatar
Michael Beck committed
49
50
51
/**
 * checks if a node represents the NOREG value
 */
52
53
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;
54
55
}

56
57
58
59
60
61
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
	*/
62
63
64
	//ia32_transform_all_firm_consts(cg);
	irg_walk_graph(cg->irg, NULL, ia32_transform_psi_cond_tree, cg);
	//ia32_transform_all_firm_consts(cg);
65
}
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

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

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

82
83
84
85
86
87
88
89
90
91
92
93
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;
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
}

/**
 * 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;
		}
	}

144
145
	if (!same_args)
		return 0;
146

147
	return ia32_const_equal(cand, irn);
148
149
150
151
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
179
}

/**
 * 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) {
		DBG((cg->mod, LEVEL_1, "replacing %+F by ", irn));

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

		DB((cg->mod, LEVEL_1, "%+F\n", irn));
	}
}

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) {
180
	int i, arity;
181

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

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

/**
 * 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) {
		DBG((cg->mod, LEVEL_1, "replacing %+F by ", irn));
Christian Würdig's avatar
Christian Würdig committed
204
		DBG_OPT_CJMP(irn);
205

Michael Beck's avatar
Michael Beck committed
206
		set_irn_op(irn, op_ia32_CJmpAM);
207
208
209
210
211

		DB((cg->mod, LEVEL_1, "%+F\n", irn));
	}
}

212
213
// only optimize up to 48 stores behind IncSPs
#define MAXPUSH_OPTIMIZE	48
214
215

/**
216
 * Tries to create pushs from IncSP,Store combinations
217
 */
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
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
233
	if(offset < 4)
234
235
236
237
238
239
240
241
242
243
		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;
244
		int offset;
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
		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;

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

		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
283
284
285
286
287
288
	i = (offset / 4) - 1;
	if(i >= MAXPUSH_OPTIMIZE) {
		i = MAXPUSH_OPTIMIZE - 1;
	}

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

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

298
299
300
301
302
		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
303
		push = new_rd_ia32_Push(NULL, irg, block, noreg, noreg, val, curr_sp, mem);
304
305
306
307

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

308
309
310
311
312
313
314
		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);

315
316
317
318
319
320
		// 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);
321

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

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

	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());
342
		sched_remove(irn);
343
344
345
	} else {
		set_irn_n(irn, 0, curr_sp);
	}
346
347
}

348
#if 0
349
/**
350
 * Tries to optimize two following IncSP.
351
 */
352
353
354
355
356
357
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 */
358
359
		int prev_offs = be_get_IncSP_offset(prev);
		int curr_offs = be_get_IncSP_offset(irn);
360

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

		/* Omit the optimized IncSP */
		be_set_IncSP_pred(irn, be_get_IncSP_pred(prev));
365
366

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

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

378
379
380
381
382
383
384
	/* 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);
	}
385
386
387
388

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

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

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

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

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

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

418
419
420
421
422
423
424
425
426
427
428
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
429
/**
Christian Würdig's avatar
Christian Würdig committed
430
431
432
433
434
 * 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
435
 */
436
static int pred_is_specific_node(const ir_node *pred, is_op_func_t *is_op_func) {
437
	return is_op_func(pred);
Christian Würdig's avatar
Christian Würdig committed
438
439
}

Christian Würdig's avatar
Christian Würdig committed
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
/**
 * 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;
}

462
/**
463
464
465
 * 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.
466
467
468
469
 *
 * - 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
470
471
472
473
 * @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
474
static int is_addr_candidate(const ir_node *irn) {
475
#ifndef AGGRESSIVE_AM
Matthias Braun's avatar
fix    
Matthias Braun committed
476
	const ir_node *block = get_nodes_block(irn);
477
478
	ir_node *left, *right;
	int      n;
Christian Würdig's avatar
Christian Würdig committed
479
480
481
482

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

483
484
485
486
487
	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
488
489
	}

490
491
492
493
	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
494
	}
495
#endif
Christian Würdig's avatar
Christian Würdig committed
496

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

/**
 * Checks if irn is a candidate for address mode.
 *
503
504
505
506
507
 * 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
 *
508
 * @param cg          The ia32 code generator
Christian Würdig's avatar
Christian Würdig committed
509
510
 * @param h           The height information of the irg
 * @param block       The block the Loads must/mustnot be in
511
 * @param irn         The irn to check
Christian Würdig's avatar
Christian Würdig committed
512
 * return 0 if irn is no candidate, 1 if left load can be used, 2 if right one, 3 for both
513
 */
514
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
515
	ir_node *in, *load, *other, *left, *right;
Matthias Braun's avatar
Matthias Braun committed
516
	int      is_cand = 0, cand;
517
	int arity;
518

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

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

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

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

		load  = get_Proj_pred(in);
		other = right;

548
549
550
551
		/* 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);
552
			is_cand = 0;
553
		}
554

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

Christian Würdig's avatar
Christian Würdig committed
564
565
566
	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
567

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

		load  = get_Proj_pred(in);
		other = left;

580
581
582
583
		/* 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
584
		/* If there is a data dependency of other irn from load: cannot use load */
585
		if (is_cand && get_nodes_block(other) == block) {
586
587
			other   = skip_Proj(other);
			is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
588
589
			/* this could happen in loops */
			is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
590
		}
591
592
	}

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

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

/**
 * 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)
{
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
	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;
624
625
}

Christian Würdig's avatar
Christian Würdig committed
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
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)
{
642
643
644
645
646
	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
647
648
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
	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
730

731
732
733
734
735
736
737
738
739
740
741
/**
 * 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);
}

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

749
750
751
752
753
	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);
754
		}
755
	}
756

757
758
759
760
761
762
763
764
765
766
	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());
767
768
	}
}
Christian Würdig's avatar
Christian Würdig committed
769

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

	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
804
	/* "normalize" arguments in case of add with two operands */
Michael Beck's avatar
Michael Beck committed
805
	if  (isadd && ! be_is_NoReg(cg, right)) {
Christian Würdig's avatar
Christian Würdig committed
806
807
		/* 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
808
809
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
810
811
812
813
814
815
816
			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
817
818
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
819
820
821
822
823
			temp  = left;
			left  = right;
			right = temp;
		}

Christian Würdig's avatar
Christian Würdig committed
824
825
		/* 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
826
827
			set_irn_n(irn, 2, right);
			set_irn_n(irn, 3, left);
Christian Würdig's avatar
Christian Würdig committed
828
829
830
831
832
833
			temp  = left;
			left  = right;
			right = temp;
		}
	}

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

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

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

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

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

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

861
862
863
864
	/* 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) {
Christian Würdig's avatar
Christian Würdig committed
865
866
		DBG((mod, LEVEL_1, "\tgot op with LEA am_O"));

867
		offs_lea   = get_ia32_am_offs_int(temp);
868
869
870
871
		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
872
		lea_o      = temp;
873
874
875

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

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

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

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

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

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

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

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

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

	/* 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
927
928
929
930
		/* 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) {
Christian Würdig's avatar
Christian Würdig committed
931
932
933
934
			DBG((mod, LEVEL_1, "\tleave old LEA, creating new one\n"));
		}
		else {
			DBG((mod, LEVEL_1, "\tgot LEA as left operand ... assimilating\n"));
Christian Würdig's avatar
Christian Würdig committed
935
936
937
			lea = left; /* for statistics */

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

			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
944
			}
Christian Würdig's avatar
Christian Würdig committed
945
946
947
948
949
950
951
952
953
954
955
956

			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
957
		}
Christian Würdig's avatar
Christian Würdig committed
958
959
960
961
	}

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

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

		/* add the new offset */
		if (isadd) {
969
970
971
			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
972
			/* either lea_O-cnst, -cnst or -lea_O  */
973
974
975
976
977
			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
978
			}
Christian Würdig's avatar
Christian Würdig committed
979
980
		}

981
982
983
984
985
986
987
		/* 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);
		}

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

Christian Würdig's avatar
Christian Würdig committed
999
1000
		/* set scale */
		set_ia32_am_scale(res, scale);
For faster browsing, not all history is shown. View entire blame