ldstopt.c 59.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Michael Beck's avatar
Michael Beck committed
6
7
8
9
/**
 * @file
 * @brief   Load/Store optimizations.
 * @author  Michael Beck
Michael Beck's avatar
Michael Beck committed
10
 */
11
#include <string.h>
Michael Beck's avatar
Michael Beck committed
12

13
#include "entity_t.h"
14
#include "error.h"
15
#include "iroptimize.h"
16
17
18
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
19
#include "type_t.h"
20
21
22
23
#include "iropt_t.h"
#include "ircons_t.h"
#include "irgmod.h"
#include "irgwalk.h"
24
#include "irtools.h"
25
26
27
28
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
29
#include "array.h"
30
#include "irhooks.h"
Michael Beck's avatar
BugFix:    
Michael Beck committed
31
#include "iredges.h"
32
#include "irmemory.h"
33
#include "irnodehashmap.h"
34
#include "irgopt.h"
35
#include "set.h"
Matthias Braun's avatar
Matthias Braun committed
36
#include "be.h"
37
38
39
40
#include "debug.h"

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

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

Matthias Braun's avatar
Matthias Braun committed
44
45
typedef enum changes_t {
	NO_CHANGES = 0,
46
47
48
49
50
	DF_CHANGED = (1 << 0), /**< data flow changed */
	CF_CHANGED = (1 << 1), /**< control flow changed */
	/** nodes have been created but are not reachable. This is a bad hack
	 * try hard to avoid it! */
	NODES_CREATED = (1 << 2),
Matthias Braun's avatar
Matthias Braun committed
51
} changes_t;
52

Michael Beck's avatar
Michael Beck committed
53
54
55
/**
 * walker environment
 */
56
typedef struct walk_env_t {
Matthias Braun's avatar
Matthias Braun committed
57
58
	struct obstack obst;    /**< list of all stores */
	changes_t      changes; /**< a bitmask of graph changes */
Michael Beck's avatar
Michael Beck committed
59
60
} walk_env_t;

61
/** A Load/Store info. */
62
typedef struct ldst_info_t {
Matthias Braun's avatar
Matthias Braun committed
63
64
65
66
	ir_node  *projs[MAX_PROJ+1]; /**< list of Proj's of this node */
	ir_node  *exc_block;         /**< the exception block if available */
	int      exc_idx;            /**< predecessor index in exception block */
	unsigned visited;            /**< visited counter for breaking loops */
Michael Beck's avatar
Michael Beck committed
67
68
} ldst_info_t;

69
/**
70
 * flags for control flow.
71
72
 */
enum block_flags_t {
Matthias Braun's avatar
Matthias Braun committed
73
74
	BLOCK_HAS_COND = 1, /**< Block has conditional control flow */
	BLOCK_HAS_EXC  = 2  /**< Block has exceptional control flow */
75
76
77
};

/**
78
 * a Block info.
79
 */
80
typedef struct block_info_t {
Matthias Braun's avatar
Matthias Braun committed
81
	unsigned flags;  /**< flags for the block */
82
83
} block_info_t;

84
/** the master visited flag for loop detection. */
Matthias Braun's avatar
Matthias Braun committed
85
static unsigned master_visited;
86
87
88
89
90

#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
91
92
93
/**
 * get the Load/Store info of a node
 */
94
95
static ldst_info_t *get_ldst_info(ir_node *node, struct obstack *obst)
{
96
	ldst_info_t *info = (ldst_info_t*)get_irn_link(node);
Matthias Braun's avatar
Matthias Braun committed
97
	if (info == NULL) {
98
		info = OALLOCZ(obst, ldst_info_t);
99
100
101
		set_irn_link(node, info);
	}
	return info;
102
}
Michael Beck's avatar
Michael Beck committed
103

104
105
106
/**
 * get the Block info of a node
 */
107
108
static block_info_t *get_block_info(ir_node *node, struct obstack *obst)
{
109
	block_info_t *info = (block_info_t*)get_irn_link(node);
Matthias Braun's avatar
Matthias Braun committed
110
	if (info == NULL) {
111
		info = OALLOCZ(obst, block_info_t);
112
113
114
		set_irn_link(node, info);
	}
	return info;
115
}
116

Michael Beck's avatar
Michael Beck committed
117
/**
Michael Beck's avatar
Michael Beck committed
118
 * update the projection info for a Load/Store
Michael Beck's avatar
Michael Beck committed
119
 */
Matthias Braun's avatar
Matthias Braun committed
120
static changes_t update_projs(ldst_info_t *info, ir_node *proj)
Michael Beck's avatar
Michael Beck committed
121
{
122
	long nr = get_Proj_proj(proj);
Michael Beck's avatar
Michael Beck committed
123

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

126
127
128
129
	if (info->projs[nr]) {
		/* there is already one, do CSE */
		exchange(proj, info->projs[nr]);
		return DF_CHANGED;
Matthias Braun's avatar
Matthias Braun committed
130
	} else {
131
		info->projs[nr] = proj;
Matthias Braun's avatar
Matthias Braun committed
132
		return NO_CHANGES;
133
	}
134
}
Michael Beck's avatar
Michael Beck committed
135
136

/**
137
138
139
140
141
 * 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
142
 */
Matthias Braun's avatar
Matthias Braun committed
143
static void update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
144
{
145
146
147
	assert(info->exc_block == NULL && "more than one exception block found");
	info->exc_block = block;
	info->exc_idx   = pos;
148
}
Michael Beck's avatar
Michael Beck committed
149
150

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

160
	if (opcode == iro_Proj) {
Matthias Braun's avatar
Matthias Braun committed
161
		ir_node *pred = get_Proj_pred(node);
162
		opcode = get_irn_opcode(pred);
163

164
		if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
Andreas Fried's avatar
Andreas Fried committed
165
			ldst_info_t *ldst_info = get_ldst_info(pred, &wenv->obst);
166
167
168
169

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

			/*
170
171
172
173
174
			 * Place the Proj's to the same block as the
			 * predecessor Load. This is always ok and prevents
			 * "non-SSA" form after optimizations if the Proj
			 * is in a wrong block.
			 */
Andreas Fried's avatar
Andreas Fried committed
175
176
			ir_node *blk      = get_nodes_block(node);
			ir_node *pred_blk = get_nodes_block(pred);
177
178
179
180
181
			if (blk != pred_blk) {
				wenv->changes |= DF_CHANGED;
				set_nodes_block(node, pred_blk);
			}
		}
182
	} else if (opcode == iro_Block) {
Matthias Braun's avatar
Matthias Braun committed
183
184
		for (int i = get_Block_n_cfgpreds(node); i-- > 0; ) {
			bool     is_exc = false;
Andreas Fried's avatar
Andreas Fried committed
185
186
			ir_node *proj   = get_Block_cfgpred(node, i);
			ir_node *pred   = proj;
187
188
189
190
191

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

Matthias Braun's avatar
Matthias Braun committed
192
193
194
195
			if (is_Proj(proj)) {
				pred   = get_Proj_pred(proj);
				is_exc = is_x_except_Proj(proj);
			}
Andreas Fried's avatar
Andreas Fried committed
196
197
			ir_node      *pred_block = get_nodes_block(pred);
			block_info_t *bl_info    = get_block_info(pred_block, &wenv->obst);
198

199
			if (is_fragile_op(pred) && is_exc)
200
201
202
203
				bl_info->flags |= BLOCK_HAS_EXC;
			else if (is_irn_forking(pred))
				bl_info->flags |= BLOCK_HAS_COND;

204
			opcode = get_irn_opcode(pred);
Matthias Braun's avatar
Matthias Braun committed
205
206
			if (is_exc && (opcode == iro_Load || opcode == iro_Store
			               || opcode == iro_Call)) {
Andreas Fried's avatar
Andreas Fried committed
207
				ldst_info_t *ldst_info = get_ldst_info(pred, &wenv->obst);
208

Matthias Braun's avatar
Matthias Braun committed
209
				update_exc(ldst_info, node, i);
210
211
			}
		}
212
213
214
	} else if (opcode == iro_CopyB) {
		/* Just initialize a ldst_info for the CopyB node. */
		(void) get_ldst_info(node, &wenv->obst);
215
	}
216
}
Michael Beck's avatar
Michael Beck committed
217

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

			/* Do not fiddle with polymorphism. */
235
			if (is_Class_type(tp) &&
Matthias Braun's avatar
Matthias Braun committed
236
237
				(get_entity_n_overwrites(ent) > 0
			     || get_entity_n_overwrittenby(ent) > 0))
238
239
240
241
				return NULL;

			if (is_Array_type(tp)) {
				/* check bounds */
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
				ir_node   *index = get_Sel_index(ptr, 0);
				ir_tarval *tv    = computed_value(index);

				/* check if the index is constant */
				if (!tarval_is_constant(tv))
					return NULL;

				ir_node   *size  = get_array_size(tp);
				ir_tarval *tsize = computed_value(size);

				if (!tarval_is_constant(tsize))
					return NULL;

				if (tarval_cmp(tv, tsize) != ir_relation_less)
					return NULL;
				/* ok, bounds check finished */
258
259
			}

Matthias Braun's avatar
Matthias Braun committed
260
			if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT)
261
262
263
264
				return ent;

			/* try next */
			ptr = get_Sel_ptr(ptr);
265
266
267
268
269
270
271
272
273
274
275
		} 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;

Matthias Braun's avatar
Matthias Braun committed
276
277
278
			/* we support only one addition, reassoc should fold all others */
			if (!is_Address(ptr) && !is_Align(ptr) && !is_Offset(ptr)
			    && !is_Sel(ptr) && !is_Size(ptr))
279
280
281
282
283
				return NULL;
		} else if (is_Sub(ptr)) {
			ir_node *l = get_Sub_left(ptr);
			ir_node *r = get_Sub_right(ptr);

284
			if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
285
286
287
				ptr = l;
			else
				return NULL;
Matthias Braun's avatar
Matthias Braun committed
288
289
290
			/* we support only one subtraction, reassoc should fold all others */
			if (!is_Address(ptr) && !is_Align(ptr) && !is_Offset(ptr)
			    && !is_Sel(ptr) && !is_Size(ptr))
291
				return NULL;
Matthias Braun's avatar
Matthias Braun committed
292
		} else {
293
			return NULL;
Matthias Braun's avatar
Matthias Braun committed
294
		}
295
	}
296
}
Michael Beck's avatar
Michael Beck committed
297

298
/* forward */
299
static void reduce_node_usage(ir_node *ptr);
300
301

/**
Christoph Mallon's avatar
Christoph Mallon committed
302
 * Update a Load that may have lost its users.
303
 */
304
305
static void handle_load_update(ir_node *load)
{
306
307
308
	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return;
309

Matthias Braun's avatar
Matthias Braun committed
310
311
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
	if (!info->projs[pn_Load_res] && !info->projs[pn_Load_X_except]) {
312
313
		ir_node *ptr = get_Load_ptr(load);
		ir_node *mem = get_Load_mem(load);
314

Christoph Mallon's avatar
Christoph Mallon committed
315
		/* a Load whose value is neither used nor exception checked, remove it */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
316
		exchange(info->projs[pn_Load_M], mem);
Matthias Braun's avatar
Matthias Braun committed
317
318
319
320
		if (info->projs[pn_Load_X_regular]) {
			ir_node *jmp = new_r_Jmp(get_nodes_block(load));
			exchange(info->projs[pn_Load_X_regular], jmp);
		}
321
		kill_node(load);
322
		reduce_node_usage(ptr);
323
	}
324
}
325
326

/**
327
 * A use of a node has vanished. Check if this was a Proj
328
329
 * node and update the counters.
 */
330
static void reduce_node_usage(ir_node *ptr)
331
{
332
333
334
335
	if (!is_Proj(ptr))
		return;
	if (get_irn_n_edges(ptr) > 0)
		return;
336

337
	/* this Proj is dead now */
Matthias Braun's avatar
Matthias Braun committed
338
	ir_node *pred = get_Proj_pred(ptr);
339
	if (is_Load(pred)) {
340
		ldst_info_t *info = (ldst_info_t*)get_irn_link(pred);
341
		info->projs[get_Proj_proj(ptr)] = NULL;
342

343
344
		/* this node lost its result proj, handle that */
		handle_load_update(pred);
345
	}
346
}
347

348
349
350
351
/**
 * Kill a Load or Store and all other nodes which are not needed after
 * it has been killed.
 */
Matthias Braun's avatar
Matthias Braun committed
352
353
static void kill_and_reduce_usage(ir_node *node)
{
354
	ir_node *ptr;
Matthias Braun's avatar
Matthias Braun committed
355
	ir_node *value;
356
357
	switch(get_irn_opcode(node)) {
	case iro_Load:
Matthias Braun's avatar
Matthias Braun committed
358
359
		ptr   = get_Load_ptr(node);
		value = NULL;
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
		break;
	case iro_Store:
		ptr   = get_Store_ptr(node);
		value = get_Store_value(node);
		break;
	default:
		panic("Cannot handle node %+F", node);
	}

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

376
377
378
379
/**
 * Check, if an already existing value of mode old_mode can be converted
 * into the needed one new_mode without loss.
 */
Matthias Braun's avatar
Matthias Braun committed
380
static bool can_use_stored_value(ir_mode *old_mode, ir_mode *new_mode)
381
{
382
	if (old_mode == new_mode)
383
384
		return true;

Andreas Fried's avatar
Andreas Fried committed
385
386
	unsigned old_size = get_mode_size_bits(old_mode);
	unsigned new_size = get_mode_size_bits(new_mode);
387
388

	/* if both modes are two-complement ones, we can always convert the
389
390
391
	   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 &&
392
		  get_mode_arithmetic(old_mode) == irma_twos_complement &&
393
394
395
396
397
398
399
		  get_mode_arithmetic(new_mode) == irma_twos_complement &&
		  (!be_get_backend_param()->byte_order_big_endian
	        || old_size == new_size)) {
		return true;
	}
	return false;
}
400

Michael Beck's avatar
Michael Beck committed
401
/**
402
 * Check whether a Call is at least pure, i.e. does only read memory.
403
 */
Matthias Braun's avatar
Matthias Braun committed
404
static bool is_Call_pure(ir_node *call)
405
{
406
	ir_type *call_tp = get_Call_type(call);
Matthias Braun's avatar
Matthias Braun committed
407
	unsigned prop    = get_method_additional_properties(call_tp);
408
409
410
411

	/* check first the call type */
	if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
		/* try the called entity */
412
413
414
		ir_entity *callee = get_Call_callee(call);
		if (callee != NULL) {
			prop = get_entity_additional_properties(callee);
415
416
		}
	}
Matthias Braun's avatar
Matthias Braun committed
417
	return prop & (mtp_property_const|mtp_property_pure);
418
}
419

Michael Beck's avatar
Michael Beck committed
420
static ir_node *get_base_and_offset(ir_node *ptr, long *pOffset)
421
{
Michael Beck's avatar
Michael Beck committed
422
423
	ir_mode *mode  = get_irn_mode(ptr);
	long    offset = 0;
424
425

	/* TODO: long might not be enough, we should probably use some tarval thingy... */
Michael Beck's avatar
Michael Beck committed
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
	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)) {
Matthias Braun's avatar
Matthias Braun committed
450
				assert(get_Sel_n_indexs(ptr) == 1);
yb9976's avatar
yb9976 committed
451
				ir_node *index = get_Sel_index(ptr, 0);
Matthias Braun's avatar
Matthias Braun committed
452
				if (!is_Const(index))
Michael Beck's avatar
Michael Beck committed
453
454
					break;

Matthias Braun's avatar
Matthias Braun committed
455
456
				ir_type *element_type = get_entity_type(ent);
				if (get_type_state(element_type) != layout_fixed)
Michael Beck's avatar
Michael Beck committed
457
458
					break;

Matthias Braun's avatar
Matthias Braun committed
459
				int size = get_type_size_bytes(element_type);
Michael Beck's avatar
Michael Beck committed
460
461
462
463
464
465
466
467
				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
468
469
470
			break;
	}

Michael Beck's avatar
Michael Beck committed
471
472
	*pOffset = offset;
	return ptr;
473
474
}

Matthias Braun's avatar
Matthias Braun committed
475
476
static changes_t try_load_after_store(ir_node *load, ir_node *load_base_ptr,
                                      long load_offset, ir_node *store)
477
478
{
	ir_node *store_ptr      = get_Store_ptr(store);
Michael Beck's avatar
Michael Beck committed
479
480
	long     store_offset;
	ir_node *store_base_ptr = get_base_and_offset(store_ptr, &store_offset);
481
482

	if (load_base_ptr != store_base_ptr)
Matthias Braun's avatar
Matthias Braun committed
483
		return NO_CHANGES;
484

Andreas Fried's avatar
Andreas Fried committed
485
486
487
488
489
490
	ir_mode *load_mode      = get_Load_mode(load);
	long     load_mode_len  = get_mode_size_bytes(load_mode);
	ir_mode *store_mode     = get_irn_mode(get_Store_value(store));
	long     store_mode_len = get_mode_size_bytes(store_mode);
	long     delta          = load_offset - store_offset;
	ir_node *store_value    = get_Store_value(store);
491

yb9976's avatar
yb9976 committed
492
	/* Ensure that Load is completely contained in Store. */
493
	if (delta < 0 || delta+load_mode_len > store_mode_len)
Matthias Braun's avatar
Matthias Braun committed
494
		return NO_CHANGES;
495

496
497
498
499
500
501
502
503
504
505
506
507
	if (store_mode != load_mode) {
		if (get_mode_arithmetic(store_mode) == irma_twos_complement &&
		    get_mode_arithmetic(load_mode)  == irma_twos_complement) {

			/* produce a shift to adjust offset delta */
			unsigned const shift = be_get_backend_param()->byte_order_big_endian
				? store_mode_len - load_mode_len - delta
				: delta;
			if (shift != 0) {
				ir_graph *const irg  = get_irn_irg(load);
				ir_node  *const cnst = new_r_Const_long(irg, mode_Iu, shift * 8);
				store_value = new_r_Shr(get_nodes_block(load),
yb9976's avatar
yb9976 committed
508
				                        store_value, cnst, store_mode);
509
			}
510

511
512
513
			store_value = new_r_Conv(get_nodes_block(load), store_value, load_mode);
		} else {
			/* we would need some kind of bitcast node here */
Matthias Braun's avatar
Matthias Braun committed
514
			return NO_CHANGES;
515
		}
516
517
	}

Michael Beck's avatar
Michael Beck committed
518
519
	DBG_OPT_RAW(load, store_value);

Andreas Fried's avatar
Andreas Fried committed
520
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
521
522
523
	if (info->projs[pn_Load_M])
		exchange(info->projs[pn_Load_M], get_Load_mem(load));

Matthias Braun's avatar
Matthias Braun committed
524
	changes_t res = NO_CHANGES;
525
526
	/* no exception */
	if (info->projs[pn_Load_X_except]) {
527
		ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
528
529
		ir_node  *bad = new_r_Bad(irg, mode_X);
		exchange(info->projs[pn_Load_X_except], bad);
530
531
532
		res |= CF_CHANGED;
	}
	if (info->projs[pn_Load_X_regular]) {
Matthias Braun's avatar
Matthias Braun committed
533
534
		ir_node *jmp = new_r_Jmp(get_nodes_block(load));
		exchange(info->projs[pn_Load_X_regular], jmp);
535
536
537
538
539
540
		res |= CF_CHANGED;
	}

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

541
	kill_and_reduce_usage(load);
542
543
544
	return res | DF_CHANGED;
}

yb9976's avatar
yb9976 committed
545
546
static ir_node *try_update_ptr_CopyB(ir_node *load, ir_node *load_base_ptr,
                                     long load_offset, ir_node *copyB)
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
{
	ir_node *copyB_dst = get_CopyB_dst(copyB);
	long     dst_offset;
	ir_node *dst_base_ptr = get_base_and_offset(copyB_dst, &dst_offset);

	if (load_base_ptr != dst_base_ptr) {
		return NULL;
	}

	/*
	 * There are quite a few offsets here, please do not get
	 * confused: The CopyB node copies n_copy bytes from
	 * (src_base_ptr + src_offset) to (dst_base_ptr + dst_offset)
	 * (calculated in bytes; no pointer arithmetic). The Load
	 * loads from (dst_base_ptr + load_offset). This is translated
	 * into load_src_offset, which points to the same data in the
	 * CopyB's source array, if it is within its bounds.
	 */
	ir_type *copyB_type      = get_CopyB_type(copyB);
	long     n_copy          = get_type_size_bytes(copyB_type);

	ir_node *copyB_src       = get_CopyB_src(copyB);
	long     src_offset;
	ir_node *src_base_ptr    = get_base_and_offset(copyB_src, &src_offset);

	long     load_src_offset = src_offset - dst_offset + load_offset;

	ir_mode *load_mode       = get_Load_mode(load);
	long     load_size       = get_mode_size_bytes(load_mode);

Matthias Braun's avatar
Matthias Braun committed
577
	if (load_src_offset + load_size > n_copy || load_src_offset < src_offset) {
578
579
580
581
582
583
584
585
586
587
588
		return NULL;
	}

	/*
	 * Everything is OK, we can replace
	 *   ptr = (load_base_ptr + load_offset)
	 * with
	 *   new_load_ptr = (src_base_ptr + load_src_offset)
	 */
	ir_graph *irg          = get_irn_irg(load);
	ir_node  *block        = get_nodes_block(load);
589
590
591
592
	ir_mode  *mode_ref     = get_irn_mode(src_base_ptr);
	ir_mode  *mode_ref_int = get_reference_mode_unsigned_eq(mode_ref);
	ir_node  *cnst         = new_r_Const_long(irg, mode_ref_int, load_src_offset);
	ir_node  *new_load_ptr = new_r_Add(block, src_base_ptr, cnst, mode_ref);
593
594
595
	return new_load_ptr;
}

596
597
598
599
/**
 * 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
600
601
602
603
604
605
 * 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
 */
Matthias Braun's avatar
Matthias Braun committed
606
static changes_t follow_Mem_chain(ir_node *load, ir_node *curr)
607
{
Matthias Braun's avatar
Matthias Braun committed
608
	changes_t    res  = NO_CHANGES;
609
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Michael Beck's avatar
Michael Beck committed
610
611
612
	ir_node     *ptr       = get_Load_ptr(load);
	ir_node     *mem       = get_Load_mem(load);
	ir_mode     *load_mode = get_Load_mode(load);
613

Matthias Braun's avatar
Matthias Braun committed
614
615
	ir_node *pred = curr;
	while (load != pred) {
616
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
617
618

		/*
619
620
		 * 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
621
		 * exception handler OR they are in the same Block. In the latter
622
623
624
625
626
		 * 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
627
		 * the load Block :-(
628
629
		 * We could make it a little bit better if we would know that the
		 * exception handler of the Store jumps directly to the end...
630
		 */
631
632
		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
633
				|| get_nodes_block(load) == get_nodes_block(pred)))
634
		{
Matthias Braun's avatar
Matthias Braun committed
635
636
637
			long      load_offset;
			ir_node  *base_ptr = get_base_and_offset(ptr, &load_offset);
			changes_t changes  = try_load_after_store(load, base_ptr, load_offset, pred);
Michael Beck's avatar
Michael Beck committed
638

Matthias Braun's avatar
Matthias Braun committed
639
			if (changes != NO_CHANGES)
640
				return res | changes;
641
		} else if (is_Load(pred) && get_Load_ptr(pred) == ptr &&
642
		           can_use_stored_value(get_Load_mode(pred), load_mode)) {
643
644
			/*
			 * a Load after a Load -- a read after read.
Matthias Braun's avatar
Matthias Braun committed
645
646
647
648
			 * 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.
649
			 *
Matthias Braun's avatar
Matthias Braun committed
650
651
652
			 * Here, there is no need to check if the previous Load has an
			 * exception hander because they would have exact the same
			 * exception...
653
654
655
			 *
			 * TODO: implement load-after-load with different mode for big
			 *       endian
656
			 */
Matthias Braun's avatar
Matthias Braun committed
657
658
			if (info->projs[pn_Load_X_except] == NULL
					|| get_nodes_block(load) == get_nodes_block(pred)) {
659
660
				DBG_OPT_RAR(load, pred);

661
662
663
664
				/* the result is used */
				if (info->projs[pn_Load_res]) {
					if (pred_info->projs[pn_Load_res] == NULL) {
						/* create a new Proj again */
665
						pred_info->projs[pn_Load_res] = new_r_Proj(pred, get_Load_mode(pred), pn_Load_res);
666
					}
Andreas Fried's avatar
Andreas Fried committed
667
					ir_node *value = pred_info->projs[pn_Load_res];
668
669
670

					/* add an convert if needed */
					if (get_Load_mode(pred) != load_mode) {
671
						value = new_r_Conv(get_nodes_block(load), value, load_mode);
672
673
					}

674
					exchange(info->projs[pn_Load_res], value);
675
676
				}

677
678
679
				if (info->projs[pn_Load_M])
					exchange(info->projs[pn_Load_M], mem);

680
681
				/* no exception */
				if (info->projs[pn_Load_X_except]) {
682
					ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
683
					exchange(info->projs[pn_Load_X_except], new_r_Bad(irg, mode_X));
684
685
					res |= CF_CHANGED;
				}
686
				if (info->projs[pn_Load_X_regular]) {
687
					exchange( info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
688
689
					res |= CF_CHANGED;
				}
690

691
				kill_and_reduce_usage(load);
692
693
694
695
				return res |= DF_CHANGED;
			}
		}

696
		if (is_Store(pred)) {
697
			/* check if we can pass through this store */
698
699
			ir_alias_relation rel = get_alias_relation(
				get_Store_ptr(pred),
700
701
702
				get_type_for_mode(get_irn_mode(get_Store_value(pred))),
				ptr,
				get_type_for_mode(load_mode));
703
			/* if the might be an alias, we cannot pass this Store */
Michael Beck's avatar
Michael Beck committed
704
			if (rel != ir_no_alias)
705
706
				break;
			pred = skip_Proj(get_Store_mem(pred));
707
		} else if (is_Load(pred)) {
708
			pred = skip_Proj(get_Load_mem(pred));
709
710
711
712
713
714
715
716
717
		} 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;
			}
718
719
720
721
722
723
724
725
726
727
728
729
730
731
		} else if (is_CopyB(pred)) {
			/*
			 * We cannot replace the Load with another
			 * Load from the CopyB's source directly,
			 * because there may be Stores in between,
			 * destroying the source data. However, we can
			 * use the source address from this point
			 * onwards for further optimizations.
			 */
			long     load_offset;
			ir_node *base_ptr = get_base_and_offset(ptr, &load_offset);
			ir_node *new_ptr  = try_update_ptr_CopyB(load, base_ptr, load_offset, pred);

			if (new_ptr) {
732
				res |= NODES_CREATED;
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
				ptr = new_ptr;
				/*
				 * Special case: If new_ptr points to
				 * a constant, we *can* replace the
				 * Load immediately.
				 */
				if (find_constant_entity(new_ptr)) {
					set_Load_ptr(load, new_ptr);
					return res | DF_CHANGED;
				}
			} else {
				ir_alias_relation rel = get_alias_relation(
					get_CopyB_dst(pred),
					get_CopyB_type(pred),
					ptr,
					get_type_for_mode(load_mode));
				if (rel != ir_no_alias)
					break;
			}

			pred = skip_Proj(get_CopyB_mem(pred));
754
755
756
757
758
759
760
761
762
763
764
		} else {
			/* follow only Load chains */
			break;
		}

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

765
	if (is_Sync(pred)) {
766
		/* handle all Sync predecessors */
Matthias Braun's avatar
Matthias Braun committed
767
		for (int i = get_Sync_n_preds(pred); i-- > 0; ) {
768
769
			res |=  follow_Mem_chain(load, skip_Proj(get_Sync_pred(pred, i)));
			if (res & ~NODES_CREATED)
770
				return res;
771
772
773
774
		}
	}

	return res;
775
}
Michael Beck's avatar
Michael Beck committed
776

777
778
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
779
780
781
782
	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);
783
	ir_node  *res    = duplicate_subgraph(dbgi, c, block);
784
785
786
787
788

	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 */
789
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
790
791
		} else {
			return NULL;
792
793
794
		}
	}
	return res;
795
}
796

Michael Beck's avatar
Michael Beck committed
797
798
/**
 * optimize a Load
799
800
 *
 * @param load  the Load node
Michael Beck's avatar
Michael Beck committed
801
 */
Matthias Braun's avatar
Matthias Braun committed
802
static changes_t optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
803
{
804
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
Matthias Braun's avatar
Matthias Braun committed
805
	changes_t    res  = NO_CHANGES;
806
807
808

	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
Matthias Braun's avatar
Matthias Braun committed
809
		return NO_CHANGES;
810
811

	/* the address of the load to be optimized */
Andreas Fried's avatar
Andreas Fried committed
812
	ir_node *ptr = get_Load_ptr(load);
813
814

	/* The mem of the Load. Must still be returned after optimization. */
Andreas Fried's avatar
Andreas Fried committed
815
	ir_node *mem = get_Load_mem(load);
816

817
818
819
	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 */
820
821
		exchange(info->projs[pn_Load_M], mem);

822
823
		if (info->projs[pn_Load_X_regular]) {
			/* should not happen, but if it does, remove it */
824
			exchange(info->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load)));
825
826
			res |= CF_CHANGED;
		}
827
		kill_and_reduce_usage(load);
828
829
830
831
		return res | DF_CHANGED;
	}

	/* Check, if the address of this load is used more than once.
Michael Beck's avatar
Michael Beck committed
832
	 * If not, more load cannot be removed in any case. */
Andreas Fried's avatar
Andreas Fried committed
833
	long dummy;
834
	if (get_irn_n_edges(ptr) <= 1 && get_irn_n_edges(get_base_and_offset(ptr, &dummy)) <= 1)
835
836
837
838
839
840
841
842
843
844
845
846
		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;
847
}
Michael Beck's avatar
Michael Beck committed
848

849
850
851
852
853
854
855
/**
 * Check whether a value of mode new_mode would completely overwrite a value
 * of mode old_mode in memory.
 */
static int is_completely_overwritten(ir_mode *old_mode, ir_mode *new_mode)
{
	return get_mode_size_bits(new_mode) >= get_mode_size_bits(old_mode);
856
}
857

858
859
860
861
862
863
864
865
866
867
868
869
/**
 * Check whether small is a part of large (starting at same address).
 */
static int is_partially_same(ir_node *small, ir_node *large)
{
	ir_mode *sm = get_irn_mode(small);
	ir_mode *lm = get_irn_mode(large);

	/* FIXME: Check endianness */
	return is_Conv(small) && get_Conv_op(small) == large
	    && get_mode_size_bytes(sm) < get_mode_size_bytes(lm)
	    && get_mode_arithmetic(sm) == irma_twos_complement
870
	    && get_mode_arithmetic(lm) == irma_twos_complement;
871
}
872

Michael Beck's avatar
Michael Beck committed
873
/**
Matthias Braun's avatar
Matthias Braun committed
874
875
 * follow the memory chain as long as there are only Loads and alias free
 * Stores.
Michael Beck's avatar
Michael Beck committed
876
877
 * INC_MASTER() must be called before dive into
 */
Matthias Braun's avatar
Matthias Braun committed
878
879
static changes_t follow_Mem_chain_for_Store(ir_node *store, ir_node *curr,
                                            bool had_split)
880
{
Matthias Braun's avatar
Matthias Braun committed
881
882
883
884
885
886
887
888
889
890
	changes_t    res   = NO_CHANGES;
	ldst_info_t *info  = (ldst_info_t*)get_irn_link(store);
	ir_node     *ptr   = get_Store_ptr(store);
	ir_node     *mem   = get_Store_mem(store);
	ir_node     *value = get_Store_value(store);
	ir_mode     *mode  = get_irn_mode(value);
	ir_node     *block = get_nodes_block(store);

	ir_node *pred = curr;
	while (pred != store) {
891
		ldst_info_t *pred_info = (ldst_info_t*)get_irn_link(pred);
892
893
894
895
896
897

		/*
		 * BEWARE: one might think that checking the modes is useless, because
		 * if the pointers are identical, they refer to the same object.
		 * This is only true in strong typed languages, not is C were the following
		 * is possible *(ir_type1 *)p = a; *(ir_type2 *)p = b ...
898
899
900
		 * However, if the size of the mode that is written is bigger or equal the
		 * size of the old one, the old value is completely overwritten and can be
		 * killed ...
901
		 */
902
		if (is_Store(pred) && !had_split && get_Store_ptr(pred) == ptr &&
yb9976's avatar
yb9976 committed
903
		    get_nodes_block(pred) == block) {
904
			/*
Matthias Braun's avatar
Matthias Braun committed
905
			 * a Store after a Store in the same Block -- a write after write.
906
907
908
909
910
911
			 */

			/*
			 * We may remove the first Store, if the old value is completely
			 * overwritten or the old value is a part of the new value,
			 * and if it does not have an exception handler.
912
913
914
			 *
			 * TODO: What, if both have the same exception handler ???
			 */
915
916
917
918
919
			if (get_Store_volatility(pred) != volatility_is_volatile
			        && !pred_info->projs[pn_Store_X_except]) {
				ir_node *predvalue = get_Store_value(pred);
				ir_mode *predmode  = get_irn_mode(predvalue);

920
				if (is_completely_overwritten(predmode, mode)
921
922
				        || is_partially_same(predvalue, value)) {
					DBG_OPT_WAW(pred, store);
923
					DB((dbg, LEVEL_1, "  killing store %+F (override by %+F)\n", pred, store));
924
					exchange(pred_info->projs[pn_Store_M], get_Store_mem(pred));
925
					kill_and_reduce_usage(pred);
926
927
928
929
930
931
932
933
934
935
936
937
938
939
					return DF_CHANGED;
				}
			}

			/*
			 * We may remove the Store, if the old value already contains
			 * the new value, and if it does not have an exception handler.
			 *
			 * TODO: What, if both have the same exception handler ???
			 */
			if (get_Store_volatility(store) != volatility_is_volatile
			        && !info->projs[pn_Store_X_except]) {
				ir_node *predvalue = get_Store_value(pred);

940
				if (is_partially_same(value, predvalue)) {
941
					DBG_OPT_WAW(pred, store);
942
					DB((dbg, LEVEL_1, "  killing store %+F (override by %+F)\n", pred, store));
943
					exchange(info->projs[pn_Store_M], mem);
944
					kill_and_reduce_usage(store);
945
946
					return DF_CHANGED;
				}
947
			}
948
		} else if (is_Load(pred) && get_Load_ptr(pred) == ptr &&
949
950
		           value == pred_info->projs[pn_Load_res]) {
			/*
951
952
953
954
			 * a Store of a value just loaded from the same address
			 * -- a write after read.
			 * We may remove the Store, if it does not have an exception
			 * handler.
955
			 */
Matthias Braun's avatar
Matthias Braun committed
956
			if (!info->projs[pn_Store_X_except]) {
957
				DBG_OPT_WAR(store, pred);
958
				DB((dbg, LEVEL_1, "  killing store %+F (read %+F from same address)\n", store, pred));
959
				exchange(info->projs[pn_Store_M], mem);
960
				kill_and_reduce_usage(store);
961
962
963
964
				return DF_CHANGED;
			}
		}

965
		if (is_Store(pred)) {
Michael Beck's avatar
Michael Beck committed
966
			/* check if we can pass through this store */
967
968
			ir_alias_relation rel = get_alias_relation(
				get_Store_ptr(pred),
969
970
971
				get_type_for_mode(get_irn_mode(get_Store_value(