ldstopt.c 56.2 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 "error.h"
14
#include "iroptimize.h"
15
16
17
18
19
20
21
#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"
22
#include "irtools.h"
23
24
25
26
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
27
#include "array_t.h"
28
#include "irhooks.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
29
#include "iredges.h"
30
#include "irmemory.h"
31
#include "irnodehashmap.h"
32
#include "irgopt.h"
33
#include "set.h"
Matthias Braun's avatar
Matthias Braun committed
34
#include "be.h"
35
36
37
38
#include "debug.h"

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

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

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

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

55
/** A Load/Store info. */
56
typedef struct ldst_info_t {
57
	ir_node  *projs[MAX_PROJ+1];  /**< list of Proj's of this node */
58
59
60
	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
61
62
} ldst_info_t;

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

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

78
79
80
81
82
83
84
/** 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
85
86
87
/**
 * get the Load/Store info of a node
 */
88
89
static ldst_info_t *get_ldst_info(ir_node *node, struct obstack *obst)
{
90
	ldst_info_t *info = (ldst_info_t*)get_irn_link(node);
Michael Beck's avatar
Michael Beck committed
91

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

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

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

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

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

122
123
124
125
126
127
128
129
130
	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;
	}
131
}
Michael Beck's avatar
Michael Beck committed
132
133

/**
134
135
136
137
138
 * 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
139
 */
140
static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
141
{
142
	assert(info->exc_block == NULL && "more than one exception block found");
Michael Beck's avatar
Michael Beck committed
143

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

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

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

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

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

			/*
171
172
173
174
175
			 * 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.
			 */
176
177
178
179
180
181
182
			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);
			}
		}
183
	} else if (opcode == iro_Block) {
184
185
186
		int i;

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

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

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

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

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

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

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

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

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

			/* Do not fiddle with polymorphism. */
237
			if (is_Class_type(tp) &&
238
239
240
241
242
243
244
245
246
				((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
247
248
249
250
					ir_node   *bound;
					ir_tarval *tlower, *tupper;
					ir_node   *index = get_Sel_index(ptr, i);
					ir_tarval *tv    = computed_value(index);
251
252
253
254
255
256
257
258
259
260
261
262
263

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

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

					/* ok, bounds check finished */
				}
			}

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

			/* try next */
			ptr = get_Sel_ptr(ptr);
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
		} 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);

296
			if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
297
298
299
300
301
302
				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;
303
304
305
		} else
			return NULL;
	}
306
}
Michael Beck's avatar
Michael Beck committed
307

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

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

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

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

343
344
345
346
347
348
349
350
351
352
			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;
				}
			}
353
			if (p->index >= n)
354
355
				return NULL;
			initializer = get_initializer_compound_value(initializer, p->index);
356
357
358
359
360
361
362
363
364
365
366
367
368

			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);
369
		}
370

371
372
373
374
375
376
377
378
379
		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)) {
380
381
382
383
		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");
384
			entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
385
		} else {
386
			size_t i, n_members = get_compound_n_members(tp);
387
388
389
390
391
392
393
394
395
396
397
			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);
398
399
400
	}  else if (is_Add(ptr)) {
		ir_mode  *mode;
		unsigned pos;
401

402
403
404
405
406
407
408
409
410
411
		{
			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);
			}
412
413
414
		}
ptr_arith:
		mode = get_tarval_mode(tv);
415

416
417
418
419
420
421
		/* 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);
		}
422

423
424
425
426
427
428
429
430
431
432
433
		/* 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)
434
435
			return NULL;

436
437
438
439
440
441
		/* 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
442
443
444
445
			unsigned   size;
			ir_tarval *sz, *tv_index, *tlower, *tupper;
			long       index;
			ir_node   *bound;
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
471

			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;

472
			if (tarval_cmp(tv_index, tlower) == ir_relation_less)
473
				return NULL;
474
			if (tarval_cmp(tupper, tv_index) == ir_relation_less)
475
476
477
478
479
480
481
482
483
				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 */
484
			return NULL;
485
486
487
488
489
490
		}
		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);
491

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

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

505
/* forward */
506
static void reduce_node_usage(ir_node *ptr);
507
508

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

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

519
520
521
	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);
522

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

/**
533
 * A use of a node has vanished. Check if this was a Proj
534
535
 * node and update the counters.
 */
536
static void reduce_node_usage(ir_node *ptr)
537
{
538
539
540
541
542
	ir_node *pred;
	if (!is_Proj(ptr))
		return;
	if (get_irn_n_edges(ptr) > 0)
		return;
543

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

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

555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
/**
 * Kill a Load or Store and all other nodes which are not needed after
 * it has been killed.
 */
static void kill_and_reduce_usage(ir_node *node) {
	ir_node *ptr;
	ir_node *value = NULL;

	switch(get_irn_opcode(node)) {
	case iro_Load:
		ptr = get_Load_ptr(node);
		break;
	case iro_Store:
		ptr   = get_Store_ptr(node);
		value = get_Store_value(node);
		break;
	default:
		panic("Cannot handle node %+F", node);
	}

	kill_node(node);
	reduce_node_usage(ptr);
	if (value != NULL) {
		reduce_node_usage(value);
	}
}

582
583
584
585
/**
 * Check, if an already existing value of mode old_mode can be converted
 * into the needed one new_mode without loss.
 */
586
587
static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode)
{
588
589
	unsigned old_size;
	unsigned new_size;
590
	if (old_mode == new_mode)
591
592
593
594
		return true;

	old_size = get_mode_size_bits(old_mode);
	new_size = get_mode_size_bits(new_mode);
595
596

	/* if both modes are two-complement ones, we can always convert the
597
598
599
	   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 &&
600
		  get_mode_arithmetic(old_mode) == irma_twos_complement &&
601
602
603
604
605
606
607
		  get_mode_arithmetic(new_mode) == irma_twos_complement &&
		  (!be_get_backend_param()->byte_order_big_endian
	        || old_size == new_size)) {
		return true;
	}
	return false;
}
608

Michael Beck's avatar
Michael Beck committed
609
/**
610
 * Check whether a Call is at least pure, i.e. does only read memory.
611
 */
612
613
static unsigned is_Call_pure(ir_node *call)
{
614
615
616
617
618
619
620
621
	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);

622
623
		if (is_SymConst_addr_ent(ptr)) {
			ir_entity *ent = get_SymConst_entity(ptr);
624
625
626
627
628

			prop = get_entity_additional_properties(ent);
		}
	}
	return (prop & (mtp_property_const|mtp_property_pure)) != 0;
629
}
630

Michael Beck's avatar
Michael Beck committed
631
static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset)
632
{
Michael Beck's avatar
Michael Beck committed
633
634
	ir_mode *mode  = get_irn_mode(ptr);
	long    offset = 0;
635
636

	/* TODO: long might not be enough, we should probably use some tarval thingy... */
Michael Beck's avatar
Michael Beck committed
637
638
639
640
641
642
643
644
645
646
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
	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
684
685
686
			break;
	}

Michael Beck's avatar
Michael Beck committed
687
688
	*pOffset = offset;
	return ptr;
689
690
}

Michael Beck's avatar
Michael Beck committed
691
static int try_load_after_store(ir_node *load,
692
693
694
695
		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
696
697
	long     store_offset;
	ir_node *store_base_ptr = get_base_and_offset(store_ptr, &store_offset);
698
699
700
701
702
703
704
705
706
707
708
	ir_node *store_value;
	ir_mode *store_mode;
	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
709
710
	load_mode      = get_Load_mode(load);
	load_mode_len  = get_mode_size_bytes(load_mode);
711
712
	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
713
	delta          = load_offset - store_offset;
714
	store_value    = get_Store_value(store);
715

716
717
	if (delta < 0 || delta+load_mode_len > store_mode_len)
		return 0;
718

719
720
721
722
723
724
725
726
727
728
729
730
731
732
	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);
			}
733

734
735
736
737
738
			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;
		}
739
740
	}

Michael Beck's avatar
Michael Beck committed
741
742
	DBG_OPT_RAW(load, store_value);

743
	info = (ldst_info_t*)get_irn_link(load);
744
745
746
747
748
749
	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]) {
750
		ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
751
		exchange( info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
752
753
754
		res |= CF_CHANGED;
	}
	if (info->projs[pn_Load_X_regular]) {
755
		exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
756
757
758
759
760
761
		res |= CF_CHANGED;
	}

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

762
	kill_and_reduce_usage(load);
763
764
765
	return res | DF_CHANGED;
}

766
767
768
769
/**
 * 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
770
771
772
773
774
775
 * 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
 */
776
777
static unsigned follow_Mem_chain(ir_node *load, ir_node *curr)
{
Michael Beck's avatar
Michael Beck committed
778
	unsigned    res = 0;
779
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
780
781
782
783
	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);
784
785

	for (pred = curr; load != pred; ) {
786
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
787
788

		/*
789
790
		 * 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
791
		 * exception handler OR they are in the same Block. In the latter
792
793
794
795
796
		 * 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
797
		 * the load Block :-(
798
799
		 * We could make it a little bit better if we would know that the
		 * exception handler of the Store jumps directly to the end...
800
		 */
801
802
		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
803
				|| get_nodes_block(load) == get_nodes_block(pred)))
804
		{
Michael Beck's avatar
Michael Beck committed
805
806
807
808
809
			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)
810
				return res | changes;
811
		} else if (is_Load(pred) && get_Load_ptr(pred) == ptr &&
812
		           can_use_stored_value(get_Load_mode(pred), load_mode)) {
813
814
			/*
			 * a Load after a Load -- a read after read.
Matthias Braun's avatar
Matthias Braun committed
815
816
817
818
			 * 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.
819
			 *
Matthias Braun's avatar
Matthias Braun committed
820
821
822
			 * Here, there is no need to check if the previous Load has an
			 * exception hander because they would have exact the same
			 * exception...
823
824
825
			 *
			 * TODO: implement load-after-load with different mode for big
			 *       endian
826
			 */
Matthias Braun's avatar
Matthias Braun committed
827
828
			if (info->projs[pn_Load_X_except] == NULL
					|| get_nodes_block(load) == get_nodes_block(pred)) {
829
830
				ir_node *value;

831
832
				DBG_OPT_RAR(load, pred);

833
834
835
836
				/* the result is used */
				if (info->projs[pn_Load_res]) {
					if (pred_info->projs[pn_Load_res] == NULL) {
						/* create a new Proj again */
837
						pred_info->projs[pn_Load_res] = new_r_Proj(pred, get_Load_mode(pred), pn_Load_res);
838
839
					}
					value = pred_info->projs[pn_Load_res];
840
841
842

					/* add an convert if needed */
					if (get_Load_mode(pred) != load_mode) {
843
						value = new_r_Conv(get_nodes_block(load), value, load_mode);
844
845
					}

846
					exchange(info->projs[pn_Load_res], value);
847
848
				}

849
850
851
				if (info->projs[pn_Load_M])
					exchange(info->projs[pn_Load_M], mem);

852
853
				/* no exception */
				if (info->projs[pn_Load_X_except]) {
854
					ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
855
					exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
856
857
					res |= CF_CHANGED;
				}
858
				if (info->projs[pn_Load_X_regular]) {
859
					exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
860
861
					res |= CF_CHANGED;
				}
862

863
				kill_and_reduce_usage(load);
864
865
866
867
				return res |= DF_CHANGED;
			}
		}

868
		if (is_Store(pred)) {
869
			/* check if we can pass through this store */
870
871
872
			ir_alias_relation rel = get_alias_relation(
				get_Store_ptr(pred),
				get_irn_mode(get_Store_value(pred)),
873
				ptr, load_mode);
874
			/* if the might be an alias, we cannot pass this Store */
Michael Beck's avatar
Michael Beck committed
875
			if (rel != ir_no_alias)
876
877
				break;
			pred = skip_Proj(get_Store_mem(pred));
878
		} else if (is_Load(pred)) {
879
			pred = skip_Proj(get_Load_mem(pred));
880
881
882
883
884
885
886
887
888
		} 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;
			}
889
890
891
892
893
894
895
896
897
898
899
		} else {
			/* follow only Load chains */
			break;
		}

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

900
	if (is_Sync(pred)) {
901
902
903
904
905
906
		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)
907
				return res;
908
909
910
911
		}
	}

	return res;
912
}
Michael Beck's avatar
Michael Beck committed
913

914
915
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
916
917
918
919
920
	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);
921
922
923
924
925

	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 */
926
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
927
928
		} else {
			return NULL;
929
930
931
		}
	}
	return res;
932
}
933

Michael Beck's avatar
Michael Beck committed
934
935
/**
 * optimize a Load
936
937
 *
 * @param load  the Load node
Michael Beck's avatar
Michael Beck committed
938
 */
939
static unsigned optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
940
{
941
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
942
943
944
945
	ir_node     *mem, *ptr, *value;
	ir_entity   *ent;
	long        dummy;
	unsigned    res = 0;
946
947
948
949
950
951
952
953
954

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

957
958
959
	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 */
960
961
		exchange(info->projs[pn_Load_M], mem);

962
963
		if (info->projs[pn_Load_X_regular]) {
			/* should not happen, but if it does, remove it */
964
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
965
966
			res |= CF_CHANGED;
		}
967
		kill_and_reduce_usage(load);
968
969
970
		return res | DF_CHANGED;
	}

Matthias Braun's avatar
Matthias Braun committed
971
972
973
974
975
976
977
978
	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
979

Matthias Braun's avatar
Matthias Braun committed
980
981
982
983
984
985
986
987
988
989
990
991
		/* 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
992

Matthias Braun's avatar
Matthias Braun committed
993
994
995
996
997
998
999
		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) {
				value = can_replace_load_by_const(load, value);
Michael Beck's avatar
Michael Beck committed
1000
			}
1001
		}
Michael Beck's avatar
Michael Beck committed
1002
1003
1004
	}
	if (value != NULL) {
		/* we completely replace the load by this value */
1005
		if (info->projs[pn_Load_X_except]) {
1006
			ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
1007
			exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
1008
			info->projs[pn_Load_X_except] = NULL;
1009
1010
1011
			res |= CF_CHANGED;
		}
		if (info->projs[pn_Load_X_regular]) {
1012
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1013
1014
			info->projs[pn_Load_X_regular] = NULL;
			res |= CF_CHANGED;
1015
		}
Michael Beck's avatar
Michael Beck committed
1016
1017
1018
1019
1020
1021
1022
1023
		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;
		}
1024
		kill_and_reduce_usage(load);
Michael Beck's avatar
Michael Beck committed
1025
		return res;
1026
1027
1028
	}

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

1045
1046
1047
1048
1049
1050
1051
/**
 * 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);
1052
}
1053

1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
/**
 * 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