ldstopt.c 55.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Michael Beck's avatar
Michael Beck committed
6
7
8
9
/**
 * @file
 * @brief   Load/Store optimizations.
 * @author  Michael Beck
Michael Beck's avatar
Michael Beck committed
10
 */
11
#include <string.h>
Michael Beck's avatar
Michael Beck committed
12

13
#include "iroptimize.h"
14
15
16
17
18
19
20
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "ircons_t.h"
#include "irgmod.h"
#include "irgwalk.h"
21
#include "irtools.h"
22
23
24
25
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
26
#include "array_t.h"
27
#include "irhooks.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
28
#include "iredges.h"
29
#include "irmemory.h"
30
#include "irnodehashmap.h"
31
#include "irgopt.h"
32
#include "set.h"
Matthias Braun's avatar
Matthias Braun committed
33
#include "be.h"
34
35
36
37
#include "debug.h"

/** The debug handle. */
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
38

39
#define MAX_PROJ MAX(MAX((long)pn_Load_max, (long)pn_Store_max), (long)pn_Call_max)
Michael Beck's avatar
Michael Beck committed
40

41
enum changes_t {
42
43
	DF_CHANGED = 1,       /**< data flow changed */
	CF_CHANGED = 2,       /**< control flow changed */
44
45
};

Michael Beck's avatar
Michael Beck committed
46
47
48
/**
 * walker environment
 */
49
typedef struct walk_env_t {
50
51
	struct obstack obst;          /**< list of all stores */
	unsigned changes;             /**< a bitmask of graph changes */
Michael Beck's avatar
Michael Beck committed
52
53
} walk_env_t;

54
/** A Load/Store info. */
55
typedef struct ldst_info_t {
56
	ir_node  *projs[MAX_PROJ+1];  /**< list of Proj's of this node */
57
58
59
	ir_node  *exc_block;          /**< the exception block if available */
	int      exc_idx;             /**< predecessor index in the exception block */
	unsigned visited;             /**< visited counter for breaking loops */
Michael Beck's avatar
Michael Beck committed
60
61
} ldst_info_t;

62
/**
63
 * flags for control flow.
64
65
 */
enum block_flags_t {
66
67
	BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
	BLOCK_HAS_EXC  = 2       /**< Block has exceptional control flow */
68
69
70
};

/**
71
 * a Block info.
72
 */
73
typedef struct block_info_t {
74
	unsigned flags;               /**< flags for the block */
75
76
} block_info_t;

77
78
79
80
81
82
83
/** the master visited flag for loop detection. */
static unsigned master_visited = 0;

#define INC_MASTER()       ++master_visited
#define MARK_NODE(info)    (info)->visited = master_visited
#define NODE_VISITED(info) (info)->visited >= master_visited

Michael Beck's avatar
Michael Beck committed
84
85
86
/**
 * get the Load/Store info of a node
 */
87
88
static ldst_info_t *get_ldst_info(ir_node *node, struct obstack *obst)
{
89
	ldst_info_t *info = (ldst_info_t*)get_irn_link(node);
Michael Beck's avatar
Michael Beck committed
90

91
	if (! info) {
92
		info = OALLOCZ(obst, ldst_info_t);
93
94
95
		set_irn_link(node, info);
	}
	return info;
96
}
Michael Beck's avatar
Michael Beck committed
97

98
99
100
/**
 * get the Block info of a node
 */
101
102
static block_info_t *get_block_info(ir_node *node, struct obstack *obst)
{
103
	block_info_t *info = (block_info_t*)get_irn_link(node);
104

105
	if (! info) {
106
		info = OALLOCZ(obst, block_info_t);
107
108
109
		set_irn_link(node, info);
	}
	return info;
110
}
111

Michael Beck's avatar
Michael Beck committed
112
/**
Michael Beck's avatar
Michael Beck committed
113
 * update the projection info for a Load/Store
Michael Beck's avatar
Michael Beck committed
114
 */
115
static unsigned update_projs(ldst_info_t *info, ir_node *proj)
Michael Beck's avatar
Michael Beck committed
116
{
117
	long nr = get_Proj_proj(proj);
Michael Beck's avatar
Michael Beck committed
118

119
	assert(0 <= nr && nr <= MAX_PROJ && "Wrong proj from LoadStore");
Michael Beck's avatar
Michael Beck committed
120

121
122
123
124
125
126
127
128
129
	if (info->projs[nr]) {
		/* there is already one, do CSE */
		exchange(proj, info->projs[nr]);
		return DF_CHANGED;
	}
	else {
		info->projs[nr] = proj;
		return 0;
	}
130
}
Michael Beck's avatar
Michael Beck committed
131
132

/**
133
134
135
136
137
 * update the exception block info for a Load/Store node.
 *
 * @param info   the load/store info struct
 * @param block  the exception handler block for this load/store
 * @param pos    the control flow input of the block
Michael Beck's avatar
Michael Beck committed
138
 */
139
static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
140
{
141
	assert(info->exc_block == NULL && "more than one exception block found");
Michael Beck's avatar
Michael Beck committed
142

143
144
145
	info->exc_block = block;
	info->exc_idx   = pos;
	return 0;
146
}
Michael Beck's avatar
Michael Beck committed
147
148
149

/**
 * walker, collects all Load/Store/Proj nodes
150
 *
151
 * walks from Start -> End
Michael Beck's avatar
Michael Beck committed
152
 */
Michael Beck's avatar
Michael Beck committed
153
static void collect_nodes(ir_node *node, void *env)
Michael Beck's avatar
Michael Beck committed
154
{
155
156
	walk_env_t  *wenv   = (walk_env_t *)env;
	unsigned     opcode = get_irn_opcode(node);
157
158
159
	ir_node     *pred, *blk, *pred_blk;
	ldst_info_t *ldst_info;

160
161
162
	if (opcode == iro_Proj) {
		pred   = get_Proj_pred(node);
		opcode = get_irn_opcode(pred);
163

164
		if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
165
			ldst_info = get_ldst_info(pred, &wenv->obst);
166
167
168
169

			wenv->changes |= update_projs(ldst_info, node);

			/*
170
171
172
173
174
			 * Place the Proj's to the same block as the
			 * predecessor Load. This is always ok and prevents
			 * "non-SSA" form after optimizations if the Proj
			 * is in a wrong block.
			 */
175
176
177
178
179
180
181
			blk      = get_nodes_block(node);
			pred_blk = get_nodes_block(pred);
			if (blk != pred_blk) {
				wenv->changes |= DF_CHANGED;
				set_nodes_block(node, pred_blk);
			}
		}
182
	} else if (opcode == iro_Block) {
183
184
185
		int i;

		for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
186
			ir_node      *pred_block, *proj;
187
			block_info_t *bl_info;
188
189
190
			int          is_exc = 0;

			pred = proj = get_Block_cfgpred(node, i);
191

192
193
			if (is_Proj(proj)) {
				pred   = get_Proj_pred(proj);
Matthias Braun's avatar
Matthias Braun committed
194
				is_exc = is_x_except_Proj(proj);
195
			}
196
197
198
199
200
201

			/* ignore Bad predecessors, they will be removed later */
			if (is_Bad(pred))
				continue;

			pred_block = get_nodes_block(pred);
202
			bl_info    = get_block_info(pred_block, &wenv->obst);
203

204
			if (is_fragile_op(pred) && is_exc)
205
206
207
208
				bl_info->flags |= BLOCK_HAS_EXC;
			else if (is_irn_forking(pred))
				bl_info->flags |= BLOCK_HAS_COND;

209
210
			opcode = get_irn_opcode(pred);
			if (is_exc && (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call)) {
211
				ldst_info = get_ldst_info(pred, &wenv->obst);
212
213
214
215
216

				wenv->changes |= update_exc(ldst_info, node, i);
			}
		}
	}
217
}
Michael Beck's avatar
Michael Beck committed
218

Michael Beck's avatar
Michael Beck committed
219
/**
220
 * Returns an entity if the address ptr points to a constant one.
221
222
223
224
 *
 * @param ptr  the address
 *
 * @return an entity or NULL
Michael Beck's avatar
Michael Beck committed
225
 */
226
static ir_entity *find_constant_entity(ir_node *ptr)
Michael Beck's avatar
Michael Beck committed
227
{
228
	for (;;) {
229
		if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
230
			return get_SymConst_entity(ptr);
231
		} else if (is_Sel(ptr)) {
232
233
234
235
			ir_entity *ent = get_Sel_entity(ptr);
			ir_type   *tp  = get_entity_owner(ent);

			/* Do not fiddle with polymorphism. */
236
			if (is_Class_type(tp) &&
237
238
239
240
241
242
243
244
245
				((get_entity_n_overwrites(ent)    != 0) ||
				(get_entity_n_overwrittenby(ent) != 0)   ) )
				return NULL;

			if (is_Array_type(tp)) {
				/* check bounds */
				int i, n;

				for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
246
247
248
249
					ir_node   *bound;
					ir_tarval *tlower, *tupper;
					ir_node   *index = get_Sel_index(ptr, i);
					ir_tarval *tv    = computed_value(index);
250
251
252
253
254
255
256
257
258
259
260
261
262

					/* check if the index is constant */
					if (tv == tarval_bad)
						return NULL;

					bound  = get_array_lower_bound(tp, i);
					tlower = computed_value(bound);
					bound  = get_array_upper_bound(tp, i);
					tupper = computed_value(bound);

					if (tlower == tarval_bad || tupper == tarval_bad)
						return NULL;

263
					if (tarval_cmp(tv, tlower) == ir_relation_less)
264
						return NULL;
265
					if (tarval_cmp(tupper, tv) == ir_relation_less)
266
267
268
269
270
271
						return NULL;

					/* ok, bounds check finished */
				}
			}

Matthias Braun's avatar
Matthias Braun committed
272
			if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT)
273
274
275
276
				return ent;

			/* try next */
			ptr = get_Sel_ptr(ptr);
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
		} else if (is_Add(ptr)) {
			ir_node *l = get_Add_left(ptr);
			ir_node *r = get_Add_right(ptr);

			if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
				ptr = l;
			else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l))
				ptr = r;
			else
				return NULL;

			/* for now, we support only one addition, reassoc should fold all others */
			if (! is_SymConst(ptr) && !is_Sel(ptr))
				return NULL;
		} else if (is_Sub(ptr)) {
			ir_node *l = get_Sub_left(ptr);
			ir_node *r = get_Sub_right(ptr);

295
			if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
296
297
298
299
300
301
				ptr = l;
			else
				return NULL;
			/* for now, we support only one substraction, reassoc should fold all others */
			if (! is_SymConst(ptr) && !is_Sel(ptr))
				return NULL;
302
303
304
		} else
			return NULL;
	}
305
}
Michael Beck's avatar
Michael Beck committed
306

Michael Beck's avatar
Michael Beck committed
307
308
309
/**
 * Return the Selection index of a Sel node from dimension n
 */
310
311
static long get_Sel_array_index_long(ir_node *n, int dim)
{
312
313
	ir_node *index = get_Sel_index(n, dim);
	return get_tarval_long(get_Const_tarval(index));
314
}
315

316
317
318
typedef struct path_entry {
	ir_entity         *ent;
	struct path_entry *next;
319
	size_t            index;
320
321
} path_entry;

322
323
static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next)
{
324
	path_entry       entry, *p;
325
	ir_entity        *ent, *field;
326
	ir_initializer_t *initializer;
Matthias Braun's avatar
Matthias Braun committed
327
	ir_tarval        *tv;
328
	ir_type          *tp;
329
	size_t           n;
330

331
	entry.next = next;
332
333
	if (is_SymConst(ptr)) {
		/* found the root */
334
		ent         = get_SymConst_entity(ptr);
335
		initializer = get_entity_initializer(ent);
336
		for (p = next; p != NULL;) {
337
338
			if (initializer->kind != IR_INITIALIZER_COMPOUND)
				return NULL;
339
340
			n  = get_initializer_compound_n_entries(initializer);
			tp = get_entity_type(ent);
341

342
343
344
345
346
347
348
349
350
351
			if (is_Array_type(tp)) {
				ent = get_array_element_entity(tp);
				if (ent != p->ent) {
					/* a missing [0] */
					if (0 >= n)
						return NULL;
					initializer = get_initializer_compound_value(initializer, 0);
					continue;
				}
			}
352
			if (p->index >= n)
353
354
				return NULL;
			initializer = get_initializer_compound_value(initializer, p->index);
355
356
357
358
359
360
361
362
363
364
365
366
367

			ent = p->ent;
			p   = p->next;
		}
		tp = get_entity_type(ent);
		while (is_Array_type(tp)) {
			ent = get_array_element_entity(tp);
			tp = get_entity_type(ent);
			/* a missing [0] */
			n  = get_initializer_compound_n_entries(initializer);
			if (0 >= n)
				return NULL;
			initializer = get_initializer_compound_value(initializer, 0);
368
		}
369

370
371
372
373
374
375
376
377
378
		switch (initializer->kind) {
		case IR_INITIALIZER_CONST:
			return get_initializer_const_value(initializer);
		case IR_INITIALIZER_TARVAL:
		case IR_INITIALIZER_NULL:
		default:
			return NULL;
		}
	} else if (is_Sel(ptr)) {
379
380
381
382
		entry.ent = field = get_Sel_entity(ptr);
		tp = get_entity_owner(field);
		if (is_Array_type(tp)) {
			assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
383
			entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
384
		} else {
385
			size_t i, n_members = get_compound_n_members(tp);
386
387
388
389
390
391
392
393
394
395
396
			for (i = 0; i < n_members; ++i) {
				if (get_compound_member(tp, i) == field)
					break;
			}
			if (i >= n_members) {
				/* not found: should NOT happen */
				return NULL;
			}
			entry.index = i;
		}
		return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry);
397
398
399
	}  else if (is_Add(ptr)) {
		ir_mode  *mode;
		unsigned pos;
400

401
402
403
404
405
406
407
408
409
410
		{
			ir_node *l = get_Add_left(ptr);
			ir_node *r = get_Add_right(ptr);
			if (is_Const(r)) {
				ptr = l;
				tv  = get_Const_tarval(r);
			} else {
				ptr = r;
				tv  = get_Const_tarval(l);
			}
411
412
413
		}
ptr_arith:
		mode = get_tarval_mode(tv);
414

415
416
417
418
419
420
		/* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */
		if (is_Sel(ptr)) {
			field = get_Sel_entity(ptr);
		} else {
			field = get_SymConst_entity(ptr);
		}
421

422
423
424
425
426
427
428
429
430
431
432
		/* count needed entries */
		pos = 0;
		for (ent = field;;) {
			tp = get_entity_type(ent);
			if (! is_Array_type(tp))
				break;
			ent = get_array_element_entity(tp);
			++pos;
		}
		/* should be at least ONE entry */
		if (pos == 0)
433
434
			return NULL;

435
436
437
438
439
440
		/* allocate the right number of entries */
		NEW_ARR_A(path_entry, p, pos);

		/* fill them up */
		pos = 0;
		for (ent = field;;) {
Matthias Braun's avatar
Matthias Braun committed
441
442
443
444
			unsigned   size;
			ir_tarval *sz, *tv_index, *tlower, *tupper;
			long       index;
			ir_node   *bound;
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470

			tp = get_entity_type(ent);
			if (! is_Array_type(tp))
				break;
			ent = get_array_element_entity(tp);
			p[pos].ent  = ent;
			p[pos].next = &p[pos + 1];

			size = get_type_size_bytes(get_entity_type(ent));
			sz   = new_tarval_from_long(size, mode);

			tv_index = tarval_div(tv, sz);
			tv       = tarval_mod(tv, sz);

			if (tv_index == tarval_bad || tv == tarval_bad)
				return NULL;

			assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented");
			bound  = get_array_lower_bound(tp, 0);
			tlower = computed_value(bound);
			bound  = get_array_upper_bound(tp, 0);
			tupper = computed_value(bound);

			if (tlower == tarval_bad || tupper == tarval_bad)
				return NULL;

471
			if (tarval_cmp(tv_index, tlower) == ir_relation_less)
472
				return NULL;
473
			if (tarval_cmp(tupper, tv_index) == ir_relation_less)
474
475
476
477
478
479
480
481
482
				return NULL;

			/* ok, bounds check finished */
			index = get_tarval_long(tv_index);
			p[pos].index = index;
			++pos;
		}
		if (! tarval_is_null(tv)) {
			/* hmm, wrong access */
483
			return NULL;
484
485
486
487
488
489
		}
		p[pos - 1].next = next;
		return rec_find_compound_ent_value(ptr, p);
	} else if (is_Sub(ptr)) {
		ir_node *l = get_Sub_left(ptr);
		ir_node *r = get_Sub_right(ptr);
490

491
492
493
494
		ptr = l;
		tv  = get_Const_tarval(r);
		tv  = tarval_neg(tv);
		goto ptr_arith;
495
	}
496
	return NULL;
497
498
}

499
500
static ir_node *find_compound_ent_value(ir_node *ptr)
{
501
502
503
	return rec_find_compound_ent_value(ptr, NULL);
}

504
505
506
507
/* forward */
static void reduce_adr_usage(ir_node *ptr);

/**
Christoph Mallon's avatar
Christoph Mallon committed
508
 * Update a Load that may have lost its users.
509
 */
510
511
static void handle_load_update(ir_node *load)
{
512
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
513

514
515
516
	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return;
517

518
519
520
	if (! info->projs[pn_Load_res] && ! info->projs[pn_Load_X_except]) {
		ir_node *ptr = get_Load_ptr(load);
		ir_node *mem = get_Load_mem(load);
521

Christoph Mallon's avatar
Christoph Mallon committed
522
		/* a Load whose value is neither used nor exception checked, remove it */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
523
		exchange(info->projs[pn_Load_M], mem);
524
		if (info->projs[pn_Load_X_regular])
525
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
526
		kill_node(load);
527
528
		reduce_adr_usage(ptr);
	}
529
}
530
531

/**
Christoph Mallon's avatar
Christoph Mallon committed
532
 * A use of an address node has vanished. Check if this was a Proj
533
534
 * node and update the counters.
 */
535
536
static void reduce_adr_usage(ir_node *ptr)
{
537
538
539
540
541
	ir_node *pred;
	if (!is_Proj(ptr))
		return;
	if (get_irn_n_edges(ptr) > 0)
		return;
542

543
544
545
	/* this Proj is dead now */
	pred = get_Proj_pred(ptr);
	if (is_Load(pred)) {
546
		ldst_info_t *info = (ldst_info_t*)get_irn_link(pred);
547
		info->projs[get_Proj_proj(ptr)] = NULL;
548

549
550
		/* this node lost its result proj, handle that */
		handle_load_update(pred);
551
	}
552
}
553

554
555
556
557
/**
 * Check, if an already existing value of mode old_mode can be converted
 * into the needed one new_mode without loss.
 */
558
559
static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode)
{
560
561
	unsigned old_size;
	unsigned new_size;
562
	if (old_mode == new_mode)
563
564
565
566
		return true;

	old_size = get_mode_size_bits(old_mode);
	new_size = get_mode_size_bits(new_mode);
567
568

	/* if both modes are two-complement ones, we can always convert the
569
570
571
	   Stored value into the needed one. (on big endian machines we currently
	   only support this for modes of same size) */
	if (old_size >= new_size &&
572
		  get_mode_arithmetic(old_mode) == irma_twos_complement &&
573
574
575
576
577
578
579
		  get_mode_arithmetic(new_mode) == irma_twos_complement &&
		  (!be_get_backend_param()->byte_order_big_endian
	        || old_size == new_size)) {
		return true;
	}
	return false;
}
580

Michael Beck's avatar
Michael Beck committed
581
/**
582
 * Check whether a Call is at least pure, i.e. does only read memory.
583
 */
584
585
static unsigned is_Call_pure(ir_node *call)
{
586
587
588
589
590
591
592
593
	ir_type *call_tp = get_Call_type(call);
	unsigned prop = get_method_additional_properties(call_tp);

	/* check first the call type */
	if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
		/* try the called entity */
		ir_node *ptr = get_Call_ptr(call);

594
595
		if (is_SymConst_addr_ent(ptr)) {
			ir_entity *ent = get_SymConst_entity(ptr);
596
597
598
599
600

			prop = get_entity_additional_properties(ent);
		}
	}
	return (prop & (mtp_property_const|mtp_property_pure)) != 0;
601
}
602

Michael Beck's avatar
Michael Beck committed
603
static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset)
604
{
Michael Beck's avatar
Michael Beck committed
605
606
	ir_mode *mode  = get_irn_mode(ptr);
	long    offset = 0;
607
608

	/* TODO: long might not be enough, we should probably use some tarval thingy... */
Michael Beck's avatar
Michael Beck committed
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
	for (;;) {
		if (is_Add(ptr)) {
			ir_node *l = get_Add_left(ptr);
			ir_node *r = get_Add_right(ptr);

			if (get_irn_mode(l) != mode || !is_Const(r))
				break;

			offset += get_tarval_long(get_Const_tarval(r));
			ptr     = l;
		} else if (is_Sub(ptr)) {
			ir_node *l = get_Sub_left(ptr);
			ir_node *r = get_Sub_right(ptr);

			if (get_irn_mode(l) != mode || !is_Const(r))
				break;

			offset -= get_tarval_long(get_Const_tarval(r));
			ptr     = l;
		} else if (is_Sel(ptr)) {
			ir_entity *ent = get_Sel_entity(ptr);
			ir_type   *tp  = get_entity_owner(ent);

			if (is_Array_type(tp)) {
				int     size;
				ir_node *index;

				/* only one dimensional arrays yet */
				if (get_Sel_n_indexs(ptr) != 1)
					break;
				index = get_Sel_index(ptr, 0);
				if (! is_Const(index))
					break;

				tp = get_entity_type(ent);
				if (get_type_state(tp) != layout_fixed)
					break;

				size    = get_type_size_bytes(tp);
				offset += size * get_tarval_long(get_Const_tarval(index));
			} else {
				if (get_type_state(tp) != layout_fixed)
					break;
				offset += get_entity_offset(ent);
			}
			ptr = get_Sel_ptr(ptr);
		} else
656
657
658
			break;
	}

Michael Beck's avatar
Michael Beck committed
659
660
	*pOffset = offset;
	return ptr;
661
662
}

Michael Beck's avatar
Michael Beck committed
663
static int try_load_after_store(ir_node *load,
664
665
666
667
		ir_node *load_base_ptr, long load_offset, ir_node *store)
{
	ldst_info_t *info;
	ir_node *store_ptr      = get_Store_ptr(store);
Michael Beck's avatar
Michael Beck committed
668
669
	long     store_offset;
	ir_node *store_base_ptr = get_base_and_offset(store_ptr, &store_offset);
670
671
672
673
674
675
676
677
678
679
680
681
	ir_node *store_value;
	ir_mode *store_mode;
	ir_node *load_ptr;
	ir_mode *load_mode;
	long     load_mode_len;
	long     store_mode_len;
	long     delta;
	int      res;

	if (load_base_ptr != store_base_ptr)
		return 0;

Michael Beck's avatar
Michael Beck committed
682
683
	load_mode      = get_Load_mode(load);
	load_mode_len  = get_mode_size_bytes(load_mode);
684
685
	store_mode     = get_irn_mode(get_Store_value(store));
	store_mode_len = get_mode_size_bytes(store_mode);
Michael Beck's avatar
Michael Beck committed
686
	delta          = load_offset - store_offset;
687
	store_value    = get_Store_value(store);
688

689
690
	if (delta < 0 || delta+load_mode_len > store_mode_len)
		return 0;
691

692
693
694
	if (store_mode != load_mode &&
	    get_mode_arithmetic(store_mode) == irma_twos_complement &&
	    get_mode_arithmetic(load_mode)  == irma_twos_complement) {
Michael Beck's avatar
Michael Beck committed
695

696
		/* produce a shift to adjust offset delta */
697
698
699
700
701
702
		unsigned const shift = be_get_backend_param()->byte_order_big_endian
			? store_mode_len - load_mode_len - delta
			: delta;
		if (shift != 0) {
			ir_graph *const irg  = get_irn_irg(load);
			ir_node  *const cnst = new_r_Const_long(irg, mode_Iu, shift * 8);
703
			store_value = new_r_Shr(get_nodes_block(load),
704
705
706
									store_value, cnst, store_mode);
		}

707
708
709
710
		store_value = new_r_Conv(get_nodes_block(load), store_value, load_mode);
	} else {
		/* we would need some kind of bitcast node here */
		return 0;
711
712
	}

Michael Beck's avatar
Michael Beck committed
713
714
	DBG_OPT_RAW(load, store_value);

715
	info = (ldst_info_t*)get_irn_link(load);
716
717
718
719
720
721
	if (info->projs[pn_Load_M])
		exchange(info->projs[pn_Load_M], get_Load_mem(load));

	res = 0;
	/* no exception */
	if (info->projs[pn_Load_X_except]) {
722
		ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
723
		exchange( info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
724
725
726
		res |= CF_CHANGED;
	}
	if (info->projs[pn_Load_X_regular]) {
727
		exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
728
729
730
731
732
733
734
735
736
737
738
739
		res |= CF_CHANGED;
	}

	if (info->projs[pn_Load_res])
		exchange(info->projs[pn_Load_res], store_value);

	load_ptr = get_Load_ptr(load);
	kill_node(load);
	reduce_adr_usage(load_ptr);
	return res | DF_CHANGED;
}

740
741
742
743
/**
 * Follow the memory chain as long as there are only Loads,
 * alias free Stores, and constant Calls and try to replace the
 * current Load by a previous ones.
Michael Beck's avatar
Michael Beck committed
744
745
746
747
748
749
 * Note that in unreachable loops it might happen that we reach
 * load again, as well as we can fall into a cycle.
 * We break such cycles using a special visited flag.
 *
 * INC_MASTER() must be called before dive into
 */
750
751
static unsigned follow_Mem_chain(ir_node *load, ir_node *curr)
{
Michael Beck's avatar
Michael Beck committed
752
	unsigned    res = 0;
753
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
754
755
756
757
	ir_node     *pred;
	ir_node     *ptr       = get_Load_ptr(load);
	ir_node     *mem       = get_Load_mem(load);
	ir_mode     *load_mode = get_Load_mode(load);
758
759

	for (pred = curr; load != pred; ) {
760
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
761
762

		/*
763
764
		 * a Load immediately after a Store -- a read after write.
		 * We may remove the Load, if both Load & Store does not have an
Matthias Braun's avatar
Matthias Braun committed
765
		 * exception handler OR they are in the same Block. In the latter
766
767
768
769
770
		 * case the Load cannot throw an exception when the previous Store was
		 * quiet.
		 *
		 * Why we need to check for Store Exception? If the Store cannot
		 * be executed (ROM) the exception handler might simply jump into
Matthias Braun's avatar
Matthias Braun committed
771
		 * the load Block :-(
772
773
		 * We could make it a little bit better if we would know that the
		 * exception handler of the Store jumps directly to the end...
774
		 */
775
776
		if (is_Store(pred) && ((pred_info->projs[pn_Store_X_except] == NULL
				&& info->projs[pn_Load_X_except] == NULL)
Matthias Braun's avatar
Matthias Braun committed
777
				|| get_nodes_block(load) == get_nodes_block(pred)))
778
		{
Michael Beck's avatar
Michael Beck committed
779
780
781
782
783
			long    load_offset;
			ir_node *base_ptr = get_base_and_offset(ptr, &load_offset);
			int     changes   = try_load_after_store(load, base_ptr, load_offset, pred);

			if (changes != 0)
784
				return res | changes;
785
		} else if (is_Load(pred) && get_Load_ptr(pred) == ptr &&
786
		           can_use_stored_value(get_Load_mode(pred), load_mode)) {
787
788
			/*
			 * a Load after a Load -- a read after read.
Matthias Braun's avatar
Matthias Braun committed
789
790
791
792
			 * We may remove the second Load, if it does not have an exception
			 * handler OR they are in the same Block. In the later case
			 * the Load cannot throw an exception when the previous Load was
			 * quiet.
793
			 *
Matthias Braun's avatar
Matthias Braun committed
794
795
796
			 * Here, there is no need to check if the previous Load has an
			 * exception hander because they would have exact the same
			 * exception...
797
798
799
			 *
			 * TODO: implement load-after-load with different mode for big
			 *       endian
800
			 */
Matthias Braun's avatar
Matthias Braun committed
801
802
			if (info->projs[pn_Load_X_except] == NULL
					|| get_nodes_block(load) == get_nodes_block(pred)) {
803
804
				ir_node *value;

805
806
				DBG_OPT_RAR(load, pred);

807
808
809
810
				/* the result is used */
				if (info->projs[pn_Load_res]) {
					if (pred_info->projs[pn_Load_res] == NULL) {
						/* create a new Proj again */
811
						pred_info->projs[pn_Load_res] = new_r_Proj(pred, get_Load_mode(pred), pn_Load_res);
812
813
					}
					value = pred_info->projs[pn_Load_res];
814
815
816

					/* add an convert if needed */
					if (get_Load_mode(pred) != load_mode) {
817
						value = new_r_Conv(get_nodes_block(load), value, load_mode);
818
819
					}

820
					exchange(info->projs[pn_Load_res], value);
821
822
				}

823
824
825
				if (info->projs[pn_Load_M])
					exchange(info->projs[pn_Load_M], mem);

826
827
				/* no exception */
				if (info->projs[pn_Load_X_except]) {
828
					ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
829
					exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
830
831
					res |= CF_CHANGED;
				}
832
				if (info->projs[pn_Load_X_regular]) {
833
					exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
834
835
					res |= CF_CHANGED;
				}
836

837
				kill_node(load);
838
839
840
841
842
				reduce_adr_usage(ptr);
				return res |= DF_CHANGED;
			}
		}

843
		if (is_Store(pred)) {
844
			/* check if we can pass through this store */
845
846
847
			ir_alias_relation rel = get_alias_relation(
				get_Store_ptr(pred),
				get_irn_mode(get_Store_value(pred)),
848
				ptr, load_mode);
849
			/* if the might be an alias, we cannot pass this Store */
Michael Beck's avatar
Michael Beck committed
850
			if (rel != ir_no_alias)
851
852
				break;
			pred = skip_Proj(get_Store_mem(pred));
853
		} else if (is_Load(pred)) {
854
			pred = skip_Proj(get_Load_mem(pred));
855
856
857
858
859
860
861
862
863
		} else if (is_Call(pred)) {
			if (is_Call_pure(pred)) {
				/* The called graph is at least pure, so there are no Store's
				   in it. We can handle it like a Load and skip it. */
				pred = skip_Proj(get_Call_mem(pred));
			} else {
				/* there might be Store's in the graph, stop here */
				break;
			}
864
865
866
867
868
869
870
871
872
873
874
		} else {
			/* follow only Load chains */
			break;
		}

		/* check for cycles */
		if (NODE_VISITED(pred_info))
			break;
		MARK_NODE(pred_info);
	}

875
	if (is_Sync(pred)) {
876
877
878
879
880
881
		int i;

		/* handle all Sync predecessors */
		for (i = get_Sync_n_preds(pred) - 1; i >= 0; --i) {
			res |= follow_Mem_chain(load, skip_Proj(get_Sync_pred(pred, i)));
			if (res)
882
				return res;
883
884
885
886
		}
	}

	return res;
887
}
Michael Beck's avatar
Michael Beck committed
888

889
890
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
891
892
893
894
895
	ir_mode  *c_mode = get_irn_mode(c);
	ir_mode  *l_mode = get_Load_mode(load);
	ir_node  *block  = get_nodes_block(load);
	dbg_info *dbgi   = get_irn_dbg_info(load);
	ir_node  *res    = copy_const_value(dbgi, c, block);
896
897
898
899
900

	if (c_mode != l_mode) {
		/* check, if the mode matches OR can be easily converted info */
		if (is_reinterpret_cast(c_mode, l_mode)) {
			/* copy the value from the const code irg and cast it */
901
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
902
903
		} else {
			return NULL;
904
905
906
		}
	}
	return res;
907
}
908

Michael Beck's avatar
Michael Beck committed
909
910
/**
 * optimize a Load
911
912
 *
 * @param load  the Load node
Michael Beck's avatar
Michael Beck committed
913
 */
914
static unsigned optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
915
{
916
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
917
918
919
920
	ir_node     *mem, *ptr, *value;
	ir_entity   *ent;
	long        dummy;
	unsigned    res = 0;
921
922
923
924
925
926
927
928
929

	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return 0;

	/* the address of the load to be optimized */
	ptr = get_Load_ptr(load);

	/* The mem of the Load. Must still be returned after optimization. */
Christoph Mallon's avatar
Christoph Mallon committed
930
	mem = get_Load_mem(load);
931

932
933
934
	if (info->projs[pn_Load_res] == NULL
			&& info->projs[pn_Load_X_except] == NULL) {
		/* the value is never used and we don't care about exceptions, remove */
935
936
		exchange(info->projs[pn_Load_M], mem);

937
938
		if (info->projs[pn_Load_X_regular]) {
			/* should not happen, but if it does, remove it */
939
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
940
941
			res |= CF_CHANGED;
		}
942
		kill_node(load);
943
944
945
946
		reduce_adr_usage(ptr);
		return res | DF_CHANGED;
	}

Matthias Braun's avatar
Matthias Braun committed
947
948
949
950
951
952
953
954
	value = NULL;
	/* check if we can determine the entity that will be loaded */
	ent = find_constant_entity(ptr);
	if (ent != NULL
			&& get_entity_visibility(ent) != ir_visibility_external) {
		/* a static allocation that is not external: there should be NO
		 * exception when loading even if we cannot replace the load itself.
		 */
Christoph Mallon's avatar
Christoph Mallon committed
955

Matthias Braun's avatar
Matthias Braun committed
956
957
958
959
960
961
962
963
964
965
966
967
		/* no exception, clear the info field as it might be checked later again */
		if (info->projs[pn_Load_X_except]) {
			ir_graph *irg = get_irn_irg(load);
			exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
			info->projs[pn_Load_X_except] = NULL;
			res |= CF_CHANGED;
		}
		if (info->projs[pn_Load_X_regular]) {
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
			info->projs[pn_Load_X_regular] = NULL;
			res |= CF_CHANGED;
		}
Michael Beck's avatar
Michael Beck committed
968

Matthias Braun's avatar
Matthias Braun committed
969
970
971
972
973
974
975
976
		if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT) {
			if (has_entity_initializer(ent)) {
				/* new style initializer */
				value = find_compound_ent_value(ptr);
			}
			if (value != NULL) {
				ir_graph *irg = get_irn_irg(load);
				value = can_replace_load_by_const(load, value);
977
				if (value != NULL && is_Sel(ptr)) {
Matthias Braun's avatar
Matthias Braun committed
978
979
980
					/* frontend has inserted masking operations after bitfield accesses,
					 * so we might have to shift the const. */
					unsigned char bit_offset = get_entity_offset_bits_remainder(get_Sel_entity(ptr));
981
982
983
984
985
986
987
988
989
990
					if (bit_offset != 0) {
						if (is_Const(value)) {
							ir_tarval *tv_old = get_Const_tarval(value);
							ir_tarval *tv_offset = new_tarval_from_long(bit_offset, mode_Bu);
							ir_tarval *tv_new = tarval_shl(tv_old, tv_offset);
							value = new_r_Const(irg, tv_new);
						} else {
							value = NULL;
						}
					}
Andreas Zwinkau's avatar
Andreas Zwinkau committed
991
				}
Michael Beck's avatar
Michael Beck committed
992
			}
993
		}
Michael Beck's avatar
Michael Beck committed
994
995
996
	}
	if (value != NULL) {
		/* we completely replace the load by this value */
997
		if (info->projs[pn_Load_X_except]) {
998
			ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
999
			exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
1000
			info->projs[pn_Load_X_except] = NULL;
1001
1002
1003
			res |= CF_CHANGED;
		}
		if (info->projs[pn_Load_X_regular]) {
1004
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1005
1006
			info->projs[pn_Load_X_regular] = NULL;
			res |= CF_CHANGED;
1007
		}
Michael Beck's avatar
Michael Beck committed
1008
1009
1010
1011
1012
1013
1014
1015
		if (info->projs[pn_Load_M]) {
			exchange(info->projs[pn_Load_M], mem);
			res |= DF_CHANGED;
		}
		if (info->projs[pn_Load_res]) {
			exchange(info->projs[pn_Load_res], value);
			res |= DF_CHANGED;
		}
1016
		kill_node(load);
1017
		reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
1018
		return res;
1019
1020
1021
	}

	/* Check, if the address of this load is used more than once.
Michael Beck's avatar
Michael Beck committed
1022
	 * If not, more load cannot be removed in any case. */
1023
	if (get_irn_n_edges(ptr) <= 1 && get_irn_n_edges(get_base_and_offset(ptr, &dummy)) <= 1)
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
		return res;

	/*
	 * follow the memory chain as long as there are only Loads
	 * and try to replace current Load or Store by a previous one.
	 * Note that in unreachable loops it might happen that we reach
	 * load again, as well as we can fall into a cycle.
	 * We break such cycles using a special visited flag.
	 */
	INC_MASTER();
	res = follow_Mem_chain(load, skip_Proj(mem));
	return res;
1036
}
Michael Beck's avatar
Michael Beck committed
1037

1038
1039
1040
1041
1042
1043
1044
/**
 * Check whether a value of mode new_mode would completely overwrite a value
 * of mode old_mode in memory.
 */
static int is_completely_overwritten(ir_mode *old_mode, ir_mode *new_mode)
{
	return get_mode_size_bits(new_mode) >= get_mode_size_bits(old_mode);
1045
}
1046

1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
/**
 * Check whether small is a part of large (starting at same address).
 */
static int is_partially_same(ir_node *small, ir_node *large)
{
	ir_mode *sm = get_irn_mode(small);
	ir_mode *lm = get_irn_mode(large);

	/* FIXME: Check endianness */
	return is_Conv(small) && get_Conv_op(small) == large
	    && get_mode_size_bytes(sm) < get_mode_size_bytes(lm)