ldstopt.c 56.3 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
/**
 * @file
 * @brief   Load/Store optimizations.
 * @author  Michael Beck
Michael Beck's avatar
Michael Beck committed
24
 */
Matthias Braun's avatar
Matthias Braun committed
25
#include "config.h"
Michael Beck's avatar
Michael Beck committed
26

27
#include <string.h>
Michael Beck's avatar
Michael Beck committed
28

29
#include "iroptimize.h"
30
31
32
33
34
35
36
#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"
37
#include "irtools.h"
38
39
40
41
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
42
#include "array_t.h"
43
#include "irhooks.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
44
#include "iredges.h"
45
#include "irpass.h"
46
#include "irmemory.h"
47
#include "irnodehashmap.h"
48
#include "irgopt.h"
49
#include "set.h"
Matthias Braun's avatar
Matthias Braun committed
50
#include "be.h"
51
52
53
54
#include "debug.h"

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

Michael Beck's avatar
Michael Beck committed
56
#undef IMAX
57
#define IMAX(a,b)   ((a) > (b) ? (a) : (b))
Michael Beck's avatar
Michael Beck committed
58

59
#define MAX_PROJ    IMAX(IMAX((long)pn_Load_max, (long)pn_Store_max), (long)pn_Call_max)
Michael Beck's avatar
Michael Beck committed
60

61
enum changes_t {
62
63
	DF_CHANGED = 1,       /**< data flow changed */
	CF_CHANGED = 2,       /**< control flow changed */
64
65
};

Michael Beck's avatar
Michael Beck committed
66
67
68
/**
 * walker environment
 */
69
typedef struct walk_env_t {
70
71
	struct obstack obst;          /**< list of all stores */
	unsigned changes;             /**< a bitmask of graph changes */
Michael Beck's avatar
Michael Beck committed
72
73
} walk_env_t;

74
/** A Load/Store info. */
75
typedef struct ldst_info_t {
76
	ir_node  *projs[MAX_PROJ+1];  /**< list of Proj's of this node */
77
78
79
	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
80
81
} ldst_info_t;

82
/**
83
 * flags for control flow.
84
85
 */
enum block_flags_t {
86
87
	BLOCK_HAS_COND = 1,      /**< Block has conditional control flow */
	BLOCK_HAS_EXC  = 2       /**< Block has exceptional control flow */
88
89
90
};

/**
91
 * a Block info.
92
 */
93
typedef struct block_info_t {
94
	unsigned flags;               /**< flags for the block */
95
96
} block_info_t;

97
98
99
100
101
102
103
/** 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
104
105
106
/**
 * get the Load/Store info of a node
 */
107
108
static ldst_info_t *get_ldst_info(ir_node *node, struct obstack *obst)
{
109
	ldst_info_t *info = (ldst_info_t*)get_irn_link(node);
Michael Beck's avatar
Michael Beck committed
110

111
	if (! info) {
112
		info = OALLOCZ(obst, ldst_info_t);
113
114
115
		set_irn_link(node, info);
	}
	return info;
116
}
Michael Beck's avatar
Michael Beck committed
117

118
119
120
/**
 * get the Block info of a node
 */
121
122
static block_info_t *get_block_info(ir_node *node, struct obstack *obst)
{
123
	block_info_t *info = (block_info_t*)get_irn_link(node);
124

125
	if (! info) {
126
		info = OALLOCZ(obst, block_info_t);
127
128
129
		set_irn_link(node, info);
	}
	return info;
130
}
131

Michael Beck's avatar
Michael Beck committed
132
/**
Michael Beck's avatar
Michael Beck committed
133
 * update the projection info for a Load/Store
Michael Beck's avatar
Michael Beck committed
134
 */
135
static unsigned update_projs(ldst_info_t *info, ir_node *proj)
Michael Beck's avatar
Michael Beck committed
136
{
137
	long nr = get_Proj_proj(proj);
Michael Beck's avatar
Michael Beck committed
138

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

141
142
143
144
145
146
147
148
149
	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;
	}
150
}
Michael Beck's avatar
Michael Beck committed
151
152

/**
153
154
155
156
157
 * 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
158
 */
159
static unsigned update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
160
{
161
	assert(info->exc_block == NULL && "more than one exception block found");
Michael Beck's avatar
Michael Beck committed
162

163
164
165
	info->exc_block = block;
	info->exc_idx   = pos;
	return 0;
166
}
Michael Beck's avatar
Michael Beck committed
167
168
169

/**
 * walker, collects all Load/Store/Proj nodes
170
 *
171
 * walks from Start -> End
Michael Beck's avatar
Michael Beck committed
172
 */
Michael Beck's avatar
Michael Beck committed
173
static void collect_nodes(ir_node *node, void *env)
Michael Beck's avatar
Michael Beck committed
174
{
175
176
	walk_env_t  *wenv   = (walk_env_t *)env;
	unsigned     opcode = get_irn_opcode(node);
177
178
179
	ir_node     *pred, *blk, *pred_blk;
	ldst_info_t *ldst_info;

180
181
182
	if (opcode == iro_Proj) {
		pred   = get_Proj_pred(node);
		opcode = get_irn_opcode(pred);
183

184
		if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
185
			ldst_info = get_ldst_info(pred, &wenv->obst);
186
187
188
189

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

			/*
190
191
192
193
194
			 * 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.
			 */
195
196
197
198
199
200
201
			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);
			}
		}
202
	} else if (opcode == iro_Block) {
203
204
205
		int i;

		for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
206
			ir_node      *pred_block, *proj;
207
			block_info_t *bl_info;
208
209
210
			int          is_exc = 0;

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

212
213
			if (is_Proj(proj)) {
				pred   = get_Proj_pred(proj);
Matthias Braun's avatar
Matthias Braun committed
214
				is_exc = is_x_except_Proj(proj);
215
			}
216
217
218
219
220
221

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

			pred_block = get_nodes_block(pred);
222
			bl_info    = get_block_info(pred_block, &wenv->obst);
223

224
			if (is_fragile_op(pred) && is_exc)
225
226
227
228
				bl_info->flags |= BLOCK_HAS_EXC;
			else if (is_irn_forking(pred))
				bl_info->flags |= BLOCK_HAS_COND;

229
230
			opcode = get_irn_opcode(pred);
			if (is_exc && (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call)) {
231
				ldst_info = get_ldst_info(pred, &wenv->obst);
232
233
234
235
236

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

Michael Beck's avatar
Michael Beck committed
239
/**
240
 * Returns an entity if the address ptr points to a constant one.
241
242
243
244
 *
 * @param ptr  the address
 *
 * @return an entity or NULL
Michael Beck's avatar
Michael Beck committed
245
 */
246
static ir_entity *find_constant_entity(ir_node *ptr)
Michael Beck's avatar
Michael Beck committed
247
{
248
	for (;;) {
249
		if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
250
			return get_SymConst_entity(ptr);
251
		} else if (is_Sel(ptr)) {
252
253
254
255
256
257
258
259
260
261
262
263
264
265
			ir_entity *ent = get_Sel_entity(ptr);
			ir_type   *tp  = get_entity_owner(ent);

			/* Do not fiddle with polymorphism. */
			if (is_Class_type(get_entity_owner(ent)) &&
				((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
266
267
268
269
					ir_node   *bound;
					ir_tarval *tlower, *tupper;
					ir_node   *index = get_Sel_index(ptr, i);
					ir_tarval *tv    = computed_value(index);
270
271
272
273
274
275
276
277
278
279
280
281
282

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

283
					if (tarval_cmp(tv, tlower) == ir_relation_less)
284
						return NULL;
285
					if (tarval_cmp(tupper, tv) == ir_relation_less)
286
287
288
289
290
291
						return NULL;

					/* ok, bounds check finished */
				}
			}

Matthias Braun's avatar
Matthias Braun committed
292
			if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT)
293
294
295
296
				return ent;

			/* try next */
			ptr = get_Sel_ptr(ptr);
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
		} 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);

315
			if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
316
317
318
319
320
321
				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;
322
323
324
		} else
			return NULL;
	}
325
}
Michael Beck's avatar
Michael Beck committed
326

Michael Beck's avatar
Michael Beck committed
327
328
329
/**
 * Return the Selection index of a Sel node from dimension n
 */
330
331
static long get_Sel_array_index_long(ir_node *n, int dim)
{
332
333
	ir_node *index = get_Sel_index(n, dim);
	return get_tarval_long(get_Const_tarval(index));
334
}
335

336
337
338
typedef struct path_entry {
	ir_entity         *ent;
	struct path_entry *next;
339
	size_t            index;
340
341
} path_entry;

342
343
static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next)
{
344
	path_entry       entry, *p;
345
	ir_entity        *ent, *field;
346
	ir_initializer_t *initializer;
Matthias Braun's avatar
Matthias Braun committed
347
	ir_tarval        *tv;
348
	ir_type          *tp;
349
	size_t           n;
350

351
	entry.next = next;
352
353
	if (is_SymConst(ptr)) {
		/* found the root */
354
		ent         = get_SymConst_entity(ptr);
355
		initializer = get_entity_initializer(ent);
356
		for (p = next; p != NULL;) {
357
358
			if (initializer->kind != IR_INITIALIZER_COMPOUND)
				return NULL;
359
360
			n  = get_initializer_compound_n_entries(initializer);
			tp = get_entity_type(ent);
361

362
363
364
365
366
367
368
369
370
371
			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;
				}
			}
372
			if (p->index >= n)
373
374
				return NULL;
			initializer = get_initializer_compound_value(initializer, p->index);
375
376
377
378
379
380
381
382
383
384
385
386
387

			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);
388
		}
389

390
391
392
393
394
395
396
397
398
		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)) {
399
400
401
402
		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");
403
			entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
404
		} else {
405
			size_t i, n_members = get_compound_n_members(tp);
406
407
408
409
410
411
412
413
414
415
416
			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);
417
418
419
	}  else if (is_Add(ptr)) {
		ir_mode  *mode;
		unsigned pos;
420

421
422
423
424
425
426
427
428
429
430
		{
			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);
			}
431
432
433
		}
ptr_arith:
		mode = get_tarval_mode(tv);
434

435
436
437
438
439
440
		/* 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);
		}
441

442
443
444
445
446
447
448
449
450
451
452
		/* 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)
453
454
			return NULL;

455
456
457
458
459
460
		/* 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
461
462
463
464
			unsigned   size;
			ir_tarval *sz, *tv_index, *tlower, *tupper;
			long       index;
			ir_node   *bound;
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490

			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;

491
			if (tarval_cmp(tv_index, tlower) == ir_relation_less)
492
				return NULL;
493
			if (tarval_cmp(tupper, tv_index) == ir_relation_less)
494
495
496
497
498
499
500
501
502
				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 */
503
			return NULL;
504
505
506
507
508
509
		}
		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);
510

511
512
513
514
		ptr = l;
		tv  = get_Const_tarval(r);
		tv  = tarval_neg(tv);
		goto ptr_arith;
515
	}
516
	return NULL;
517
518
}

519
520
static ir_node *find_compound_ent_value(ir_node *ptr)
{
521
522
523
	return rec_find_compound_ent_value(ptr, NULL);
}

524
525
526
527
/* forward */
static void reduce_adr_usage(ir_node *ptr);

/**
Christoph Mallon's avatar
Christoph Mallon committed
528
 * Update a Load that may have lost its users.
529
 */
530
531
static void handle_load_update(ir_node *load)
{
532
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
533

534
535
536
	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return;
537

538
539
540
	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);
541

Christoph Mallon's avatar
Christoph Mallon committed
542
		/* a Load whose value is neither used nor exception checked, remove it */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
543
		exchange(info->projs[pn_Load_M], mem);
544
		if (info->projs[pn_Load_X_regular])
545
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
546
		kill_node(load);
547
548
		reduce_adr_usage(ptr);
	}
549
}
550
551

/**
Christoph Mallon's avatar
Christoph Mallon committed
552
 * A use of an address node has vanished. Check if this was a Proj
553
554
 * node and update the counters.
 */
555
556
static void reduce_adr_usage(ir_node *ptr)
{
557
558
559
560
561
	ir_node *pred;
	if (!is_Proj(ptr))
		return;
	if (get_irn_n_edges(ptr) > 0)
		return;
562

563
564
565
	/* this Proj is dead now */
	pred = get_Proj_pred(ptr);
	if (is_Load(pred)) {
566
		ldst_info_t *info = (ldst_info_t*)get_irn_link(pred);
567
		info->projs[get_Proj_proj(ptr)] = NULL;
568

569
570
		/* this node lost its result proj, handle that */
		handle_load_update(pred);
571
	}
572
}
573

574
575
576
577
/**
 * Check, if an already existing value of mode old_mode can be converted
 * into the needed one new_mode without loss.
 */
578
579
static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode)
{
580
581
	unsigned old_size;
	unsigned new_size;
582
	if (old_mode == new_mode)
583
584
585
586
		return true;

	old_size = get_mode_size_bits(old_mode);
	new_size = get_mode_size_bits(new_mode);
587
588

	/* if both modes are two-complement ones, we can always convert the
589
590
591
	   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 &&
592
		  get_mode_arithmetic(old_mode) == irma_twos_complement &&
593
594
595
596
597
598
599
		  get_mode_arithmetic(new_mode) == irma_twos_complement &&
		  (!be_get_backend_param()->byte_order_big_endian
	        || old_size == new_size)) {
		return true;
	}
	return false;
}
600

Michael Beck's avatar
Michael Beck committed
601
/**
602
 * Check whether a Call is at least pure, i.e. does only read memory.
603
 */
604
605
static unsigned is_Call_pure(ir_node *call)
{
606
607
608
609
610
611
612
613
	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);

614
615
		if (is_SymConst_addr_ent(ptr)) {
			ir_entity *ent = get_SymConst_entity(ptr);
616
617
618
619
620

			prop = get_entity_additional_properties(ent);
		}
	}
	return (prop & (mtp_property_const|mtp_property_pure)) != 0;
621
}
622

Michael Beck's avatar
Michael Beck committed
623
static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset)
624
{
Michael Beck's avatar
Michael Beck committed
625
626
	ir_mode *mode  = get_irn_mode(ptr);
	long    offset = 0;
627
628

	/* TODO: long might not be enough, we should probably use some tarval thingy... */
Michael Beck's avatar
Michael Beck committed
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
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
	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
676
677
678
			break;
	}

Michael Beck's avatar
Michael Beck committed
679
680
	*pOffset = offset;
	return ptr;
681
682
}

Michael Beck's avatar
Michael Beck committed
683
static int try_load_after_store(ir_node *load,
684
685
686
687
		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
688
689
	long     store_offset;
	ir_node *store_base_ptr = get_base_and_offset(store_ptr, &store_offset);
690
691
692
693
694
695
696
697
698
699
700
701
	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
702
703
	load_mode      = get_Load_mode(load);
	load_mode_len  = get_mode_size_bytes(load_mode);
704
705
	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
706
	delta          = load_offset - store_offset;
707
	store_value    = get_Store_value(store);
708

709
710
	if (delta < 0 || delta+load_mode_len > store_mode_len)
		return 0;
711

712
713
714
	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
715

716
		/* produce a shift to adjust offset delta */
717
718
719
720
721
722
		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);
723
			store_value = new_r_Shr(get_nodes_block(load),
724
725
726
									store_value, cnst, store_mode);
		}

727
728
729
730
		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;
731
732
	}

Michael Beck's avatar
Michael Beck committed
733
734
	DBG_OPT_RAW(load, store_value);

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

760
761
762
763
/**
 * 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
764
765
766
767
768
769
 * 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
 */
770
771
static unsigned follow_Mem_chain(ir_node *load, ir_node *curr)
{
Michael Beck's avatar
Michael Beck committed
772
	unsigned    res = 0;
773
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
774
775
776
777
	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);
778
779

	for (pred = curr; load != pred; ) {
780
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
781
782

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

825
826
				DBG_OPT_RAR(load, pred);

827
828
829
830
				/* the result is used */
				if (info->projs[pn_Load_res]) {
					if (pred_info->projs[pn_Load_res] == NULL) {
						/* create a new Proj again */
831
						pred_info->projs[pn_Load_res] = new_r_Proj(pred, get_Load_mode(pred), pn_Load_res);
832
833
					}
					value = pred_info->projs[pn_Load_res];
834
835
836

					/* add an convert if needed */
					if (get_Load_mode(pred) != load_mode) {
837
						value = new_r_Conv(get_nodes_block(load), value, load_mode);
838
839
					}

840
					exchange(info->projs[pn_Load_res], value);
841
842
				}

843
844
845
				if (info->projs[pn_Load_M])
					exchange(info->projs[pn_Load_M], mem);

846
847
				/* no exception */
				if (info->projs[pn_Load_X_except]) {
848
					ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
849
					exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
850
851
					res |= CF_CHANGED;
				}
852
				if (info->projs[pn_Load_X_regular]) {
853
					exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
854
855
					res |= CF_CHANGED;
				}
856

857
				kill_node(load);
858
859
860
861
862
				reduce_adr_usage(ptr);
				return res |= DF_CHANGED;
			}
		}

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

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

895
	if (is_Sync(pred)) {
896
897
898
899
900
901
		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)
902
				return res;
903
904
905
906
		}
	}

	return res;
907
}
Michael Beck's avatar
Michael Beck committed
908

909
910
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
911
912
913
914
915
	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);
916
917
918
919
920

	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 */
921
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
922
923
		} else {
			return NULL;
924
925
926
		}
	}
	return res;
927
}
928

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

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

952
953
954
	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 */
955
956
		exchange(info->projs[pn_Load_M], mem);

957
958
		if (info->projs[pn_Load_X_regular]) {
			/* should not happen, but if it does, remove it */
959
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
960
961
			res |= CF_CHANGED;
		}
962
		kill_node(load);
963
964
965
966
		reduce_adr_usage(ptr);
		return res | DF_CHANGED;
	}

Matthias Braun's avatar
Matthias Braun committed
967
968
969
970
971
972
973
974
	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
975

Matthias Braun's avatar
Matthias Braun committed
976
977
978
979
980
981
982
983
984
985
986
987
		/* 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
988

Matthias Braun's avatar
Matthias Braun committed
989
990
991
992
993
994
995
996
		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);
997
				if (value != NULL && is_Sel(ptr)) {
Matthias Braun's avatar
Matthias Braun committed
998
999
1000
					/* 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));
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
					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
1011
				}
Michael Beck's avatar
Michael Beck committed
1012
			}
1013
		}
Michael Beck's avatar
Michael Beck committed
1014
1015
1016
	}
	if (value != NULL) {
		/* we completely replace the load by this value */
1017
		if (info->projs[pn_Load_X_except]) {
1018
			ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
1019
			exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
1020
			info->projs[pn_Load_X_except] = NULL;
1021
1022
1023
			res |= CF_CHANGED;
		}
		if (info->projs[pn_Load_X_regular]) {
1024
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1025
1026
			info->projs[pn_Load_X_regular] = NULL;
			res |= CF_CHANGED;
1027
		}
Michael Beck's avatar
Michael Beck committed
1028
1029
1030
1031
1032
1033
1034
1035
		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;
		}
1036
		kill_node(load);
1037
		reduce_adr_usage(ptr);
Michael Beck's avatar
Michael Beck committed
1038
		return res;
1039
1040
1041
	}

	/* Check, if the address of this load is used more than once.
Michael Beck's avatar
Michael Beck committed
1042
	 * If not, more load cannot be removed in any case. */
1043
	if (get_irn_n_edges(ptr) <= 1 && get_irn_n_edges(get_base_and_offset(ptr, &dummy)) <= 1)
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
		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;
1056
}
Michael Beck's avatar
Michael Beck committed
1057

1058
1059
1060
1061
1062