irmemory.c 38.1 KB
Newer Older
1
/*
Matthias Braun's avatar
Matthias Braun committed
2
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Matthias Braun's avatar
Matthias Braun committed
4
5
6
7
8
9
10
 */

/**
 * @file
 * @brief    Memory disambiguator
 * @author   Michael Beck
 * @date     27.12.2006
11
12
 */
#include <stdlib.h>
13
#include <stdbool.h>
14

15
#include "adt/pmap.h"
16
17
18
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irprog_t.h"
19
#include "irmemory_t.h"
20
21
22
23
24
25
#include "irmemory.h"
#include "irflag.h"
#include "hashptr.h"
#include "irflag.h"
#include "irouts.h"
#include "irgwalk.h"
Matthias Braun's avatar
Matthias Braun committed
26
#include "irprintf.h"
27
#include "debug.h"
28
#include "error.h"
29
#include "typerep.h"
30
#include "type_t.h"
31
32
33

/** The debug handle. */
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
34
DEBUG_ONLY(static firm_dbg_module_t *dbgcall = NULL;)
35
36
37
38

/** The source language specific language disambiguator function. */
static DISAMBIGUATOR_FUNC language_disambuigator = NULL;

39
40
41
/** The global memory disambiguator options. */
static unsigned global_mem_disamgig_opt = aa_opt_no_opt;

42
43
const char *get_ir_alias_relation_name(ir_alias_relation rel)
{
44
45
#define X(a) case a: return #a
	switch (rel) {
Michael Beck's avatar
Michael Beck committed
46
47
48
	X(ir_no_alias);
	X(ir_may_alias);
	X(ir_sure_alias);
49
50
	}
#undef X
Matthias Braun's avatar
Matthias Braun committed
51
	panic("UNKNOWN alias relation");
52
53
}

54
55
unsigned get_irg_memory_disambiguator_options(const ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
56
	unsigned opt = irg->mem_disambig_opt;
57
58
59
	if (opt & aa_opt_inherited)
		return global_mem_disamgig_opt;
	return opt;
60
}
61

62
63
void set_irg_memory_disambiguator_options(ir_graph *irg, unsigned options)
{
Michael Beck's avatar
Michael Beck committed
64
	irg->mem_disambig_opt = options & ~aa_opt_inherited;
65
}
66

67
68
void set_irp_memory_disambiguator_options(unsigned options)
{
69
	global_mem_disamgig_opt = options;
70
}
71

72
73
74
ir_storage_class_class_t get_base_sc(ir_storage_class_class_t x)
{
	return x & ~ir_sc_modifiers;
75
}
76

77
/**
78
79
80
81
82
83
 * Find the base address and entity of an Sel node.
 *
 * @param sel  the node
 * @param pEnt after return points to the base entity.
 *
 * @return the base address.
84
 */
85
86
static ir_node *find_base_adr(const ir_node *sel, ir_entity **pEnt)
{
87
88
89
90
91
92
	ir_node *ptr = get_Sel_ptr(sel);

	while (is_Sel(ptr)) {
		sel = ptr;
		ptr = get_Sel_ptr(sel);
	}
93
	*pEnt = get_Sel_entity(sel);
94
	return ptr;
95
}
96

97
/**
Michael Beck's avatar
Michael Beck committed
98
99
 * Check if a given Const node is greater or equal a given size.
 *
Michael Beck's avatar
Michael Beck committed
100
101
102
 * @param cns   a Const node
 * @param size  a integer size
 *
Michael Beck's avatar
Michael Beck committed
103
 * @return ir_no_alias if the Const is greater, ir_may_alias else
104
 */
105
106
static ir_alias_relation check_const(const ir_node *cns, int size)
{
Matthias Braun's avatar
Matthias Braun committed
107
	ir_tarval *tv = get_Const_tarval(cns);
Michael Beck's avatar
Michael Beck committed
108
109

	if (size == 0)
Michael Beck's avatar
Michael Beck committed
110
		return tarval_is_null(tv) ? ir_may_alias : ir_no_alias;
Matthias Braun's avatar
Matthias Braun committed
111
	ir_tarval *tv_size = new_tarval_from_long(size, get_tarval_mode(tv));
112
	return tarval_cmp(tv_size, tv) & (ir_relation_less_equal) ? ir_no_alias : ir_may_alias;
113
}
114

Michael Beck's avatar
Michael Beck committed
115
116
117
/**
 * Treat idx1 and idx2 as integer indexes and check if they differ always more than size.
 *
Michael Beck's avatar
Michael Beck committed
118
119
120
121
 * @param idx1  a node representing the first index
 * @param idx2  a node representing the second index
 * @param size  an integer size
 *
Michael Beck's avatar
Michael Beck committed
122
123
124
 * @return ir_sure_alias iff idx1 == idx2
 *         ir_no_alias iff they ALWAYS differ more than size
 *         ir_may_alias else
Michael Beck's avatar
Michael Beck committed
125
 */
Matthias Braun's avatar
Matthias Braun committed
126
127
static ir_alias_relation different_index(const ir_node *idx1,
                                         const ir_node *idx2, int size)
128
{
129
	if (idx1 == idx2)
Michael Beck's avatar
Michael Beck committed
130
		return ir_sure_alias;
131
132
	if (is_Const(idx1) && is_Const(idx2)) {
		/* both are const, we can compare them */
Matthias Braun's avatar
Matthias Braun committed
133
134
		ir_tarval *tv1 = get_Const_tarval(idx1);
		ir_tarval *tv2 = get_Const_tarval(idx2);
Michael Beck's avatar
Michael Beck committed
135
		if (size == 0)
Michael Beck's avatar
Michael Beck committed
136
			return tv1 == tv2 ? ir_sure_alias : ir_no_alias;
Michael Beck's avatar
Michael Beck committed
137

138
		/* arg, modes may be different */
Matthias Braun's avatar
Matthias Braun committed
139
140
		ir_mode *m1 = get_tarval_mode(tv1);
		ir_mode *m2 = get_tarval_mode(tv2);
141
142
143
144
145
146
147
148
		if (m1 != m2) {
			int size = get_mode_size_bits(m1) - get_mode_size_bits(m2);

			if (size < 0) {
				/* m1 is a small mode, cast up */
				m1 = mode_is_signed(m1) ? find_signed_mode(m2) : find_unsigned_mode(m2);
				if (m1 == NULL) {
					/* should NOT happen, but if it does we give up here */
Michael Beck's avatar
Michael Beck committed
149
					return ir_may_alias;
150
151
152
153
154
155
156
				}
				tv1 = tarval_convert_to(tv1, m1);
			} else if (size > 0) {
				/* m2 is a small mode, cast up */
				m2 = mode_is_signed(m2) ? find_signed_mode(m1) : find_unsigned_mode(m1);
				if (m2 == NULL) {
					/* should NOT happen, but if it does we give up here */
Michael Beck's avatar
Michael Beck committed
157
					return ir_may_alias;
158
159
160
161
162
163
164
				}
				tv2 = tarval_convert_to(tv2, m2);
			}
			/* here the size should be identical, check for signed */
			if (get_mode_sign(m1) != get_mode_sign(m2)) {
				/* find the signed */
				if (mode_is_signed(m2)) {
Matthias Braun's avatar
Matthias Braun committed
165
					ir_tarval *t = tv1;
Matthias Braun's avatar
Matthias Braun committed
166
167
					tv1 = tv2;
					tv2 = t;
168
					ir_mode *tm = m1;
Matthias Braun's avatar
Matthias Braun committed
169
170
					m1 = m2;
					m2 = tm;
171
172
173
				}

				/* m1 is now the signed one */
174
				if (!tarval_is_negative(tv1)) {
175
176
177
					/* tv1 is signed, but >= 0, simply cast into unsigned */
					tv1 = tarval_convert_to(tv1, m2);
				} else {
Matthias Braun's avatar
Matthias Braun committed
178
					ir_tarval *tv_size = new_tarval_from_long(size, m2);
179
					if (tarval_cmp(tv2, tv_size) & (ir_relation_greater_equal)) {
180
						/* tv1 is negative and tv2 >= tv_size, so the difference is bigger than size */
Michael Beck's avatar
Michael Beck committed
181
						return ir_no_alias;
182
183
					}
					/* tv_size > tv2, so we can subtract without overflow */
184
					tv2 = tarval_sub(tv_size, tv2, NULL);
185
186
187
188
189
190
191
192

					/* tv1 is < 0, so we can negate it */
					tv1 = tarval_neg(tv1);

					/* cast it into unsigned. for two-complement it does the right thing for MIN_INT */
					tv1 = tarval_convert_to(tv1, m2);

					/* now we can compare without overflow */
193
					return tarval_cmp(tv1, tv2) & (ir_relation_greater_equal) ? ir_no_alias : ir_may_alias;
194
195
196
				}
			}
		}
197
		if (tarval_cmp(tv1, tv2) == ir_relation_greater) {
Matthias Braun's avatar
Matthias Braun committed
198
			ir_tarval *t = tv1;
Michael Beck's avatar
Michael Beck committed
199
200
201
202
			tv1 = tv2;
			tv2 = t;
		}
		/* tv1 is now the "smaller" one */
Matthias Braun's avatar
Matthias Braun committed
203
204
		ir_tarval *tv      = tarval_sub(tv2, tv1, NULL);
		ir_tarval *tv_size = new_tarval_from_long(size, get_tarval_mode(tv));
205
		return tarval_cmp(tv_size, tv) & (ir_relation_less_equal) ? ir_no_alias : ir_may_alias;
206
207
208
209
210
211
212
213
214
	}

	/* Note: we rely here on the fact that normalization puts constants on the RIGHT side */
	if (is_Add(idx1)) {
		ir_node *l1 = get_Add_left(idx1);
		ir_node *r1 = get_Add_right(idx1);

		if (l1 == idx2) {
			/* x + c == y */
Michael Beck's avatar
Michael Beck committed
215
216
			if (is_Const(r1))
				return check_const(r1, size);
217
218
		}
		if (is_Add(idx2)) {
219
			/* both are Adds, check if they are of x + a == x + b kind */
220
221
222
223
			ir_node *l2 = get_Add_left(idx2);
			ir_node *r2 = get_Add_right(idx2);

			if (l1 == l2)
Michael Beck's avatar
Michael Beck committed
224
				return different_index(r1, r2, size);
225
			else if (l1 == r2)
Michael Beck's avatar
Michael Beck committed
226
				return different_index(r1, l2, size);
227
			else if (r1 == r2)
Michael Beck's avatar
Michael Beck committed
228
				return different_index(l1, l2, size);
229
			else if (r1 == l2)
Michael Beck's avatar
Michael Beck committed
230
				return different_index(l1, r2, size);
231
232
233
234
235
236
237
238
		}
	}
	if (is_Add(idx2)) {
		ir_node *l2 = get_Add_left(idx2);
		ir_node *r2 = get_Add_right(idx2);

		if (l2 == idx1) {
			/* x + c == y */
Michael Beck's avatar
Michael Beck committed
239
240
			if (is_Const(r2))
				return check_const(r2, size);
241
242
243
244
245
246
247
248
249
		}
	}

	if (is_Sub(idx1)) {
		ir_node *l1 = get_Sub_left(idx1);
		ir_node *r1 = get_Sub_right(idx1);

		if (l1 == idx2) {
			/* x - c == y */
Michael Beck's avatar
Michael Beck committed
250
251
			if (is_Const(r1))
				return check_const(r1, size);
252
253
254
		}

		if (is_Sub(idx2)) {
255
			/* both are Subs, check if they are of x - a == x - b kind */
256
257
258
259
			ir_node *l2 = get_Sub_left(idx2);

			if (l1 == l2) {
				ir_node *r2 = get_Sub_right(idx2);
Michael Beck's avatar
Michael Beck committed
260
				return different_index(r1, r2, size);
261
262
263
264
265
266
267
268
269
			}
		}
	}
	if (is_Sub(idx2)) {
		ir_node *l2 = get_Sub_left(idx2);
		ir_node *r2 = get_Sub_right(idx2);

		if (l2 == idx1) {
			/* x - c == y */
Michael Beck's avatar
Michael Beck committed
270
271
			if (is_Const(r2))
				return check_const(r2, size);
272
273
274
		}

	}
Michael Beck's avatar
Michael Beck committed
275
	return ir_may_alias;
276
}
277
278

/**
279
 * Two Sel addresses have the same base address, check if their offsets are
280
 * different.
281
282
283
284
 *
 * @param adr1  The first address.
 * @param adr2  The second address.
 */
Matthias Braun's avatar
Matthias Braun committed
285
286
static ir_alias_relation different_sel_offsets(const ir_node *sel1,
                                               const ir_node *sel2)
287
{
Matthias Braun's avatar
Matthias Braun committed
288
	/* TODO: fix */
289
290
	(void) sel1;
	(void) sel2;
291
#if 0
292
293
294
295
296
297
298
299
300
301
302
303
304
	ir_entity *ent1 = get_Sel_entity(sel1);
	ir_entity *ent2 = get_Sel_entity(sel2);
	int i, check_arr = 0;

	if (ent1 == ent2)
		check_arr = 1;
	else {
		ir_type *tp1 = get_entity_type(ent1);
		ir_type *tp2 = get_entity_type(ent2);

		if (tp1 == tp2)
			check_arr = 1;
		else if (get_type_state(tp1) == layout_fixed && get_type_state(tp2) == layout_fixed &&
305
		         get_type_size_bytes(tp1) == get_type_size_bytes(tp2))
306
307
308
309
310
311
312
313
314
315
316
317
			check_arr = 1;
	}
	if (check_arr) {
		/* we select an entity of same size, check for indexes */
		int n = get_Sel_n_indexs(sel1);
		int have_no = 0;

		if (n > 0 && n == get_Sel_n_indexs(sel2)) {
			/* same non-zero number of indexes, an array access, check */
			for (i = 0; i < n; ++i) {
				ir_node *idx1 = get_Sel_index(sel1, i);
				ir_node *idx2 = get_Sel_index(sel2, i);
Michael Beck's avatar
Michael Beck committed
318
				ir_alias_relation res = different_index(idx1, idx2, 0); /* we can safely IGNORE the size here if it's at least >0 */
319
320
321
322
323
324
325
326
327
328

				if (res == may_alias)
					return may_alias;
				else if (res == no_alias)
					have_no = 1;
			}
			/* if we have at least one no_alias, there is no alias relation, else we have sure */
			return have_no > 0 ? no_alias : sure_alias;
		}
	}
Matthias Braun's avatar
Matthias Braun committed
329
330
#else
	(void) different_index;
331
#endif
Michael Beck's avatar
Michael Beck committed
332
	return ir_may_alias;
333
}
334

335
336
337
/**
 * Determine the alias relation by checking if adr1 and adr2 are pointer
 * to different type.
338
339
340
 *
 * @param adr1    The first address.
 * @param adr2    The second address.
341
 */
Matthias Braun's avatar
Matthias Braun committed
342
343
static ir_alias_relation different_types(const ir_node *adr1,
                                         const ir_node *adr2)
344
{
Matthias Braun's avatar
Matthias Braun committed
345
346
	ir_entity *ent1 = NULL;
	ir_entity *ent2 = NULL;
347

348
349
	if (is_SymConst_addr_ent(adr1))
		ent1 = get_SymConst_entity(adr1);
350
351
352
	else if (is_Sel(adr1))
		ent1 = get_Sel_entity(adr1);

353
354
	if (is_SymConst_addr_ent(adr2))
		ent2 = get_SymConst_entity(adr2);
355
356
357
358
359
360
361
362
	else if (is_Sel(adr2))
		ent2 = get_Sel_entity(adr2);

	if (ent1 != NULL && ent2 != NULL) {
		ir_type *tp1 = get_entity_type(ent1);
		ir_type *tp2 = get_entity_type(ent2);

		if (tp1 != tp2) {
Michael Beck's avatar
Michael Beck committed
363
364
365
366
			/* do deref until no pointer types are found */
			while (is_Pointer_type(tp1) && is_Pointer_type(tp2)) {
				tp1 = get_pointer_points_to_type(tp1);
				tp2 = get_pointer_points_to_type(tp2);
367
368
369
370
			}

			if (get_type_tpop(tp1) != get_type_tpop(tp2)) {
				/* different type structure */
Michael Beck's avatar
Michael Beck committed
371
				return ir_no_alias;
372
373
374
			}
			if (is_Class_type(tp1)) {
				/* check class hierarchy */
Matthias Braun's avatar
Matthias Braun committed
375
				if (!is_SubClass_of(tp1, tp2) && !is_SubClass_of(tp2, tp1))
Michael Beck's avatar
Michael Beck committed
376
					return ir_no_alias;
377
378
			} else {
				/* different types */
Michael Beck's avatar
Michael Beck committed
379
				return ir_no_alias;
380
381
382
			}
		}
	}
Michael Beck's avatar
Michael Beck committed
383
	return ir_may_alias;
384
}
385

386
387
388
389
390
/**
 * Returns non-zero if a node is a result on a malloc-like routine.
 *
 * @param node  the Proj node to test
 */
391
392
static int is_malloc_Result(const ir_node *node)
{
393
	node = get_Proj_pred(node);
Matthias Braun's avatar
Matthias Braun committed
394
	if (!is_Proj(node))
395
396
		return 0;
	node = get_Proj_pred(node);
Matthias Braun's avatar
Matthias Braun committed
397
	if (!is_Call(node))
398
		return 0;
399
400
401
402
	ir_entity *callee = get_Call_callee(node);
	if (callee != NULL
	    && get_entity_additional_properties(callee) & mtp_property_malloc)
		return 1;
403
	return 0;
404
}
405

406
407
ir_storage_class_class_t classify_pointer(const ir_node *irn,
                                          const ir_entity *ent)
408
{
Matthias Braun's avatar
Matthias Braun committed
409
	ir_graph                *irg = get_irn_irg(irn);
Michael Beck's avatar
Michael Beck committed
410
	ir_storage_class_class_t res = ir_sc_pointer;
411
412
	if (is_SymConst_addr_ent(irn)) {
		ir_entity *entity = get_SymConst_entity(irn);
413
414
		ir_type   *owner  = get_entity_owner(entity);
		res = owner == get_tls_type() ? ir_sc_tls : ir_sc_globalvar;
Matthias Braun's avatar
Matthias Braun committed
415
		if (!(get_entity_usage(entity) & ir_usage_address_taken))
Michael Beck's avatar
Michael Beck committed
416
			res |= ir_sc_modifier_nottaken;
Michael Beck's avatar
Fixed:    
Michael Beck committed
417
	} else if (irn == get_irg_frame(irg)) {
Michael Beck's avatar
Michael Beck committed
418
		res = ir_sc_localvar;
419
		if (ent != NULL && !(get_entity_usage(ent) & ir_usage_address_taken))
Michael Beck's avatar
Michael Beck committed
420
			res |= ir_sc_modifier_nottaken;
421
	} else if (is_Proj(irn) && is_malloc_Result(irn)) {
Michael Beck's avatar
Michael Beck committed
422
		return ir_sc_malloced;
423
424
	} else if (is_Const(irn)) {
		return ir_sc_globaladdr;
425
426
	} else if (is_arg_Proj(irn)) {
		res |= ir_sc_modifier_argument;
427
428
	}

Michael Beck's avatar
Fixed:    
Michael Beck committed
429
	return res;
430
431
}

432
433
/**
 * Determine the alias relation between two addresses.
Michael Beck's avatar
Michael Beck committed
434
435
 *
 * @param addr1  pointer address of the first memory operation
436
 * @param type1  the type of the accessed data through addr1
Michael Beck's avatar
Michael Beck committed
437
 * @param addr2  pointer address of the second memory operation
438
 * @param type2  the type of the accessed data through addr2
Michael Beck's avatar
Michael Beck committed
439
 *
Michael Beck's avatar
Michael Beck committed
440
 * @return found memory relation
441
442
 */
static ir_alias_relation _get_alias_relation(
443
444
	const ir_node *adr1, const ir_type *const type1,
	const ir_node *adr2, const ir_type *const type2)
445
{
446

Matthias Braun's avatar
Matthias Braun committed
447
	if (!get_opt_alias_analysis())
Michael Beck's avatar
Michael Beck committed
448
		return ir_may_alias;
449
450

	if (adr1 == adr2)
Michael Beck's avatar
Michael Beck committed
451
		return ir_sure_alias;
452

Matthias Braun's avatar
Matthias Braun committed
453
454
	ir_graph *const irg     = get_irn_irg(adr1);
	unsigned  const options = get_irg_memory_disambiguator_options(irg);
455
456
457

	/* The Armageddon switch */
	if (options & aa_opt_no_alias)
Michael Beck's avatar
Michael Beck committed
458
		return ir_no_alias;
459

Andreas Fried's avatar
Andreas Fried committed
460
	/* do the addresses have constants offsets from the same base?
461
	 *  Note: sub X, C is normalized to add X, -C
Michael Beck's avatar
Fixed:    
Michael Beck committed
462
	 */
Matthias Braun's avatar
Matthias Braun committed
463
464
	long           offset1            = 0;
	long           offset2            = 0;
Andreas Fried's avatar
Andreas Fried committed
465
466
	const ir_node *sym_offset1        = NULL;
	const ir_node *sym_offset2        = NULL;
Matthias Braun's avatar
Matthias Braun committed
467
468
469
	const ir_node *orig_adr1          = adr1;
	const ir_node *orig_adr2          = adr2;
	bool           have_const_offsets = true;
Andreas Fried's avatar
Andreas Fried committed
470
471
472
473
474
475
476

	/*
	 * Currently, only expressions with at most one symbolic
	 * offset can be handled.  To extend this, change
	 * sym_offset{1,2} to be sets, and compare the sets.
	 */

477
	while (is_Add(adr1)) {
Andreas Fried's avatar
Andreas Fried committed
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
		ir_node *ptr_node;
		ir_node *int_node;

		ir_mode *mode_left = get_irn_mode(get_Add_left(adr1));

		if (mode_is_reference(mode_left)) {
			ptr_node = get_Add_left(adr1);
			int_node = get_Add_right(adr1);
		} else {
			ptr_node = get_Add_right(adr1);
			int_node = get_Add_left(adr1);
		}

		if (is_Const(int_node)) {
			ir_tarval *tv  = get_Const_tarval(int_node);
			offset1       += get_tarval_long(tv);
		} else if (sym_offset1 == NULL) {
			sym_offset1 = int_node;
Michael Beck's avatar
Fixed:    
Michael Beck committed
496
		} else {
Andreas Fried's avatar
Andreas Fried committed
497
498
			// adr1 has more than one symbolic offset.
			// Give up
Matthias Braun's avatar
Matthias Braun committed
499
			have_const_offsets = false;
500
		}
Andreas Fried's avatar
Andreas Fried committed
501
502

		adr1 = ptr_node;
503
	}
Andreas Fried's avatar
Andreas Fried committed
504

505
	while (is_Add(adr2)) {
Andreas Fried's avatar
Andreas Fried committed
506
507
508
509
510
511
512
513
		ir_node *ptr_node;
		ir_node *int_node;

		ir_mode *mode_left = get_irn_mode(get_Add_left(adr2));

		if (mode_is_reference(mode_left)) {
			ptr_node = get_Add_left(adr2);
			int_node = get_Add_right(adr2);
Michael Beck's avatar
Fixed:    
Michael Beck committed
514
		} else {
Andreas Fried's avatar
Andreas Fried committed
515
516
517
518
519
520
521
522
523
524
525
526
			ptr_node = get_Add_right(adr2);
			int_node = get_Add_left(adr2);
		}

		if (is_Const(int_node)) {
			ir_tarval *tv  = get_Const_tarval(int_node);
			offset2       += get_tarval_long(tv);
		} else if (sym_offset2 == NULL) {
			sym_offset2 = int_node;
		} else {
			// adr2 has more than one symbolic offset.
			// Give up
Matthias Braun's avatar
Matthias Braun committed
527
			have_const_offsets = false;
528
		}
Andreas Fried's avatar
Andreas Fried committed
529
530

		adr2 = ptr_node;
531
532
	}

533
534
535
	unsigned type_size = get_type_size_bytes(type1);
	if (get_type_size_bytes(type2) > type_size) {
		type_size = get_type_size_bytes(type2);
536
	}
537

Michael Beck's avatar
Fixed:    
Michael Beck committed
538
539
540
	/* same base address -> compare offsets if possible.
	 * FIXME: type long is not sufficient for this task ...
	 */
Andreas Fried's avatar
Andreas Fried committed
541
	if (adr1 == adr2 && sym_offset1 == sym_offset2 && have_const_offsets) {
542
543
544
545
546
547
548
549
550
551
552
553
554
555
		unsigned long first_offset, last_offset;
		unsigned first_type_size;

		if (offset1 <= offset2) {
			first_offset = offset1;
			last_offset = offset2;
			first_type_size = get_type_size_bytes(type1);
		} else {
			first_offset = offset2;
			last_offset = offset1;
			first_type_size = get_type_size_bytes(type2);
		}

		if (first_offset + first_type_size <= last_offset)
Michael Beck's avatar
Michael Beck committed
556
			return ir_no_alias;
557
		else
Michael Beck's avatar
Michael Beck committed
558
			return ir_sure_alias;
559
	}
560

Michael Beck's avatar
Michael Beck committed
561
	/* skip Sels */
Matthias Braun's avatar
Matthias Braun committed
562
563
564
565
	const ir_node *base1 = adr1;
	const ir_node *base2 = adr2;
	ir_entity *ent1  = NULL;
	ir_entity *ent2  = NULL;
566
	if (is_Sel(adr1)) {
Michael Beck's avatar
Fixed:    
Michael Beck committed
567
		base1 = find_base_adr(adr1, &ent1);
568
569
	}
	if (is_Sel(adr2)) {
Michael Beck's avatar
Fixed:    
Michael Beck committed
570
		base2 = find_base_adr(adr2, &ent2);
571
	}
572

Michael Beck's avatar
Michael Beck committed
573
	/* same base address -> compare Sel entities */
Michael Beck's avatar
Fixed:    
Michael Beck committed
574
	if (base1 == base2 && ent1 != NULL && ent2 != NULL) {
575
576
577
578
579
580
581
582
583
584
585
586
		if (ent1 != ent2) {
			long offset1 = get_entity_offset(ent1);
			long offset2 = get_entity_offset(ent2);
			long size1   = get_type_size_bytes(type1);
			long size2   = get_type_size_bytes(type2);

			if (offset1 + size1 <= offset2 || offset2 + size2 <= offset1) {
				return ir_no_alias;
			}

			return ir_may_alias;
		} else if (have_const_offsets)
Michael Beck's avatar
Fixed:    
Michael Beck committed
587
			return different_sel_offsets(adr1, adr2);
588
	}
589

Matthias Braun's avatar
Matthias Braun committed
590
591
592
593
	ir_storage_class_class_t mod1   = classify_pointer(base1, ent1);
	ir_storage_class_class_t mod2   = classify_pointer(base2, ent2);
	ir_storage_class_class_t class1 = get_base_sc(mod1);
	ir_storage_class_class_t class2 = get_base_sc(mod2);
Michael Beck's avatar
Michael Beck committed
594

595
596
597
598
599
600
601
602
603
604
	/* struct-access cannot alias with variables */
	if (ent1 == NULL && ent2 != NULL && is_compound_type(get_entity_owner(ent2))
		&& (class1 == ir_sc_globalvar || class1 == ir_sc_localvar || class1 == ir_sc_tls || class1 == ir_sc_globaladdr)) {
		return ir_no_alias;
	}
	if (ent2 == NULL && ent1 != NULL && is_compound_type(get_entity_owner(ent1))
		&& (class2 == ir_sc_globalvar || class2 == ir_sc_localvar || class2 == ir_sc_tls || class2 == ir_sc_globaladdr)) {
		return ir_no_alias;
	}

605
606
607
608
609
610
	if (class1 == ir_sc_pointer || class2 == ir_sc_pointer) {
		/* swap pointer class to class1 */
		if (class2 == ir_sc_pointer) {
			ir_storage_class_class_t temp = mod1;
			mod1 = mod2;
			mod2 = temp;
611
612
			class1 = get_base_sc(mod1);
			class2 = get_base_sc(mod2);
Michael Beck's avatar
Michael Beck committed
613
		}
614
615
		/* a pointer and an object whose address was never taken */
		if (mod2 & ir_sc_modifier_nottaken) {
Michael Beck's avatar
Michael Beck committed
616
617
			return ir_no_alias;
		}
618
619
620
		if (mod1 & ir_sc_modifier_argument) {
			if ( (options & aa_opt_no_alias_args)
					&& (mod2 & ir_sc_modifier_argument))
621
				return ir_no_alias;
622
623
624
625
			if ( (options & aa_opt_no_alias_args_global)
					&& (class2 == ir_sc_globalvar
						|| class2 == ir_sc_tls
						|| class2 == ir_sc_globaladdr))
626
627
				return ir_no_alias;
		}
Michael Beck's avatar
Michael Beck committed
628
629
630
631
632
633
634
635
636
637
638
639
640
	} else if (class1 != class2) {
		/* two objects from different memory spaces */
		return ir_no_alias;
	} else {
		/* both classes are equal */
		if (class1 == ir_sc_globalvar) {
			ir_entity *entity1 = get_SymConst_entity(base1);
			ir_entity *entity2 = get_SymConst_entity(base2);
			if (entity1 != entity2)
				return ir_no_alias;

			/* for some reason CSE didn't happen yet for the 2 SymConsts... */
			return ir_may_alias;
641
		} else if (class1 == ir_sc_globaladdr) {
Matthias Braun's avatar
Matthias Braun committed
642
643
644
645
			ir_tarval *tv = get_Const_tarval(base1);
			offset1      += get_tarval_long(tv);
			tv            = get_Const_tarval(base2);
			offset2      += get_tarval_long(tv);
646

647
			if ((unsigned long)labs(offset2 - offset1) >= type_size)
648
649
650
				return ir_no_alias;
			else
				return ir_sure_alias;
Michael Beck's avatar
Michael Beck committed
651
652
653
654
		}
	}

	/* Type based alias analysis */
655
656
657
658
	if (options & aa_opt_type_based) {
		ir_alias_relation rel;

		if (options & aa_opt_byte_type_may_alias) {
659
660
			if (get_type_size_bytes(type1) == 1 || get_type_size_bytes(type2) == 1) {
				/* One of the types address a byte. Assume a ir_may_alias and leave
661
662
663
664
665
				   the type based check. */
				goto leave_type_based_alias;
			}
		}

666
667
		/* cheap check: If the type sizes did not match, the types MUST be different */
		if (get_type_size_bytes(type1) != get_type_size_bytes(type2))
668
669
			return ir_no_alias;

670
671
		/* cheap test: if only one is a reference type, no alias */
		if (is_Pointer_type(type1) != is_Pointer_type(type2))
Michael Beck's avatar
Michael Beck committed
672
673
			return ir_no_alias;

674
675
676
677
678
679
680
681
682
683
		if (is_Primitive_type(type1) && is_Primitive_type(type2)) {
			const ir_mode *const mode1 = get_type_mode(type1);
			const ir_mode *const mode2 = get_type_mode(type2);

			/* cheap test: if arithmetic is different, no alias */
			if (get_mode_arithmetic(mode1) != get_mode_arithmetic(mode2))
				return ir_no_alias;

		}

684
685
686
687
688
689
690
		/* try rule R5 */
		rel = different_types(orig_adr1, orig_adr2);
		if (rel != ir_may_alias)
			return rel;
leave_type_based_alias:;
	}

691
	/* do we have a language specific memory disambiguator? */
692
	if (language_disambuigator != NULL) {
693
		ir_alias_relation rel = language_disambuigator(orig_adr1, type1, orig_adr2, type2);
Michael Beck's avatar
Michael Beck committed
694
		if (rel != ir_may_alias)
695
696
697
698
			return rel;
	}

	/* access points-to information here */
Michael Beck's avatar
Michael Beck committed
699
	return ir_may_alias;
700
}
701
702

ir_alias_relation get_alias_relation(
703
704
	const ir_node *const adr1, const ir_type *const type1,
	const ir_node *const adr2, const ir_type *const type2)
705
{
706
	ir_alias_relation rel = _get_alias_relation(adr1, type1, adr2, type2);
707
	DB((dbg, LEVEL_1, "alias(%+F, %+F) = %s\n", adr1, adr2, get_ir_alias_relation_name(rel)));
708
	return rel;
709
}
710

711
712
void set_language_memory_disambiguator(DISAMBIGUATOR_FUNC func)
{
713
	language_disambuigator = func;
714
}
715
716
717
718
719
720

/** The result cache for the memory disambiguator. */
static set *result_cache = NULL;

/** An entry in the relation cache. */
typedef struct mem_disambig_entry {
721
	const ir_node     *adr1;    /**< The first address. */
722
	const ir_type     *type1;   /**< The first address type. */
723
	const ir_node     *adr2;    /**< The second address. */
724
	const ir_type     *type2;   /**< The second address type. */
725
726
727
	ir_alias_relation result;   /**< The alias relation result. */
} mem_disambig_entry;

728
#define HASH_ENTRY(adr1, adr2)  (hash_ptr(adr1) ^ hash_ptr(adr2))
729
730
731
732

/**
 * Compare two relation cache entries.
 */
733
734
static int cmp_mem_disambig_entry(const void *elt, const void *key, size_t size)
{
Matthias Braun's avatar
Matthias Braun committed
735
	(void) size;
736
737
	const mem_disambig_entry *p1 = (const mem_disambig_entry*) elt;
	const mem_disambig_entry *p2 = (const mem_disambig_entry*) key;
Michael Beck's avatar
Michael Beck committed
738
	return p1->adr1 == p2->adr1 && p1->adr2 == p2->adr2 &&
739
	       p1->type1 == p2->type1 && p1->type2 == p2->type2;
740
}
741

742
743
void mem_disambig_init(void)
{
744
	result_cache = new_set(cmp_mem_disambig_entry, 8);
745
}
746
747

ir_alias_relation get_alias_relation_ex(
748
749
	const ir_node *adr1, const ir_type *type1,
	const ir_node *adr2, const ir_type *type2)
750
{
751
752
	ir_fprintf(stderr, "%+F <-> %+F\n", adr1, adr2);

Matthias Braun's avatar
Matthias Braun committed
753
	if (!get_opt_alias_analysis())
Michael Beck's avatar
Michael Beck committed
754
		return ir_may_alias;
755
756

	if (get_irn_opcode(adr1) > get_irn_opcode(adr2)) {
Michael Beck's avatar
Michael Beck committed
757
		const ir_node *t = adr1;
758
759
760
761
		adr1 = adr2;
		adr2 = t;
	}

Matthias Braun's avatar
Matthias Braun committed
762
	mem_disambig_entry key;
Michael Beck's avatar
Michael Beck committed
763
764
	key.adr1  = adr1;
	key.adr2  = adr2;
765
766
	key.type1 = type1;
	key.type2 = type2;
Matthias Braun's avatar
Matthias Braun committed
767
	mem_disambig_entry *entry = set_find(mem_disambig_entry, result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
768
	if (entry != NULL)
769
770
		return entry->result;

771
	key.result = get_alias_relation(adr1, type1, adr2, type2);
772

yb9976's avatar
yb9976 committed
773
	(void)set_insert(mem_disambig_entry, result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
774
	return key.result;
775
}
776

777
778
void mem_disambig_term(void)
{
779
	if (result_cache != NULL) {
780
781
782
		del_set(result_cache);
		result_cache = NULL;
	}
783
}
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803

/**
 * Check the mode of a Load/Store with the mode of the entity
 * that is accessed.
 * If the mode of the entity and the Load/Store mode do not match, we
 * have the bad reinterpret case:
 *
 * int i;
 * char b = *(char *)&i;
 *
 * We do NOT count this as one value and return address_taken
 * in that case.
 * However, we support an often used case. If the mode is two-complement
 * we allow casts between signed/unsigned.
 *
 * @param mode     the mode of the Load/Store
 * @param ent_mode the mode of the accessed entity
 *
 * @return non-zero if the Load/Store is a hidden cast, zero else
 */
804
805
static int is_hidden_cast(const ir_mode *mode, const ir_mode *ent_mode)
{
806
807
808
	if (ent_mode == NULL)
		return false;

Matthias Braun's avatar
Matthias Braun committed
809
810
811
812
813
	if (ent_mode != mode &&
		(get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
		 get_mode_arithmetic(ent_mode) != irma_twos_complement ||
		 get_mode_arithmetic(mode) != irma_twos_complement)) {
		return true;
814
	}
815
	return false;
816
}
817
818

/**
Christoph Mallon's avatar
Christoph Mallon committed
819
 * Determine the usage state of a node (or its successor Sels).
820
821
822
 *
 * @param irn  the node
 */
Matthias Braun's avatar
Matthias Braun committed
823
824
static ir_entity_usage determine_entity_usage(const ir_node *irn,
                                              ir_entity *entity)
825
{
Matthias Braun's avatar
Matthias Braun committed
826
827
	unsigned res = 0;
	for (int i = get_irn_n_outs(irn); i-- > 0; ) {
828
829
830
831
		ir_node *succ = get_irn_out(irn, i);

		switch (get_irn_opcode(succ)) {
		case iro_Load:
832
833
			/* beware: irn might be a Id node here, so irn might be not
			   equal to get_Load_ptr(succ) */
834
835
			res |= ir_usage_read;

836
			/* check if this load is not a hidden conversion */
Matthias Braun's avatar
Matthias Braun committed
837
838
			ir_mode *mode  = get_Load_mode(succ);
			ir_mode *emode = get_type_mode(get_entity_type(entity));
839
			if (is_hidden_cast(mode, emode))
840
				res |= ir_usage_reinterpret_cast;
841
842
843
844
			break;

		case iro_Store:
			/* check that the node is not the Store's value */
845
846
847
848
849
850
851
			if (irn == get_Store_value(succ)) {
				res |= ir_usage_unknown;
			}
			if (irn == get_Store_ptr(succ)) {
				res |= ir_usage_write;

				/* check if this Store is not a hidden conversion */
Matthias Braun's avatar
Matthias Braun committed
852
853
854
				ir_node *value = get_Store_value(succ);
				ir_mode *mode  = get_irn_mode(value);
				ir_mode *emode = get_type_mode(get_entity_type(entity));
855
856
857
858
				if (is_hidden_cast(mode, emode))
					res |= ir_usage_reinterpret_cast;
			}
			assert(irn != get_Store_mem(succ));
859
860
			break;

Matthias Braun's avatar
Matthias Braun committed
861
		case iro_CopyB: {
862
			/* CopyB are like Loads/Stores */
Matthias Braun's avatar
Matthias Braun committed
863
			ir_type *tp  = get_entity_type(entity);
864
865
			if (tp != get_CopyB_type(succ)) {
				/* bad, different types, might be a hidden conversion */
866
867
868
869
870
871
872
				res |= ir_usage_reinterpret_cast;
			}
			if (irn == get_CopyB_dst(succ)) {
				res |= ir_usage_write;
			} else {
				assert(irn == get_CopyB_src(succ));
				res |= ir_usage_read;
873
874
			}
			break;
Matthias Braun's avatar
Matthias Braun committed
875
		}
876

877
878
		case iro_Add:
		case iro_Sub:
879
880
881
			/* Check the successor of irn. */
			res |= determine_entity_usage(succ, entity);
			break;
882
		case iro_Sel: {
883
			ir_entity *sel_entity = get_Sel_entity(succ);
Michael Beck's avatar
Michael Beck committed
884
			/* this analysis can't handle unions correctly */
885
			if (is_Union_type(get_entity_owner(sel_entity))) {
Matthias Braun's avatar
fix    
Matthias Braun committed
886
				res |= ir_usage_unknown;
887
888
				break;
			}
889
			/* Check the successor of irn. */
890
			res |= determine_entity_usage(succ, sel_entity);
891
892
893
894
			break;
		}

		case iro_Call:
895
896
897
898
899
900
901
902
903
			if (irn == get_Call_ptr(succ)) {
				/* TODO: we could check for reinterpret casts here...
				 * But I doubt anyone is interested in that bit for
				 * function entities and I'm too lazy to write the code now.
				 */
				res |= ir_usage_read;
			} else {
				assert(irn != get_Call_mem(succ));
				res |= ir_usage_unknown;
904
905
			}
			break;
906

907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
		/* skip identities */
		case iro_Id:
			res |= determine_entity_usage(succ, entity);
			break;

		/* skip tuples */
		case iro_Tuple: {
			int input_nr;
			for (input_nr = get_Tuple_n_preds(succ) - 1; input_nr >= 0;
					--input_nr) {
				ir_node *pred = get_Tuple_pred(succ, input_nr);
				if (pred == irn) {
					int k;
					/* we found one input */
					for (k = get_irn_n_outs(succ) - 1; k >= 0; --k) {
						ir_node *proj = get_irn_out(succ, k);

						if (is_Proj(proj) && get_Proj_proj(proj) == input_nr) {
							res |= determine_entity_usage(proj, entity);
							break;
						}
					}
				}
			}
			break;
		}
933

934
		default:
935
936
			/* another op, we don't know anything (we could do more advanced
			 * things like a dataflow analysis here) */
937
938
			res |= ir_usage_unknown;
			break;
939
940
		}
	}
941

942
	return (ir_entity_usage) res;
943
}
944
945

/**
946
 * Update the usage flags of all frame entities.
947
 */
948
949
static void analyse_irg_entity_usage(ir_graph *irg)
{
950
951
	ir_type *ft = get_irg_frame_type(irg);

952
953
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS);

954
	/* set initial state to not_taken, as this is the "smallest" state */
Matthias Braun's avatar
Matthias Braun committed
955
	for (size_t i = 0, n = get_class_n_members(ft); i < n; ++i) {
956
		ir_entity *ent = get_class_member(ft, i);
957

958
		/* methods can only be analyzed globally */
Matthias Braun's avatar
Matthias Braun committed
959
		if (!is_method_entity(ent)) {
960
			ir_entity_usage flags = ir_usage_none;
Matthias Braun's avatar
Matthias Braun committed
961
962
			if (get_entity_linkage(ent) & IR_LINKAGE_HIDDEN_USER)
				flags = ir_usage_unknown;
963
964
			set_entity_usage(ent, flags);
		}
965
966
	}

Matthias Braun's avatar
Matthias Braun committed
967
	ir_node *irg_frame = get_irg_frame(irg);
968

Matthias Braun's avatar
Matthias Braun committed
969
	for (int j = get_irn_n_outs(irg_frame); j-- > 0; ) {
Michael Beck's avatar
Michael Beck committed
970
		ir_node        *succ = get_irn_out(irg_frame, j);
971
		ir_entity      *entity;
972
		unsigned        flags;
973

Michael Beck's avatar
Michael Beck committed
974
		if (!is_Sel(succ))
975
			continue;
976

977
978
979
		entity = get_Sel_entity(succ);
		flags  = get_entity_usage(entity);
		flags |= determine_entity_usage(succ, entity);
980
		set_entity_usage(entity, (ir_entity_usage) flags);
981
	}
982

983
	/* check inner functions accessing outer frame */
Matthias Braun's avatar
Matthias Braun committed
984
985
	int static_link_arg = 0;
	for (size_t i = 0, n = get_class_n_members(ft); i < n; ++i) {
986
		ir_entity *ent = get_class_member(ft, i);
Matthias Braun's avatar
Matthias Braun committed
987
		if (!is_method_entity(ent))
988
			continue;