ldstopt.c 61.1 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
24
/**
 * @file
 * @brief   Load/Store optimizations.
 * @author  Michael Beck
 * @version $Id$
Michael Beck's avatar
Michael Beck committed
25
 */
Matthias Braun's avatar
Matthias Braun committed
26
#include "config.h"
Michael Beck's avatar
Michael Beck committed
27

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

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

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

Michael Beck's avatar
Michael Beck committed
59
#undef IMAX
60
#define IMAX(a,b)   ((a) > (b) ? (a) : (b))
Michael Beck's avatar
Michael Beck committed
61

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

64
enum changes_t {
65
66
	DF_CHANGED = 1,       /**< data flow changed */
	CF_CHANGED = 2,       /**< control flow changed */
67
68
};

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

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

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

/**
94
 * a Block info.
95
 */
96
typedef struct block_info_t {
97
	unsigned flags;               /**< flags for the block */
98
99
} block_info_t;

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

114
	if (! info) {
115
		info = OALLOCZ(obst, ldst_info_t);
116
117
118
119
		set_irn_link(node, info);
	}
	return info;
}  /* get_ldst_info */
Michael Beck's avatar
Michael Beck committed
120

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

128
	if (! info) {
129
		info = OALLOCZ(obst, block_info_t);
130
131
132
133
		set_irn_link(node, info);
	}
	return info;
}  /* get_block_info */
134

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

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

144
145
146
147
148
149
150
151
152
153
	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;
	}
}  /* update_projs */
Michael Beck's avatar
Michael Beck committed
154
155

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

166
167
168
169
	info->exc_block = block;
	info->exc_idx   = pos;
	return 0;
}  /* update_exc */
Michael Beck's avatar
Michael Beck committed
170

171
/** Return the number of uses of an address node */
Michael Beck's avatar
BugFix:    
Michael Beck committed
172
#define get_irn_n_uses(adr)     get_irn_n_edges(adr)
173

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

186
187
188
	if (opcode == iro_Proj) {
		pred   = get_Proj_pred(node);
		opcode = get_irn_opcode(pred);
189

190
		if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
191
			ldst_info = get_ldst_info(pred, &wenv->obst);
192
193
194
195

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

			/*
196
197
198
199
200
			 * 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.
			 */
201
202
203
204
205
206
207
			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);
			}
		}
208
	} else if (opcode == iro_Block) {
209
210
211
		int i;

		for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
212
			ir_node      *pred_block, *proj;
213
			block_info_t *bl_info;
214
215
216
			int          is_exc = 0;

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

218
219
			if (is_Proj(proj)) {
				pred   = get_Proj_pred(proj);
Matthias Braun's avatar
Matthias Braun committed
220
				is_exc = is_x_except_Proj(proj);
221
			}
222
223
224
225
226
227

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

			pred_block = get_nodes_block(pred);
228
			bl_info    = get_block_info(pred_block, &wenv->obst);
229

230
			if (is_fragile_op(pred) && is_exc)
231
232
233
234
				bl_info->flags |= BLOCK_HAS_EXC;
			else if (is_irn_forking(pred))
				bl_info->flags |= BLOCK_HAS_COND;

235
236
			opcode = get_irn_opcode(pred);
			if (is_exc && (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call)) {
237
				ldst_info = get_ldst_info(pred, &wenv->obst);
238
239
240
241
242
243

				wenv->changes |= update_exc(ldst_info, node, i);
			}
		}
	}
}  /* collect_nodes */
Michael Beck's avatar
Michael Beck committed
244

Michael Beck's avatar
Michael Beck committed
245
/**
246
 * Returns an entity if the address ptr points to a constant one.
247
248
249
250
 *
 * @param ptr  the address
 *
 * @return an entity or NULL
Michael Beck's avatar
Michael Beck committed
251
 */
252
static ir_entity *find_constant_entity(ir_node *ptr)
Michael Beck's avatar
Michael Beck committed
253
{
254
	for (;;) {
255
		if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) {
256
			return get_SymConst_entity(ptr);
257
		} else if (is_Sel(ptr)) {
258
259
260
261
262
263
264
265
266
267
268
269
270
271
			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
272
273
274
275
					ir_node   *bound;
					ir_tarval *tlower, *tupper;
					ir_node   *index = get_Sel_index(ptr, i);
					ir_tarval *tv    = computed_value(index);
276
277
278
279
280
281
282
283
284
285
286
287
288

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

289
					if (tarval_cmp(tv, tlower) == ir_relation_less)
290
						return NULL;
291
					if (tarval_cmp(tupper, tv) == ir_relation_less)
292
293
294
295
296
297
						return NULL;

					/* ok, bounds check finished */
				}
			}

Matthias Braun's avatar
Matthias Braun committed
298
			if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT)
299
300
301
302
				return ent;

			/* try next */
			ptr = get_Sel_ptr(ptr);
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
		} 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);

321
			if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
322
323
324
325
326
327
				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;
328
329
330
331
		} else
			return NULL;
	}
}  /* find_constant_entity */
Michael Beck's avatar
Michael Beck committed
332

Michael Beck's avatar
Michael Beck committed
333
334
335
/**
 * Return the Selection index of a Sel node from dimension n
 */
336
337
static long get_Sel_array_index_long(ir_node *n, int dim)
{
338
	ir_node *index = get_Sel_index(n, dim);
Michael Beck's avatar
Michael Beck committed
339
	assert(is_Const(index));
340
341
	return get_tarval_long(get_Const_tarval(index));
}  /* get_Sel_array_index_long */
342

Michael Beck's avatar
Michael Beck committed
343
344
345
346
347
348
349
350
/**
 * Returns the accessed component graph path for an
 * node computing an address.
 *
 * @param ptr    the node computing the address
 * @param depth  current depth in steps upward from the root
 *               of the address
 */
351
static compound_graph_path *rec_get_accessed_path(ir_node *ptr, size_t depth)
352
{
353
	compound_graph_path *res = NULL;
354
	ir_entity           *root, *field, *ent;
355
	size_t              path_len, pos, idx;
Matthias Braun's avatar
Matthias Braun committed
356
	ir_tarval           *tv;
357
	ir_type             *tp;
358

359
	if (is_SymConst(ptr)) {
360
361
		/* a SymConst. If the depth is 0, this is an access to a global
		 * entity and we don't need a component path, else we know
Christoph Mallon's avatar
Christoph Mallon committed
362
		 * at least its length.
363
364
365
366
		 */
		assert(get_SymConst_kind(ptr) == symconst_addr_ent);
		root = get_SymConst_entity(ptr);
		res = (depth == 0) ? NULL : new_compound_graph_path(get_entity_type(root), depth);
367
	} else if (is_Sel(ptr)) {
368
369
		/* it's a Sel, go up until we find the root */
		res = rec_get_accessed_path(get_Sel_ptr(ptr), depth+1);
370
371
		if (res == NULL)
			return NULL;
372
373
374
375
376
377
378
379
380
381
382

		/* fill up the step in the path at the current position */
		field    = get_Sel_entity(ptr);
		path_len = get_compound_graph_path_length(res);
		pos      = path_len - depth - 1;
		set_compound_graph_path_node(res, pos, field);

		if (is_Array_type(get_entity_owner(field))) {
			assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented");
			set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
		}
383
	} else if (is_Add(ptr)) {
384
		ir_mode   *mode;
Matthias Braun's avatar
Matthias Braun committed
385
		ir_tarval *tmp;
386

387
388
389
390
391
392
393
394
395
396
		{
			ir_node   *l    = get_Add_left(ptr);
			ir_node   *r    = get_Add_right(ptr);
			if (is_Const(r) && get_irn_mode(l) == get_irn_mode(ptr)) {
				ptr = l;
				tv  = get_Const_tarval(r);
			} else {
				ptr = r;
				tv  = get_Const_tarval(l);
			}
397
398
399
		}
ptr_arith:
		mode = get_tarval_mode(tv);
Michael Beck's avatar
Michael Beck committed
400
		tmp  = tv;
401
402
403
404
405
406
407
408
409

		/* 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);
		}
		idx = 0;
		for (ent = field;;) {
Matthias Braun's avatar
Matthias Braun committed
410
411
412
			unsigned   size;
			ir_tarval *sz, *tv_index, *tlower, *tupper;
			ir_node   *bound;
413

414
415
416
417
			tp = get_entity_type(ent);
			if (! is_Array_type(tp))
				break;
			ent = get_array_element_entity(tp);
418
419
420
			size = get_type_size_bytes(get_entity_type(ent));
			sz   = new_tarval_from_long(size, mode);

Michael Beck's avatar
Michael Beck committed
421
422
			tv_index = tarval_div(tmp, sz);
			tmp      = tarval_mod(tmp, sz);
423

Michael Beck's avatar
Michael Beck committed
424
			if (tv_index == tarval_bad || tmp == tarval_bad)
425
426
427
428
429
430
431
432
433
434
435
				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;

436
			if (tarval_cmp(tv_index, tlower) == ir_relation_less)
437
				return NULL;
438
			if (tarval_cmp(tupper, tv_index) == ir_relation_less)
439
440
441
				return NULL;

			/* ok, bounds check finished */
442
443
			++idx;
		}
Michael Beck's avatar
Michael Beck committed
444
		if (! tarval_is_null(tmp)) {
445
446
447
448
			/* access to some struct/union member */
			return NULL;
		}

449
450
451
452
453
454
455
456
457
458
459
460
		/* should be at least ONE array */
		if (idx == 0)
			return NULL;

		res = rec_get_accessed_path(ptr, depth + idx);
		if (res == NULL)
			return NULL;

		path_len = get_compound_graph_path_length(res);
		pos      = path_len - depth - idx;

		for (ent = field;;) {
Matthias Braun's avatar
Matthias Braun committed
461
462
463
			unsigned   size;
			ir_tarval *sz, *tv_index;
			long       index;
464
465
466
467
468
469
470
471
472
473
474
475
476

			tp = get_entity_type(ent);
			if (! is_Array_type(tp))
				break;
			ent = get_array_element_entity(tp);
			set_compound_graph_path_node(res, pos, ent);

			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);

Michael Beck's avatar
Michael Beck committed
477
478
			/* worked above, should work again */
			assert(tv_index != tarval_bad && tv != tarval_bad);
479

480
			/* bounds already checked above */
481
482
483
484
485
486
487
488
489
490
491
492
			index = get_tarval_long(tv_index);
			set_compound_graph_path_array_index(res, pos, index);
			++pos;
		}
	} else if (is_Sub(ptr)) {
		ir_node *l = get_Sub_left(ptr);
		ir_node *r = get_Sub_right(ptr);

		ptr = l;
		tv  = get_Const_tarval(r);
		tv  = tarval_neg(tv);
		goto ptr_arith;
493
494
495
	}
	return res;
}  /* rec_get_accessed_path */
496

497
498
499
/**
 * Returns an access path or NULL.  The access path is only
 * valid, if the graph is in phase_high and _no_ address computation is used.
Michael Beck's avatar
Michael Beck committed
500
 */
501
502
static compound_graph_path *get_accessed_path(ir_node *ptr)
{
Michael Beck's avatar
Michael Beck committed
503
504
	compound_graph_path *gr = rec_get_accessed_path(ptr, 0);
	return gr;
505
}  /* get_accessed_path */
506

507
508
509
typedef struct path_entry {
	ir_entity         *ent;
	struct path_entry *next;
510
	size_t            index;
511
512
} path_entry;

513
514
static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next)
{
515
	path_entry       entry, *p;
516
	ir_entity        *ent, *field;
517
	ir_initializer_t *initializer;
Matthias Braun's avatar
Matthias Braun committed
518
	ir_tarval        *tv;
519
	ir_type          *tp;
520
	size_t           n;
521

522
	entry.next = next;
523
524
	if (is_SymConst(ptr)) {
		/* found the root */
525
		ent         = get_SymConst_entity(ptr);
526
		initializer = get_entity_initializer(ent);
527
		for (p = next; p != NULL;) {
528
529
			if (initializer->kind != IR_INITIALIZER_COMPOUND)
				return NULL;
530
531
			n  = get_initializer_compound_n_entries(initializer);
			tp = get_entity_type(ent);
532

533
534
535
536
537
538
539
540
541
542
			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;
				}
			}
543
			if (p->index >= n)
544
545
				return NULL;
			initializer = get_initializer_compound_value(initializer, p->index);
546
547
548
549
550
551
552
553
554
555
556
557
558

			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);
559
		}
560

561
562
563
564
565
566
567
568
569
		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)) {
570
571
572
573
		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");
574
			entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0);
575
		} else {
576
			size_t i, n_members = get_compound_n_members(tp);
577
578
579
580
581
582
583
584
585
586
587
			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);
588
589
590
	}  else if (is_Add(ptr)) {
		ir_mode  *mode;
		unsigned pos;
591

592
593
594
595
596
597
598
599
600
601
		{
			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);
			}
602
603
604
		}
ptr_arith:
		mode = get_tarval_mode(tv);
605

606
607
608
609
610
611
		/* 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);
		}
612

613
614
615
616
617
618
619
620
621
622
623
		/* 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)
624
625
			return NULL;

626
627
628
629
630
631
		/* 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
632
633
634
635
			unsigned   size;
			ir_tarval *sz, *tv_index, *tlower, *tupper;
			long       index;
			ir_node   *bound;
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

			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;

662
			if (tarval_cmp(tv_index, tlower) == ir_relation_less)
663
				return NULL;
664
			if (tarval_cmp(tupper, tv_index) == ir_relation_less)
665
666
667
668
669
670
671
672
673
				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 */
674
			return NULL;
675
676
677
678
679
680
		}
		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);
681

682
683
684
685
		ptr = l;
		tv  = get_Const_tarval(r);
		tv  = tarval_neg(tv);
		goto ptr_arith;
686
	}
687
	return NULL;
688
689
}

690
691
static ir_node *find_compound_ent_value(ir_node *ptr)
{
692
693
694
	return rec_find_compound_ent_value(ptr, NULL);
}

695
696
697
698
/* forward */
static void reduce_adr_usage(ir_node *ptr);

/**
Christoph Mallon's avatar
Christoph Mallon committed
699
 * Update a Load that may have lost its users.
700
 */
701
702
static void handle_load_update(ir_node *load)
{
703
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
704

705
706
707
	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return;
708

709
710
711
	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);
712

Christoph Mallon's avatar
Christoph Mallon committed
713
		/* a Load whose value is neither used nor exception checked, remove it */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
714
		exchange(info->projs[pn_Load_M], mem);
715
		if (info->projs[pn_Load_X_regular])
716
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
717
		kill_node(load);
718
719
720
		reduce_adr_usage(ptr);
	}
}  /* handle_load_update */
721
722

/**
Christoph Mallon's avatar
Christoph Mallon committed
723
 * A use of an address node has vanished. Check if this was a Proj
724
725
 * node and update the counters.
 */
726
727
static void reduce_adr_usage(ir_node *ptr)
{
728
729
730
731
732
	ir_node *pred;
	if (!is_Proj(ptr))
		return;
	if (get_irn_n_edges(ptr) > 0)
		return;
733

734
735
736
	/* this Proj is dead now */
	pred = get_Proj_pred(ptr);
	if (is_Load(pred)) {
737
		ldst_info_t *info = (ldst_info_t*)get_irn_link(pred);
738
		info->projs[get_Proj_proj(ptr)] = NULL;
739

740
741
		/* this node lost its result proj, handle that */
		handle_load_update(pred);
742
743
	}
}  /* reduce_adr_usage */
744

745
746
747
748
/**
 * Check, if an already existing value of mode old_mode can be converted
 * into the needed one new_mode without loss.
 */
749
750
static int can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode)
{
751
752
	unsigned old_size;
	unsigned new_size;
753
	if (old_mode == new_mode)
754
755
756
757
		return true;

	old_size = get_mode_size_bits(old_mode);
	new_size = get_mode_size_bits(new_mode);
758
759

	/* if both modes are two-complement ones, we can always convert the
760
761
762
	   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 &&
763
		  get_mode_arithmetic(old_mode) == irma_twos_complement &&
764
765
766
767
768
769
770
		  get_mode_arithmetic(new_mode) == irma_twos_complement &&
		  (!be_get_backend_param()->byte_order_big_endian
	        || old_size == new_size)) {
		return true;
	}
	return false;
}
771

Michael Beck's avatar
Michael Beck committed
772
/**
773
 * Check whether a Call is at least pure, i.e. does only read memory.
774
 */
775
776
static unsigned is_Call_pure(ir_node *call)
{
777
778
779
780
781
782
783
784
	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);

785
786
		if (is_Global(ptr)) {
			ir_entity *ent = get_Global_entity(ptr);
787
788
789
790
791
792
793

			prop = get_entity_additional_properties(ent);
		}
	}
	return (prop & (mtp_property_const|mtp_property_pure)) != 0;
}  /* is_Call_pure */

Michael Beck's avatar
Michael Beck committed
794
static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset)
795
{
Michael Beck's avatar
Michael Beck committed
796
797
	ir_mode *mode  = get_irn_mode(ptr);
	long    offset = 0;
798
799

	/* TODO: long might not be enough, we should probably use some tarval thingy... */
Michael Beck's avatar
Michael Beck committed
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
	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
847
848
849
			break;
	}

Michael Beck's avatar
Michael Beck committed
850
851
	*pOffset = offset;
	return ptr;
852
853
}

Michael Beck's avatar
Michael Beck committed
854
static int try_load_after_store(ir_node *load,
855
856
857
858
		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
859
860
	long     store_offset;
	ir_node *store_base_ptr = get_base_and_offset(store_ptr, &store_offset);
861
862
863
864
865
866
867
868
869
870
871
872
	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
873
874
	load_mode      = get_Load_mode(load);
	load_mode_len  = get_mode_size_bytes(load_mode);
875
876
	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
877
	delta          = load_offset - store_offset;
878
	store_value    = get_Store_value(store);
879

880
	if (delta != 0 || store_mode != load_mode) {
881
882
883
884
		/* TODO: implement for big-endian */
		if (delta < 0 || delta + load_mode_len > store_mode_len
				|| (be_get_backend_param()->byte_order_big_endian
				    && load_mode_len != store_mode_len))
885
			return 0;
886

887
888
889
		if (get_mode_arithmetic(store_mode) != irma_twos_complement ||
			get_mode_arithmetic(load_mode)  != irma_twos_complement)
			return 0;
890

Michael Beck's avatar
Michael Beck committed
891

892
893
894
		/* produce a shift to adjust offset delta */
		if (delta > 0) {
			ir_node *cnst;
895
			ir_graph *irg = get_irn_irg(load);
896

897
			cnst        = new_r_Const_long(irg, mode_Iu, delta * 8);
898
			store_value = new_r_Shr(get_nodes_block(load),
899
900
901
902
903
									store_value, cnst, store_mode);
		}

		/* add an convert if needed */
		if (store_mode != load_mode) {
904
			store_value = new_r_Conv(get_nodes_block(load), store_value, load_mode);
905
		}
906
907
	}

Michael Beck's avatar
Michael Beck committed
908
909
	DBG_OPT_RAW(load, store_value);

910
	info = (ldst_info_t*)get_irn_link(load);
911
912
913
914
915
916
	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]) {
917
		ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
918
		exchange( info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
919
920
921
		res |= CF_CHANGED;
	}
	if (info->projs[pn_Load_X_regular]) {
922
		exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
923
924
925
926
927
928
929
930
931
932
933
934
		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;
}

935
936
937
938
/**
 * 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
939
940
941
942
943
944
 * 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
 */
945
946
static unsigned follow_Mem_chain(ir_node *load, ir_node *curr)
{
Michael Beck's avatar
Michael Beck committed
947
	unsigned    res = 0;
948
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
949
950
951
952
	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);
953
954

	for (pred = curr; load != pred; ) {
955
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
956
957

		/*
958
959
		 * 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
960
		 * exception handler OR they are in the same Block. In the latter
961
962
963
964
965
		 * 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
966
		 * the load Block :-(
967
968
		 * We could make it a little bit better if we would know that the
		 * exception handler of the Store jumps directly to the end...
969
		 */
970
971
		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
972
				|| get_nodes_block(load) == get_nodes_block(pred)))
973
		{
Michael Beck's avatar
Michael Beck committed
974
975
976
977
978
			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)
979
				return res | changes;
980
		} else if (is_Load(pred) && get_Load_ptr(pred) == ptr &&
981
		           can_use_stored_value(get_Load_mode(pred), load_mode)) {
982
983
			/*
			 * a Load after a Load -- a read after read.
Matthias Braun's avatar
Matthias Braun committed
984
985
986
987
			 * 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.
988
			 *
Matthias Braun's avatar
Matthias Braun committed
989
990
991
			 * Here, there is no need to check if the previous Load has an
			 * exception hander because they would have exact the same
			 * exception...
992
993
994
			 *
			 * TODO: implement load-after-load with different mode for big
			 *       endian
995
			 */
Matthias Braun's avatar
Matthias Braun committed
996
997
			if (info->projs[pn_Load_X_except] == NULL
					|| get_nodes_block(load) == get_nodes_block(pred)) {
998
999
				ir_node *value;

1000
1001
				DBG_OPT_RAR(load, pred);

1002
1003
1004
1005
				/* the result is used */
				if (info->projs[pn_Load_res]) {
					if (pred_info->projs[pn_Load_res] == NULL) {
						/* create a new Proj again */
1006
						pred_info->projs[pn_Load_res] = new_r_Proj(pred, get_Load_mode(pred), pn_Load_res);
1007
1008
					}
					value = pred_info->projs[pn_Load_res];
1009
1010
1011

					/* add an convert if needed */
					if (get_Load_mode(pred) != load_mode) {
1012
						value = new_r_Conv(get_nodes_block(load), value, load_mode);
1013
1014
					}

1015
					exchange(info->projs[pn_Load_res], value);
1016
1017
				}

1018
1019
1020
				if (info->projs[pn_Load_M])
					exchange(info->projs[pn_Load_M], mem);

1021
1022
				/* no exception */
				if (info->projs[pn_Load_X_except]) {
1023
					ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
1024
					exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
1025
1026
					res |= CF_CHANGED;
				}
1027
				if (info->projs[pn_Load_X_regular]) {
1028
					exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
1029
1030
					res |= CF_CHANGED;
				}
1031

1032
				kill_node(load);
1033
1034
1035
1036
1037
				reduce_adr_usage(ptr);
				return res |= DF_CHANGED;
			}
		}

1038
		if (is_Store(pred)) {
1039
			/* check if we can pass through this store */
1040
1041
1042
			ir_alias_relation rel = get_alias_relation(
				get_Store_ptr(pred),
				get_irn_mode(get_Store_value(pred)),
1043
				ptr, load_mode);
1044
			/* if the might be an alias, we cannot pass this Store */
Michael Beck's avatar
Michael Beck committed
1045
			if (rel != ir_no_alias)
1046
1047
				break;
			pred = skip_Proj(get_Store_mem(pred));
1048
		} else if (is_Load(pred)) {
1049
			pred = skip_Proj(get_Load_mem(pred));
1050
1051
1052
1053
1054
1055
1056
1057
1058
		} 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;
			}
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
		} else {
			/* follow only Load chains */
			break;
		}

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