ldstopt.c 56.9 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
116
		set_irn_link(node, info);
	}
	return info;
}  /* get_ldst_info */
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
130
		set_irn_link(node, info);
	}
	return info;
}  /* get_block_info */
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
150
	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
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
166
	info->exc_block = block;
	info->exc_idx   = pos;
	return 0;
}  /* update_exc */
Michael Beck's avatar
Michael Beck committed
167

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

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

183
184
185
	if (opcode == iro_Proj) {
		pred   = get_Proj_pred(node);
		opcode = get_irn_opcode(pred);
186

187
		if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
188
			ldst_info = get_ldst_info(pred, &wenv->obst);
189
190
191
192

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

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

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

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

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

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

			pred_block = get_nodes_block(pred);
225
			bl_info    = get_block_info(pred_block, &wenv->obst);
226

227
			if (is_fragile_op(pred) && is_exc)
228
229
230
231
				bl_info->flags |= BLOCK_HAS_EXC;
			else if (is_irn_forking(pred))
				bl_info->flags |= BLOCK_HAS_COND;

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

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

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

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

286
					if (tarval_cmp(tv, tlower) == ir_relation_less)
287
						return NULL;
288
					if (tarval_cmp(tupper, tv) == ir_relation_less)
289
290
291
292
293
294
						return NULL;

					/* ok, bounds check finished */
				}
			}

Matthias Braun's avatar
Matthias Braun committed
295
			if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT)
296
297
298
299
				return ent;

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

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

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

340
341
342
typedef struct path_entry {
	ir_entity         *ent;
	struct path_entry *next;
343
	size_t            index;
344
345
} path_entry;

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

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

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

			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);
392
		}
393

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

425
426
427
428
429
430
431
432
433
434
		{
			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);
			}
435
436
437
		}
ptr_arith:
		mode = get_tarval_mode(tv);
438

439
440
441
442
443
444
		/* 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);
		}
445

446
447
448
449
450
451
452
453
454
455
456
		/* 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)
457
458
			return NULL;

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

			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;

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

515
516
517
518
		ptr = l;
		tv  = get_Const_tarval(r);
		tv  = tarval_neg(tv);
		goto ptr_arith;
519
	}
520
	return NULL;
521
522
}

523
524
static ir_node *find_compound_ent_value(ir_node *ptr)
{
525
526
527
	return rec_find_compound_ent_value(ptr, NULL);
}

528
529
530
531
/* forward */
static void reduce_adr_usage(ir_node *ptr);

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

538
539
540
	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return;
541

542
543
544
	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);
545

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

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

567
568
569
	/* this Proj is dead now */
	pred = get_Proj_pred(ptr);
	if (is_Load(pred)) {
570
		ldst_info_t *info = (ldst_info_t*)get_irn_link(pred);
571
		info->projs[get_Proj_proj(ptr)] = NULL;
572

573
574
		/* this node lost its result proj, handle that */
		handle_load_update(pred);
575
576
	}
}  /* reduce_adr_usage */
577

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

	old_size = get_mode_size_bits(old_mode);
	new_size = get_mode_size_bits(new_mode);
591
592

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

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

618
619
		if (is_SymConst_addr_ent(ptr)) {
			ir_entity *ent = get_SymConst_entity(ptr);
620
621
622
623
624
625
626

			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
627
static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset)
628
{
Michael Beck's avatar
Michael Beck committed
629
630
	ir_mode *mode  = get_irn_mode(ptr);
	long    offset = 0;
631
632

	/* TODO: long might not be enough, we should probably use some tarval thingy... */
Michael Beck's avatar
Michael Beck committed
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
676
677
678
679
	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
680
681
682
			break;
	}

Michael Beck's avatar
Michael Beck committed
683
684
	*pOffset = offset;
	return ptr;
685
686
}

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

713
	if (delta != 0 || store_mode != load_mode) {
714
715
716
717
		/* 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))
718
			return 0;
719

720
721
722
		if (get_mode_arithmetic(store_mode) != irma_twos_complement ||
			get_mode_arithmetic(load_mode)  != irma_twos_complement)
			return 0;
723

Michael Beck's avatar
Michael Beck committed
724

725
726
727
		/* produce a shift to adjust offset delta */
		if (delta > 0) {
			ir_node *cnst;
728
			ir_graph *irg = get_irn_irg(load);
729

730
			cnst        = new_r_Const_long(irg, mode_Iu, delta * 8);
731
			store_value = new_r_Shr(get_nodes_block(load),
732
733
734
735
736
									store_value, cnst, store_mode);
		}

		/* add an convert if needed */
		if (store_mode != load_mode) {
737
			store_value = new_r_Conv(get_nodes_block(load), store_value, load_mode);
738
		}
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
762
763
764
765
766
767
		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;
}

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

	for (pred = curr; load != pred; ) {
788
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
789
790

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

833
834
				DBG_OPT_RAR(load, pred);

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

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

848
					exchange(info->projs[pn_Load_res], value);
849
850
				}

851
852
853
				if (info->projs[pn_Load_M])
					exchange(info->projs[pn_Load_M], mem);

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

865
				kill_node(load);
866
867
868
869
870
				reduce_adr_usage(ptr);
				return res |= DF_CHANGED;
			}
		}

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

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

903
	if (is_Sync(pred)) {
904
905
906
907
908
909
		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)
910
				return res;
911
912
913
914
915
		}
	}

	return res;
}  /* follow_Mem_chain */
Michael Beck's avatar
Michael Beck committed
916

Michael Beck's avatar
Michael Beck committed
917
/*
918
919
920
 * Check if we can replace the load by a given const from
 * the const code irg.
 */
921
922
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
923
924
925
926
927
	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);
928
929
930
931
932

	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 */
933
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
934
935
		} else {
			return NULL;
936
937
938
		}
	}
	return res;
939
}
940

Michael Beck's avatar
Michael Beck committed
941
942
/**
 * optimize a Load
943
944
 *
 * @param load  the Load node
Michael Beck's avatar
Michael Beck committed
945
 */
946
static unsigned optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
947
{
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     *mem, *ptr, *value;
	ir_entity   *ent;
	long        dummy;
	unsigned    res = 0;
953
954
955
956
957
958
959
960
961

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

964
965
966
	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 */
967
968
		exchange(info->projs[pn_Load_M], mem);

969
970
		if (info->projs[pn_Load_X_regular]) {
			/* should not happen, but if it does, remove it */
971
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
972
973
			res |= CF_CHANGED;
		}
974
		kill_node(load);
975
976
977
978
		reduce_adr_usage(ptr);
		return res | DF_CHANGED;
	}

Matthias Braun's avatar
Matthias Braun committed
979
980
981
982
983
984
985
986
	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
987

Matthias Braun's avatar
Matthias Braun committed
988
989
990
991
992
993
994
995
996
997
998
999
		/* 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
1000

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

	/* Check, if the address of this load is used more than once.
Michael Beck's avatar
Michael Beck committed
1048
1049
	 * If not, more load cannot be removed in any case. */
	if (get_irn_n_uses(ptr) <= 1 && get_irn_n_uses(get_base_and_offset(ptr, &dummy)) <= 1)
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
		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;
}  /* optimize_load */
Michael Beck's avatar
Michael Beck committed
1063

1064
1065
1066
1067