ldstopt.c 57.3 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

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

/** 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
71
72
73
74
75
76
77
78
79
80
typedef struct base_offset_t {
	ir_node *base;
	long     offset;
} base_offset_t;

typedef struct track_load_env_t {
	ir_node      *load;
	base_offset_t base_offset;
	ir_node      *ptr; /* deprecated: alternative representation of
	                      base_offset */
} track_load_env_t;

81
/**
82
 * flags for control flow.
83
 */
Matthias Braun's avatar
Matthias Braun committed
84
85
86
87
typedef enum block_flags_t {
	BLOCK_HAS_COND = (1 << 0), /**< Block has conditional control flow */
	BLOCK_HAS_EXC  = (1 << 1), /**< Block has exceptional control flow */
} block_flags_t;
88
89

/**
90
 * a Block info.
91
 */
92
typedef struct block_info_t {
Matthias Braun's avatar
Matthias Braun committed
93
	block_flags_t flags;  /**< flags for the block */
94
95
} block_info_t;

96
/** the master visited flag for loop detection. */
Matthias Braun's avatar
Matthias Braun committed
97
static unsigned master_visited;
98
99
100
101
102

#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
103
104
105
/**
 * get the Load/Store info of a node
 */
106
107
static ldst_info_t *get_ldst_info(ir_node *node, struct obstack *obst)
{
108
	ldst_info_t *info = (ldst_info_t*)get_irn_link(node);
Matthias Braun's avatar
Matthias Braun committed
109
	if (info == NULL) {
110
		info = OALLOCZ(obst, ldst_info_t);
111
112
113
		set_irn_link(node, info);
	}
	return info;
114
}
Michael Beck's avatar
Michael Beck committed
115

116
117
118
/**
 * get the Block info of a node
 */
119
120
static block_info_t *get_block_info(ir_node *node, struct obstack *obst)
{
121
	block_info_t *info = (block_info_t*)get_irn_link(node);
Matthias Braun's avatar
Matthias Braun committed
122
	if (info == NULL) {
123
		info = OALLOCZ(obst, block_info_t);
124
125
126
		set_irn_link(node, info);
	}
	return info;
127
}
128

Michael Beck's avatar
Michael Beck committed
129
/**
Michael Beck's avatar
Michael Beck committed
130
 * update the projection info for a Load/Store
Michael Beck's avatar
Michael Beck committed
131
 */
Matthias Braun's avatar
Matthias Braun committed
132
static changes_t update_projs(ldst_info_t *info, ir_node *proj)
Michael Beck's avatar
Michael Beck committed
133
{
134
	long nr = get_Proj_proj(proj);
Matthias Braun's avatar
Matthias Braun committed
135
	assert(0 <= nr && nr <= MAX_PROJ);
Michael Beck's avatar
Michael Beck committed
136

Matthias Braun's avatar
Matthias Braun committed
137
	if (info->projs[nr] != NULL) {
138
139
140
		/* there is already one, do CSE */
		exchange(proj, info->projs[nr]);
		return DF_CHANGED;
Matthias Braun's avatar
Matthias Braun committed
141
	} else {
142
		info->projs[nr] = proj;
Matthias Braun's avatar
Matthias Braun committed
143
		return NO_CHANGES;
144
	}
145
}
Michael Beck's avatar
Michael Beck committed
146
147

/**
148
149
150
151
152
 * 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
153
 */
Matthias Braun's avatar
Matthias Braun committed
154
static void update_exc(ldst_info_t *info, ir_node *block, int pos)
Michael Beck's avatar
Michael Beck committed
155
{
Matthias Braun's avatar
Matthias Braun committed
156
	assert(info->exc_block == NULL);
157
158
	info->exc_block = block;
	info->exc_idx   = pos;
159
}
Michael Beck's avatar
Michael Beck committed
160
161

/**
162
 * walker, collects all Proj/Load/Store/Call/CopyB nodes
163
 *
164
 * walks from Start -> End
Michael Beck's avatar
Michael Beck committed
165
 */
Michael Beck's avatar
Michael Beck committed
166
static void collect_nodes(ir_node *node, void *env)
Michael Beck's avatar
Michael Beck committed
167
{
Matthias Braun's avatar
Matthias Braun committed
168
169
	walk_env_t *wenv   = (walk_env_t *)env;
	unsigned    opcode = get_irn_opcode(node);
170

171
	if (opcode == iro_Proj) {
Matthias Braun's avatar
Matthias Braun committed
172
		ir_node *pred = get_Proj_pred(node);
173
		opcode = get_irn_opcode(pred);
174

175
		if (opcode == iro_Load || opcode == iro_Store || opcode == iro_Call) {
Andreas Fried's avatar
Andreas Fried committed
176
			ldst_info_t *ldst_info = get_ldst_info(pred, &wenv->obst);
177
178
179
180

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

			/*
181
182
183
184
185
			 * 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
186
187
			ir_node *blk      = get_nodes_block(node);
			ir_node *pred_blk = get_nodes_block(pred);
188
189
190
191
192
			if (blk != pred_blk) {
				wenv->changes |= DF_CHANGED;
				set_nodes_block(node, pred_blk);
			}
		}
193
	} else if (opcode == iro_Block) {
Matthias Braun's avatar
Matthias Braun committed
194
195
		for (int i = get_Block_n_cfgpreds(node); i-- > 0; ) {
			bool     is_exc = false;
Andreas Fried's avatar
Andreas Fried committed
196
197
			ir_node *proj   = get_Block_cfgpred(node, i);
			ir_node *pred   = proj;
198
199
200
201
202

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

Matthias Braun's avatar
Matthias Braun committed
203
204
205
206
			if (is_Proj(proj)) {
				pred   = get_Proj_pred(proj);
				is_exc = is_x_except_Proj(proj);
			}
Andreas Fried's avatar
Andreas Fried committed
207
208
			ir_node      *pred_block = get_nodes_block(pred);
			block_info_t *bl_info    = get_block_info(pred_block, &wenv->obst);
209

210
			if (is_fragile_op(pred) && is_exc)
211
212
213
214
				bl_info->flags |= BLOCK_HAS_EXC;
			else if (is_irn_forking(pred))
				bl_info->flags |= BLOCK_HAS_COND;

215
			opcode = get_irn_opcode(pred);
Matthias Braun's avatar
Matthias Braun committed
216
217
			if (is_exc && (opcode == iro_Load || opcode == iro_Store
			               || opcode == iro_Call)) {
Andreas Fried's avatar
Andreas Fried committed
218
				ldst_info_t *ldst_info = get_ldst_info(pred, &wenv->obst);
219

Matthias Braun's avatar
Matthias Braun committed
220
				update_exc(ldst_info, node, i);
221
222
			}
		}
223
224
225
	} else if (opcode == iro_CopyB) {
		/* Just initialize a ldst_info for the CopyB node. */
		(void) get_ldst_info(node, &wenv->obst);
226
	}
227
}
Michael Beck's avatar
Michael Beck committed
228

229
/* forward */
230
static void reduce_node_usage(ir_node *ptr);
231
232

/**
Christoph Mallon's avatar
Christoph Mallon committed
233
 * Update a Load that may have lost its users.
234
 */
235
236
static void handle_load_update(ir_node *load)
{
237
238
239
	/* do NOT touch volatile loads for now */
	if (get_Load_volatility(load) == volatility_is_volatile)
		return;
240

Matthias Braun's avatar
Matthias Braun committed
241
242
	ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
	if (!info->projs[pn_Load_res] && !info->projs[pn_Load_X_except]) {
243
244
		ir_node *ptr = get_Load_ptr(load);
		ir_node *mem = get_Load_mem(load);
245

Christoph Mallon's avatar
Christoph Mallon committed
246
		/* a Load whose value is neither used nor exception checked, remove it */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
247
		exchange(info->projs[pn_Load_M], mem);
Matthias Braun's avatar
Matthias Braun committed
248
249
250
251
		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);
		}
252
		kill_node(load);
253
		reduce_node_usage(ptr);
254
	}
255
}
256
257

/**
258
 * A use of a node has vanished. Check if this was a Proj
259
260
 * node and update the counters.
 */
261
static void reduce_node_usage(ir_node *ptr)
262
{
263
264
265
266
	if (!is_Proj(ptr))
		return;
	if (get_irn_n_edges(ptr) > 0)
		return;
267

268
	/* this Proj is dead now */
Matthias Braun's avatar
Matthias Braun committed
269
	ir_node *pred = get_Proj_pred(ptr);
270
	if (is_Load(pred)) {
271
		ldst_info_t *info = (ldst_info_t*)get_irn_link(pred);
272
		info->projs[get_Proj_proj(ptr)] = NULL;
273

274
275
		/* this node lost its result proj, handle that */
		handle_load_update(pred);
276
	}
277
}
278

279
280
281
282
/**
 * 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
283
284
static void kill_and_reduce_usage(ir_node *node)
{
285
	ir_node *ptr;
Matthias Braun's avatar
Matthias Braun committed
286
	ir_node *value;
287
288
	switch(get_irn_opcode(node)) {
	case iro_Load:
Matthias Braun's avatar
Matthias Braun committed
289
290
		ptr   = get_Load_ptr(node);
		value = NULL;
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
		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);
	}
}

Michael Beck's avatar
Michael Beck committed
307
/**
308
 * Check whether a Call is at least pure, i.e. does only read memory.
309
 */
Matthias Braun's avatar
Matthias Braun committed
310
static bool is_Call_pure(ir_node *call)
311
{
312
	ir_type *call_tp = get_Call_type(call);
Matthias Braun's avatar
Matthias Braun committed
313
	unsigned prop    = get_method_additional_properties(call_tp);
314
315
316
317

	/* check first the call type */
	if ((prop & (mtp_property_const|mtp_property_pure)) == 0) {
		/* try the called entity */
318
319
320
		ir_entity *callee = get_Call_callee(call);
		if (callee != NULL) {
			prop = get_entity_additional_properties(callee);
321
322
		}
	}
Matthias Braun's avatar
Matthias Braun committed
323
	return prop & (mtp_property_const|mtp_property_pure);
324
}
325

326
static void get_base_and_offset(ir_node *ptr, base_offset_t *base_offset)
327
{
328
329
330
331
	/* TODO: long might not be enough, we should probably use some tarval
	 * thingy, or at least detect long overflows and abort */
	long     offset = 0;
	ir_mode *mode   = get_irn_mode(ptr);
Michael Beck's avatar
Michael Beck committed
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
	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
356
				assert(get_Sel_n_indexs(ptr) == 1);
yb9976's avatar
yb9976 committed
357
				ir_node *index = get_Sel_index(ptr, 0);
Matthias Braun's avatar
Matthias Braun committed
358
				if (!is_Const(index))
Michael Beck's avatar
Michael Beck committed
359
360
					break;

Matthias Braun's avatar
Matthias Braun committed
361
362
				ir_type *element_type = get_entity_type(ent);
				if (get_type_state(element_type) != layout_fixed)
Michael Beck's avatar
Michael Beck committed
363
364
					break;

Matthias Braun's avatar
Matthias Braun committed
365
				int size = get_type_size_bytes(element_type);
Michael Beck's avatar
Michael Beck committed
366
367
368
369
370
371
372
373
				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
374
375
376
			break;
	}

377
378
	base_offset->offset = offset;
	base_offset->base   = ptr;
379
380
}

381
382
383
384
385
386
387
388
389
390
/**
 * This is called for load-after-load and load-after-store.
 * If possible the value of the previous load/store is transformed in a way
 * so the 2nd load can be left out/replaced by arithmetic on the previous
 * value.
 */
static ir_node *transform_previous_value(ir_mode *const load_mode,
	const base_offset_t *const load_bo, ir_mode *const prev_mode,
	const base_offset_t *const prev_bo, ir_node *const prev_value,
	ir_node *const block)
391
{
392
393
	if (load_bo->base != prev_bo->base)
		return NULL;
394

395
396
397
398
399
400
401
402
	/* ensure the load value is completely contained in the previous one */
	long delta = load_bo->offset - prev_bo->offset;
	if (delta < 0)
		return NULL;
	long load_mode_len = get_mode_size_bytes(load_mode);
	long prev_mode_len = get_mode_size_bytes(prev_mode);
	if (delta+load_mode_len > prev_mode_len)
		return NULL;
403

404
405
406
407
408
409
	/* simple case: previous value has the same mode */
	if (load_mode == prev_mode)
		return prev_value;

	/* two complement values can be transformed with bitops */
	if (get_mode_arithmetic(prev_mode) == irma_twos_complement &&
410
		get_mode_arithmetic(load_mode) == irma_twos_complement) {
411
412
413
414
415
416
417
418
419
		/* produce a shift to adjust offset delta */
		unsigned const shift = be_get_backend_param()->byte_order_big_endian
			? prev_mode_len - load_mode_len - delta
			: delta;
		ir_node *new_value = prev_value;
		if (shift != 0) {
			ir_graph *const irg   = get_Block_irg(block);
			ir_node  *const cnst  = new_r_Const_long(irg, mode_Iu, shift * 8);
			new_value = new_r_Shr(block, new_value, cnst, prev_mode);
420
		}
421
422

		return new_r_Conv(block, new_value, load_mode);
423
424
	}

425
426
427
	/* we would need some kind of bitcast to handle non two complement values */
	return NULL;
}
Michael Beck's avatar
Michael Beck committed
428

429
430
static changes_t replace_load(ir_node *load, ir_node *new_value)
{
Matthias Braun's avatar
Matthias Braun committed
431
	const ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
432
433
434
	if (info->projs[pn_Load_M])
		exchange(info->projs[pn_Load_M], get_Load_mem(load));

Matthias Braun's avatar
Matthias Braun committed
435
	changes_t res = NO_CHANGES;
436
	/* no exception */
437
	if (info->projs[pn_Load_X_except] != NULL) {
438
		ir_graph *irg = get_irn_irg(load);
Matthias Braun's avatar
Matthias Braun committed
439
440
		ir_node  *bad = new_r_Bad(irg, mode_X);
		exchange(info->projs[pn_Load_X_except], bad);
441
		res |= CF_CHANGED;
442
443

		assert(info->projs[pn_Load_X_regular] != NULL);
Matthias Braun's avatar
Matthias Braun committed
444
445
		ir_node *jmp = new_r_Jmp(get_nodes_block(load));
		exchange(info->projs[pn_Load_X_regular], jmp);
446
447
	}

448
449
450
	/* loads without user should already be optimized away */
	assert(info->projs[pn_Load_res] != NULL);
	exchange(info->projs[pn_Load_res], new_value);
451

452
	kill_and_reduce_usage(load);
453
454
455
	return res | DF_CHANGED;
}

456
457
458
459
460
/**
 * returns false if op cannot be reached through the X_regular proj of
 * @p prev_op or if there are no exceptions possible.
 */
static bool on_regular_path(ir_node *op, ir_node *prev_op)
461
{
462
463
464
465
466
	/* TODO: create a real test, for now we just make sure the previous node
	 * does not throw an exception. */
	(void)op;
	return !is_fragile_op(prev_op) || !ir_throws_exception(prev_op);
}
467

468
469
470
471
472
static changes_t try_load_after_store(track_load_env_t *env, ir_node *store)
{
	ir_node *const load = env->load;
	if (!on_regular_path(load, store))
		return NO_CHANGES;
473

474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
	ir_node      *store_ptr = get_Store_ptr(store);
	base_offset_t base_offset;
	get_base_and_offset(store_ptr, &base_offset);

	ir_mode *const load_mode   = get_Load_mode(load);
	ir_mode *const store_mode  = get_irn_mode(get_Store_value(store));
	ir_node *const store_value = get_Store_value(store);
	ir_node *const block       = get_nodes_block(load);

	/* load value completely contained in previsou store? */
	ir_node *const new_value
		= transform_previous_value(load_mode, &env->base_offset, store_mode,
		                           &base_offset, store_value, block);
	if (new_value == NULL)
		return NO_CHANGES;
489

490
491
492
	DBG_OPT_RAW(load, new_value);
	return replace_load(load, new_value);
}
493

494
495
496
497
498
static changes_t try_load_after_load(track_load_env_t *env, ir_node *prev_load)
{
	ir_node *const load = env->load;
	if (!on_regular_path(load, prev_load))
		return NO_CHANGES;
499

Matthias Braun's avatar
Matthias Braun committed
500
	const ldst_info_t *info = (ldst_info_t*)get_irn_link(prev_load);
501
502
503
504
	ir_node *const prev_value = info->projs[pn_Load_res];
	/* the other load is unused and will get removed later anyway */
	if (prev_value == NULL)
		return NO_CHANGES;
505

506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
	ir_node *const prev_ptr = get_Load_ptr(prev_load);
	base_offset_t base_offset;
	get_base_and_offset(prev_ptr, &base_offset);
	ir_mode *const load_mode = get_Load_mode(load);
	ir_mode *const prev_mode = get_Load_mode(prev_load);
	ir_node *const block     = get_nodes_block(load);

	/* load value completely contained in previous load? */
	ir_node *const new_value
		= transform_previous_value(load_mode, &env->base_offset, prev_mode,
		                           &base_offset, prev_value, block);
	if (new_value == NULL)
		return NO_CHANGES;

	DBG_OPT_RAR(prev_load, load);
	return replace_load(load, new_value);
}

static bool try_update_ptr_CopyB(track_load_env_t *env, ir_node *copyb)
{
	ir_node *copyb_dst = get_CopyB_dst(copyb);
	base_offset_t dst_base_offset;
	get_base_and_offset(copyb_dst, &dst_base_offset);
	if (dst_base_offset.base != env->base_offset.base)
		return false;

	/* see if bytes loaded are fully contained in the CopyB */
	if (env->base_offset.offset < dst_base_offset.offset)
		return false;

	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);
	base_offset_t src_base_offset;
	get_base_and_offset(copyb_src, &src_base_offset);

	long     delta     = env->base_offset.offset - dst_base_offset.offset;
	ir_node *load      = env->load;
	ir_mode *load_mode = get_Load_mode(load);
	long     load_size = get_mode_size_bytes(load_mode);
	if (delta + load_size > n_copy)
		return false;

	/* track src input */
	env->base_offset.base   = src_base_offset.base;
	env->base_offset.offset = src_base_offset.offset + delta;
552
553
554
555
556

	/*
	 * Everything is OK, we can replace
	 *   ptr = (load_base_ptr + load_offset)
	 * with
557
	 *   new_load_ptr = (src_base_ptr + delta)
558
559
560
	 */
	ir_graph *irg          = get_irn_irg(load);
	ir_node  *block        = get_nodes_block(load);
561
	ir_mode  *mode_ref     = get_irn_mode(src_base_offset.base);
562
	ir_mode  *mode_ref_int = get_reference_mode_unsigned_eq(mode_ref);
563
564
565
566
567
	ir_node  *cnst         = new_r_Const_long(irg, mode_ref_int,
	                                          src_base_offset.offset + delta);
	ir_node  *new_load_ptr = new_r_Add(block, src_base_offset.base, cnst, mode_P);
	env->ptr = new_load_ptr;
	return true;
568
569
}

570
571
572
573
/**
 * 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
574
575
576
577
578
579
 * 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
 */
580
static changes_t follow_load_mem_chain(track_load_env_t *env, ir_node *start)
581
{
582
583
	ir_node *load      = env->load;
	ir_mode *load_mode = get_Load_mode(load);
584

585
586
587
588
	ir_node  *node = start;
	changes_t res  = NO_CHANGES;
	for (;;) {
		ldst_info_t *node_info = (ldst_info_t*)get_irn_link(node);
Michael Beck's avatar
Michael Beck committed
589

590
591
592
		if (is_Store(node)) {
			/* first try load-after-store */
			changes_t changes = try_load_after_store(env, node);
Matthias Braun's avatar
Matthias Braun committed
593
			if (changes != NO_CHANGES)
594
				return changes | res;
595

596
			/* check if we can pass through this store */
597
598
599
600
601
602
603
			const ir_node *ptr       = get_Store_ptr(node);
			const ir_node *value     = get_Store_value(node);
			const ir_mode *mode      = get_irn_mode(value);
			const ir_type *type      = get_type_for_mode(mode);
			const ir_type *load_type = get_type_for_mode(load_mode);
			ir_alias_relation rel = get_alias_relation(ptr, type, env->ptr,
			                                           load_type);
604
			/* if the might be an alias, we cannot pass this Store */
Michael Beck's avatar
Michael Beck committed
605
			if (rel != ir_no_alias)
606
				break;
607
608
609
610
611
612
613
614
615
616
617
			node = skip_Proj(get_Store_mem(node));
		} else if (is_Load(node)) {
			/* try load-after-load */
			changes_t changes = try_load_after_load(env, node);
			if (changes != NO_CHANGES)
				return changes | res;
			/* we can skip any load */
			node = skip_Proj(get_Load_mem(node));
		} else if (is_Call(node)) {
			/* there might be Store's in non-pure graph, stop here */
			if (!is_Call_pure(node))
618
				break;
619
620
621
622
			/* 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. */
			node = skip_Proj(get_Call_mem(node));
		} else if (is_CopyB(node)) {
623
624
625
626
627
628
629
630
			/*
			 * 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.
			 */
631
632
633
634
635
636
			bool updated = try_update_ptr_CopyB(env, node);
			if (updated) {
				/* Special case: If new_ptr points to
				 * a constant, we *can* replace the
				 * Load immediately.
				 */
637
				res |= NODES_CREATED;
638
639
640
				ir_node *new_value = predict_load(env->ptr, load_mode);
				if (new_value != NULL)
					return replace_load(load, new_value) | res;
641
642
			}

643
644
645
646
647
648
649
650
651
652
			/* check aliasing with the CopyB */
			ir_node *dst       = get_CopyB_dst(node);
			ir_type *type      = get_CopyB_type(node);
			ir_type *load_type = get_type_for_mode(load_mode);
			ir_alias_relation rel = get_alias_relation(dst, type, env->ptr,
			                                           load_type);
			/* possible alias => we cannot continue */
			if (rel != ir_no_alias)
				break;
			node = skip_Proj(get_CopyB_mem(node));
653
		} else {
654
655
			/* be conservative about any other node and assume aliasing
			 * that changes the loaded value */
656
657
658
659
			break;
		}

		/* check for cycles */
660
		if (NODE_VISITED(node_info))
661
			break;
662
		MARK_NODE(node_info);
663
664
	}

665
	if (is_Sync(node)) {
666
		/* handle all Sync predecessors */
667
668
669
670
		foreach_irn_in(node, i, in) {
			ir_node *skipped = skip_Proj(in);
			res |= follow_load_mem_chain(env, skipped);
			if ((res & ~NODES_CREATED) != NO_CHANGES)
Matthias Braun's avatar
Matthias Braun committed
671
				break;
672
673
674
		}
	}
	return res;
675
}
Michael Beck's avatar
Michael Beck committed
676

677
678
ir_node *can_replace_load_by_const(const ir_node *load, ir_node *c)
{
679
680
681
682
	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);
683
	ir_node  *res    = duplicate_subgraph(dbgi, c, block);
684
685
686
687
688

	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 */
689
			res = new_rd_Conv(dbgi, block, res, l_mode);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
690
691
		} else {
			return NULL;
692
693
694
		}
	}
	return res;
695
}
696

Michael Beck's avatar
Michael Beck committed
697
698
/**
 * optimize a Load
699
700
 *
 * @param load  the Load node
Michael Beck's avatar
Michael Beck committed
701
 */
Matthias Braun's avatar
Matthias Braun committed
702
static changes_t optimize_load(ir_node *load)
Michael Beck's avatar
Michael Beck committed
703
{
Matthias Braun's avatar
Matthias Braun committed
704
705
	const ldst_info_t *info = (ldst_info_t*)get_irn_link(load);
	changes_t          res  = NO_CHANGES;
706
707
708

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

	/* the address of the load to be optimized */
Andreas Fried's avatar
Andreas Fried committed
712
	ir_node *ptr = get_Load_ptr(load);
713
714

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

717
	if (info->projs[pn_Load_res] == NULL
718
719
	    && info->projs[pn_Load_X_except] == NULL) {
		assert(info->projs[pn_Load_X_regular] == NULL);
720
		/* the value is never used and we don't care about exceptions, remove */
721
		exchange(info->projs[pn_Load_M], mem);
722
		kill_and_reduce_usage(load);
723
724
725
		return res | DF_CHANGED;
	}

726
727
728
729
730
731
732
733
	track_load_env_t env;
	get_base_and_offset(ptr, &env.base_offset);
	env.ptr = ptr;

	/* Check, if the base address of this load is used more than once.
	 * If not, we won't find another store/load/CopyB anyway.
	 * TODO: can we miss values with multiple users in between? */
	if (get_irn_n_edges(ptr) <= 1 && get_irn_n_edges(env.base_offset.base) <= 1)
734
735
736
737
738
739
740
741
742
743
		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();
744
745
	env.load = load;
	res = follow_load_mem_chain(&env, skip_Proj(mem));
746
	return res;
747
}
Michael Beck's avatar
Michael Beck committed
748

749
750
751
752
/**
 * Check whether a value of mode new_mode would completely overwrite a value
 * of mode old_mode in memory.
 */
Matthias Braun's avatar
Matthias Braun committed
753
static bool is_completely_overwritten(ir_mode *old_mode, ir_mode *new_mode)
754
755
{
	return get_mode_size_bits(new_mode) >= get_mode_size_bits(old_mode);
756
}
757

758
759
760
/**
 * Check whether small is a part of large (starting at same address).
 */
Matthias Braun's avatar
Matthias Braun committed
761
static bool is_partially_same(ir_node *small, ir_node *large)
762
{
Matthias Braun's avatar
Matthias Braun committed
763
764
	const ir_mode *sm = get_irn_mode(small);
	const ir_mode *lm = get_irn_mode(large);
765
766
767
768
769

	/* 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
770
	    && get_mode_arithmetic(lm) == irma_twos_complement;
771
}
772

Michael Beck's avatar
Michael Beck committed
773
/**
Matthias Braun's avatar
Matthias Braun committed
774
775
 * follow the memory chain as long as there are only Loads and alias free
 * Stores.
Michael Beck's avatar
Michael Beck committed
776
777
 * INC_MASTER() must be called before dive into
 */
Matthias Braun's avatar
Matthias Braun committed
778
static changes_t follow_store_mem_chain(ir_node *store, ir_node *start,
779
                                        bool had_split)
780
{
Matthias Braun's avatar
Matthias Braun committed
781
782
783
784
785
786
	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);
Matthias Braun's avatar
Matthias Braun committed
787
	ir_type     *type  = get_type_for_mode(mode);
Matthias Braun's avatar
Matthias Braun committed
788
789
	ir_node     *block = get_nodes_block(store);

Matthias Braun's avatar
Matthias Braun committed
790
791
792
	ir_node *node = start;
	while (node != store) {
		ldst_info_t *node_info = (ldst_info_t*)get_irn_link(node);
793
794
795
796

		/*
		 * BEWARE: one might think that checking the modes is useless, because
		 * if the pointers are identical, they refer to the same object.
Matthias Braun's avatar
Matthias Braun committed
797
798
799
800
801
		 * This is only true in strong typed languages, not is C were the
		 * following is possible *(ir_type1 *)p = a; *(ir_type2 *)p = b ...
		 * 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 ...
802
		 */
Matthias Braun's avatar
Matthias Braun committed
803
804
		if (is_Store(node) && !had_split && get_Store_ptr(node) == ptr &&
		    get_nodes_block(node) == block) {
805
			/*
Matthias Braun's avatar
Matthias Braun committed
806
			 * a Store after a Store in the same Block -- a write after write.
807
808
809
810
811
812
			 */

			/*
			 * 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.
813
814
815
			 *
			 * TODO: What, if both have the same exception handler ???
			 */
Matthias Braun's avatar
Matthias Braun committed
816
817
818
			if (get_Store_volatility(node) != volatility_is_volatile
			    && !node_info->projs[pn_Store_X_except]) {
				ir_node *predvalue = get_Store_value(node);
819
820
				ir_mode *predmode  = get_irn_mode(predvalue);

821
				if (is_completely_overwritten(predmode, mode)
Matthias Braun's avatar
Matthias Braun committed
822
823
824
825
826
827
				    || is_partially_same(predvalue, value)) {
					DBG_OPT_WAW(node, store);
					DB((dbg, LEVEL_1, "  killing store %+F (override by %+F)\n",
					    node, store));
					exchange(node_info->projs[pn_Store_M], get_Store_mem(node));
					kill_and_reduce_usage(node);
828
829
830
831
832
833
834
835
836
837
838
839
					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]) {
Matthias Braun's avatar
Matthias Braun committed
840
				ir_node *predvalue = get_Store_value(node);
841

842
				if (is_partially_same(value, predvalue)) {
Matthias Braun's avatar
Matthias Braun committed
843
844
845
					DBG_OPT_WAW(node, store);
					DB((dbg, LEVEL_1, "  killing store %+F (override by %+F)\n",
					    node, store));
846
					exchange(info->projs[pn_Store_M], mem);
847
					kill_and_reduce_usage(store);
848
849
					return DF_CHANGED;
				}
850
			}
Matthias Braun's avatar
Matthias Braun committed
851
852
		} else if (is_Load(node) && get_Load_ptr(node) == ptr &&
		           value == node_info->projs[pn_Load_res]) {
853
			/*
854
855
856
857
			 * 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.
858
			 */
Matthias Braun's avatar
Matthias Braun committed
859
			if (!info->projs[pn_Store_X_except]) {
Matthias Braun's avatar
Matthias Braun committed
860
861
862
863
				DBG_OPT_WAR(store, node);
				DB((dbg, LEVEL_1,
				    "  killing store %+F (read %+F from same address)\n",
				    store, node));
864
				exchange(info->projs[pn_Store_M], mem);
865
				kill_and_reduce_usage(store);
866
867
868
869
				return DF_CHANGED;
			}
		}

Matthias Braun's avatar
Matthias Braun committed
870
		if (is_Store(node)) {
Michael Beck's avatar
Michael Beck committed
871
			/* check if we can pass through this store */
Matthias Braun's avatar
Matthias Braun committed
872
873
874
875
876
			ir_node *store_ptr   = get_Store_ptr(node);
			ir_node *store_value = get_Store_value(node);
			ir_type *store_type  = get_type_for_mode(get_irn_mode(store_value));
			ir_alias_relation rel
				= get_alias_relation(store_ptr, store_type, ptr, type);
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
				break;
Matthias Braun's avatar
Matthias Braun committed
880
881
882
883
884
885
			node = skip_Proj(get_Store_mem(node));
		} else if (is_Load(node)) {
			ir_node *load_ptr  = get_Load_ptr(node);
			ir_type *load_type = get_type_for_mode(get_Load_mode(node));
			ir_alias_relation rel
				= get_alias_relation(load_ptr, load_type, ptr, type);
Michael Beck's avatar
Michael Beck committed
886
			if (rel != ir_no_alias)
887
888
				break;

Matthias Braun's avatar
Matthias Braun committed
889
890
891
892
893
894
895
896
897
898
899
900
			node = skip_Proj(get_Load_mem(node));
		} else if (is_CopyB(node)) {
			ir_node *copyb_src  = get_CopyB_src(node);
			ir_type *copyb_type = get_CopyB_type(node);
			ir_alias_relation src_rel
				= get_alias_relation(copyb_src, copyb_type, ptr, type);
			if (src_rel != ir_no_alias)
				break;
			ir_node *copyb_dst = get_CopyB_dst(node);
			ir_alias_relation dst_rel
				= get_alias_relation(copyb_dst, copyb_type, ptr, type);
			if (dst_rel != ir_no_alias)
901
				break;
902
903
904
905
906
907
		} else {
			/* follow only Load chains */
			break;
		}

		/* check for cycles */
Matthias Braun's avatar
Matthias Braun committed
908
		if (NODE_VISITED(node_info))
909
			break;
Matthias Braun's avatar
Matthias Braun committed
910
		MARK_NODE(node_info);
911
912
	}

Matthias Braun's avatar
Matthias Braun committed
913
	if (is_Sync(node)) {
914
		/* handle all Sync predecessors */
Matthias Braun's avatar
Matthias Braun committed
915
916
917
918
		foreach_irn_in(node, i, in) {
			ir_node *skipped = skip_Proj(in);
			res |= follow_store_mem_chain(store, skipped, true);
			if (res != NO_CHANGES)
919
920
921
922
				break;
		}
	}
	return res;
923
}
Michael Beck's avatar
Michael Beck committed
924

925
926
static ir_entity *find_entity(ir_node *ptr)
{
927
	switch (get_irn_opcode(ptr)) {
928
929
930
931
932
	case iro_Address:
		return get_Address_entity(ptr);

	case iro_Offset:
		return get_Offset_entity(ptr);
933

934
935
936
937
938
939
940
941
942
943
944
945
	case iro_Sel: {
		ir_node *pred = get_Sel_ptr(ptr);
		if (get_irg_frame(get_irn_irg(ptr)) == pred)
			return get_Sel_entity(ptr);

		return find_entity(pred);
	}
	case iro_Sub:
	case iro_Add: {
		ir_node *left = get_binop_left(ptr);
		if (mode_is_reference(get_irn_mode(left)))
			return find_entity(left);
Matthias Braun's avatar
Matthias Braun committed
946
		ir_node *right = get_binop_right(ptr);
947
948
949
950
951
952
953
954
955
		if (mode_is_reference(get_irn_mode(right)))
			return find_entity(right);
		return NULL;
	}
	default:
		return NULL;
	}
}

Michael Beck's avatar
Michael Beck committed
956
957
/**
 * optimize a Store
958
959
 *
 * @param store  the Store node
Michael Beck's avatar
Michael Beck committed
960
 */
Matthias Braun's avatar
Matthias Braun committed
961
static changes_t optimize_store(ir_node *store)
962
{
963
	if (get_Store_volatility(store) == volatility_is_volatile)
Matthias Braun's avatar
Matthias Braun committed
964
		return NO_CHANGES;
965

966
967
	/* Check, if the address of this Store is used more than once.
	 * If not, this Store cannot be removed in any case. */
Matthias Braun's avatar
Matthias Braun committed
968
	ir_node *ptr = get_Store_ptr(store);
969
	if (get_irn_n_edges(ptr) <= 1)
Matthias Braun's avatar
Matthias Braun committed
970
		return NO_CHANGES;
971

972
	ir_node *mem = get_Store_mem(store);
Michael Beck's avatar
Michael Beck committed
973

974
975
	/* follow the memory chain as long as there are only Loads */
	INC_MASTER();
Michael Beck's avatar
Michael Beck committed
976

977
	return follow_store_mem_chain(store, skip_Proj(mem), false);
978
}
Michael Beck's avatar
Michael Beck committed
979

980
981
982
983
/**
 * Checks whether @c ptr of type @c ptr_type lies completely within an
 * object of type @c struct_type starting at @c struct_ptr;
 */
Matthias Braun's avatar
Matthias Braun committed
984
985
static bool ptr_is_in_struct(ir_node *ptr, ir_type *ptr_type,
                             ir_node *struct_ptr, ir_type *struct_type)
986
{
987
988
989
990
991
	base_offset_t base_offset;
	get_base_and_offset(ptr, &base_offset);
	long      ptr_offset    = base_offset.offset;
	base_offset_t struct_offset;
	get_base_and_offset(struct_ptr, &struct_offset);
992
993
994
	unsigned  ptr_size      = get_type_size_bytes(ptr_type);
	unsigned  struct_size   = get_type_size_bytes(struct_type);

995
996
997
	return base_offset.base == struct_offset.base &&
		ptr_offset >= struct_offset.offset &&
		ptr_offset + ptr_size <= struct_offset.offset + struct_size;
998
999
1000
}

/**
For faster browsing, not all history is shown. View entire blame