ldstopt.c 56.5 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
695
696
697
698
699
700
701
702
703
704
705
	if (store_mode != load_mode) {
		if (get_mode_arithmetic(store_mode) == irma_twos_complement &&
		    get_mode_arithmetic(load_mode)  == irma_twos_complement) {

			/* produce a shift to adjust offset delta */
			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);
				store_value = new_r_Shr(get_nodes_block(load),
							store_value, cnst, store_mode);
			}
706

707
708
709
710
711
			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;
		}
712
713
	}

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

716
	info = (ldst_info_t*)get_irn_link(load);
717
718
719
720
721
722
	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]) {
723
		ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
724
		exchange( info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
725
726
727
		res |= CF_CHANGED;
	}
	if (info->projs[pn_Load_X_regular]) {
728
		exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
729
730
731
732
733
734
735
736
737
738
739
740
		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;
}

741
742
743
744
/**
 * 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
745
746
747
748
749
750
 * 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
 */
751
752
static unsigned follow_Mem_chain(ir_node *load, ir_node *curr)
{
Michael Beck's avatar
Michael Beck committed
753
	unsigned    res = 0;
754
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
755
756
757
758
	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);
759
760

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

		/*
764
765
		 * 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
766
		 * exception handler OR they are in the same Block. In the latter
767
768
769
770
771
		 * 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
772
		 * the load Block :-(
773
774
		 * We could make it a little bit better if we would know that the
		 * exception handler of the Store jumps directly to the end...
775
		 */
776
777
		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
778
				|| get_nodes_block(load) == get_nodes_block(pred)))
779
		{
Michael Beck's avatar
Michael Beck committed
780
781
782
783
784
			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)
785
				return res | changes;
786
		} else if (is_Load(pred) && get_Load_ptr(pred) == ptr &&
787
		           can_use_stored_value(get_Load_mode(pred), load_mode)) {
788
789
			/*
			 * a Load after a Load -- a read after read.
Matthias Braun's avatar
Matthias Braun committed
790
791
792
793
			 * 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.
794
			 *
Matthias Braun's avatar
Matthias Braun committed
795
796
797
			 * Here, there is no need to check if the previous Load has an
			 * exception hander because they would have exact the same
			 * exception...
798
799
800
			 *
			 * TODO: implement load-after-load with different mode for big
			 *       endian
801
			 */
Matthias Braun's avatar
Matthias Braun committed
802
803
			if (info->projs[pn_Load_X_except] == NULL
					|| get_nodes_block(load) == get_nodes_block(pred)) {
804
805
				ir_node *value;

806
807
				DBG_OPT_RAR(load, pred);

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

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

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

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

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

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

844
		if (is_Store(pred)) {
845
			/* check if we can pass through this store */
846
847
848
			ir_alias_relation rel = get_alias_relation(
				get_Store_ptr(pred),
				get_irn_mode(get_Store_value(pred)),
849
				ptr, load_mode);
850
			/* if the might be an alias, we cannot pass this Store */
Michael Beck's avatar
Michael Beck committed
851
			if (rel != ir_no_alias)
852
853
				break;
			pred = skip_Proj(get_Store_mem(pred));
854
		} else if (is_Load(pred)) {
855
			pred = skip_Proj(get_Load_mem(pred));
856
857
858
859
860
861
862
863
864
		} 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;
			}
865
866
867
868
869
870
871
872
873
874
875
		} else {
			/* follow only Load chains */
			break;
		}

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

876
	if (is_Sync(pred)) {
877
878
879
880
881
882
		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)
883
				return res;
884
885
886
887
		}
	}

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

890
891
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
892
893
894
895
896
	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);
897
898
899
900
901

	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 */
902
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
903
904
		} else {
			return NULL;
905
906
907
		}
	}
	return res;
908
}
909

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

	/* 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
931
	mem = get_Load_mem(load);
932

933
934
935
	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 */
936
937
		exchange(info->projs[pn_Load_M], mem);

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

Matthias Braun's avatar
Matthias Braun committed
948
949
950
951
952
953
954
955
	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
956

Matthias Braun's avatar
Matthias Braun committed
957
958
959
960
961
962
963
964
965
966
967
968
		/* 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
969

Matthias Braun's avatar
Matthias Braun committed
970
971
972
973
974
975
976
977
		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);
978
				if (value != NULL && is_Sel(ptr)) {
Matthias Braun's avatar
Matthias Braun committed
979
980
981
					/* 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));
982
983
984
985
986
987
988
989
990
991
					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
992
				}
Michael Beck's avatar
Michael Beck committed
993
			}
994
		}
Michael Beck's avatar
Michael Beck committed
995
996
997
	}
	if (value != NULL) {
		/* we completely replace the load by this value */
998
		if (info->projs[pn_Load_X_except]) {
999
			ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
1000
			exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
1001
			info->projs[pn_Load_X_except] = NULL;
1002
1003
1004
			res |= CF_CHANGED;
		}
		if (info->projs[pn_Load_X_regular]) {
1005
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1006
1007
			info->projs[pn_Load_X_regular] = NULL;
			res |= CF_CHANGED;
1008
		}
Michael Beck's avatar
Michael Beck committed
1009
1010
1011
1012
1013
1014
1015
1016
		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;
		}
1017
		kill_node(load);
1018
		reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
1019
		return res;
1020
1021
1022
	}

	/* Check, if the address of this load is used more than once.
Michael Beck's avatar
Michael Beck committed
1023
	 * If not, more load cannot be removed in any case. */
1024
	if (get_irn_n_edges(ptr) <= 1 && get_irn_n_edges(get_base_and_offset(ptr, &dummy)) <= 1)
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
		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;
1037
}
Michael Beck's avatar
Michael Beck committed
1038

1039
1040
1041
1042
1043
1044
1045
/**
 * 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);
1046
}
1047

1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
/**
 * 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)
	    && get_mode_arithmetic(sm) == irma_twos_complement
1060
	    && get_mode_arithmetic(lm) == irma_twos_complement;
1061
}
1062