irmemory.c 28.9 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
#include "irmemory.h"
#include "irflag.h"
#include "hashptr.h"
#include "irflag.h"
24
#include "irouts_t.h"
25
#include "irgwalk.h"
Matthias Braun's avatar
Matthias Braun committed
26
#include "irprintf.h"
27
#include "debug.h"
Matthias Braun's avatar
Matthias Braun committed
28
#include "panic.h"
29
#include "typerep.h"
30
#include "type_t.h"
Matthias Braun's avatar
Matthias Braun committed
31
#include "util.h"
32
33
34

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

37
/** The global memory disambiguator options. */
38
static unsigned global_mem_disamgig_opt = aa_opt_none;
39

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

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

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

Matthias Braun's avatar
Matthias Braun committed
67
void set_irp_memory_disambiguator_options(ir_disambiguator_options options)
68
{
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
 * Find the base address and entity of an Sel/Member node.
79
 *
80
 * @param node the node
81
82
83
 * @param pEnt after return points to the base entity.
 *
 * @return the base address.
84
 */
85
static const ir_node *find_base_addr(const ir_node *node, ir_entity **pEnt)
86
{
87
88
89
90
91
92
	const ir_node *member = NULL;
	for (;;) {
		if (is_Sel(node)) {
			node = get_Sel_ptr(node);
			continue;
		} else if (is_Member(node)) {
93
94
95
96
97
			ir_node *pred = get_Member_ptr(node);
			/** local variables are members of the frame type, but all disjunct
			 * so we regard them as base addresses */
			if (is_Proj(pred) && pred == get_irg_frame(get_irn_irg(pred)))
				break;
98
			member = node;
99
			node   = pred;
100
101
102
		} else {
			break;
		}
103
	}
104
105
106
	if (member != NULL)
		*pEnt = get_Member_entity(member);
	return node;
107
}
108
109

/**
110
111
112
113
 * Returns true if @c compound is a compound type that contains a
 * member with type @c member, including recursively, or if @c
 * compound is an array type with a base type equal to or containing
 * @c member.
114
 *
115
116
117
118
 * @param compound  The compound type
 * @param member    The member type
 *
 * @return true, if @c compound contains @c member
119
 */
120
121
static bool type_contains(const ir_type *compound,
                          const ir_type *member)
122
{
123
124
125
126
127
128
129
130
131
132
133
134
135
	if (is_Array_type(compound)) {
		ir_type *elem = get_array_element_type(compound);
		return elem == member ||
		       type_contains(elem, member);

	} else if (is_compound_type(compound)) {
		size_t n = get_compound_n_members(compound);
		for (size_t pos = 0; pos < n; pos++) {
			ir_entity *ent = get_compound_member(compound, pos);
			ir_type *pos_type = get_entity_type(ent);
			if (pos_type == member ||
			    type_contains(pos_type, member)) {
				return true;
136
137
			}
		}
138
139
140
		return false;
	} else {
		return false;
141
	}
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
}

/**
 * Determine the alias relation by checking if type1 and type2 are
 * different types.
 *
 * @param addr1    The first type.
 * @param addr2    The second type.
 */
static ir_alias_relation different_types(const ir_type *type1,
                                         const ir_type *type2)
{
	if (type1 == type2) {
		return ir_may_alias;
	}
	/* do deref until no pointer types are found */
	while (is_Pointer_type(type1) && is_Pointer_type(type2)) {
		type1 = get_pointer_points_to_type(type1);
		type2 = get_pointer_points_to_type(type2);
	}
	if (type_contains(type1, type2) || type_contains(type2, type1)) {
		return ir_may_alias;
	}
	if (is_Class_type(type1) && is_Class_type(type2) &&
	    (is_SubClass_of(type1, type2) || is_SubClass_of(type2, type1))) {
		return ir_may_alias;
	}
	return ir_no_alias;
170
}
171

172
173
174
175
176
/**
 * Returns non-zero if a node is a result on a malloc-like routine.
 *
 * @param node  the Proj node to test
 */
177
static bool is_malloc_Result(const ir_node *node)
178
{
179
	node = get_Proj_pred(node);
Matthias Braun's avatar
Matthias Braun committed
180
	if (!is_Proj(node))
181
		return false;
182
	node = get_Proj_pred(node);
Matthias Braun's avatar
Matthias Braun committed
183
	if (!is_Call(node))
184
		return false;
185
	ir_entity *callee = get_Call_callee(node);
186
187
	return callee != NULL
	    && (get_entity_additional_properties(callee) & mtp_property_malloc);
188
}
189

190
191
ir_storage_class_class_t classify_pointer(const ir_node *const addr,
                                          const ir_node *const base)
192
{
193
194
195
196
197
198
	/* part1: determine class */
	ir_storage_class_class_t res;
	ir_entity               *entity;
	if (is_Address(base)) {
		entity = get_Address_entity(base);
		ir_type *owner = get_entity_owner(entity);
199
		res = owner == get_tls_type() ? ir_sc_tls : ir_sc_globalvar;
200
201
202
203
204
205
206
207
208
209
210
211
212
213
		goto analyze_entity;
	} else if (is_Member(base)) {
		/* should only happen for local vars */
		assert(get_Member_ptr(base) == get_irg_frame(get_irn_irg(base)));
		entity = get_Member_entity(base);
		res    = is_parameter_entity(entity) ? ir_sc_argument : ir_sc_localvar;
		goto analyze_entity;
	} else if (is_Proj(base)) {
		if (is_malloc_Result(base))
			res = ir_sc_malloced;
		else
			res = ir_sc_pointer;
	} else if (is_Const(base)) {
		ir_tarval *tv = get_Const_tarval(base);
214
		if (tarval_is_null(tv))
215
			res = ir_sc_null;
216
		else
217
218
219
220
221
			res = ir_sc_globaladdr;
	} else {
		/* we always should have Member(irg_frame) as base address */
		assert(base != get_irg_frame(get_irn_irg(base)));
		res = ir_sc_pointer;
222
223
	}

224
225
226
227
228
229
230
231
232
233
234
235
236
237
	/* part2: modifiers */

	/* if we select a member/array elem from addr, then it must have been
	 * a compound type */
	if (is_Sel(addr) || is_Member(addr))
		res |= ir_sc_modifier_obj_comp;
	return res;

analyze_entity:
	if (!(get_entity_usage(entity) & ir_usage_address_taken))
		res |= ir_sc_modifier_nottaken;
	const ir_type *type = get_entity_type(entity);
	res |= is_compound_type(type) ? ir_sc_modifier_obj_comp
	                              : ir_sc_modifier_obj_prim;
Michael Beck's avatar
Fixed:    
Michael Beck committed
238
	return res;
239
240
}

241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
typedef struct address_info {
	ir_node const *base;
	ir_node const *sym_offset;
	long           offset;
	bool           has_const_offset;
} address_info;

static address_info get_address_info(ir_node const *addr)
{
	ir_node *sym_offset       = NULL;
	long     offset           = 0;
	bool     has_const_offset = true;
	for (;;) {
		switch (get_irn_opcode(addr)) {
		case iro_Add: {
			ir_node       *ptr_node;
			ir_node       *int_node;
			ir_mode *const mode_left = get_irn_mode(get_Add_left(addr));
			if (mode_is_reference(mode_left)) {
				ptr_node = get_Add_left(addr);
				int_node = get_Add_right(addr);
			} else {
				ptr_node = get_Add_right(addr);
				int_node = get_Add_left(addr);
			}

			if (is_Const(int_node)) {
				ir_tarval *tv = get_Const_tarval(int_node);
				if (tarval_is_long(tv)) {
					/* TODO: check for overflow */
					offset += get_tarval_long(tv);
					goto follow_ptr;
				}
			}
			if (!sym_offset) {
				sym_offset = int_node;
			} else {
				// addr has more than one symbolic offset, give up.
				has_const_offset = false;
			}

follow_ptr:
			addr = ptr_node;
			break;
		}

287
288
289
290
291
		case iro_Sub:
			has_const_offset = false;
			addr             = get_Sub_left(addr);
			break;

292
293
294
295
296
297
		default:
			return (address_info){ addr, sym_offset, offset, has_const_offset };
		}
	}
}

298
static ir_alias_relation _get_alias_relation(
Matthias Braun's avatar
Matthias Braun committed
299
300
	const ir_node *addr1, const ir_type *const objt1, unsigned size1,
	const ir_node *addr2, const ir_type *const objt2, unsigned size2)
301
{
302
	if (addr1 == addr2)
Michael Beck's avatar
Michael Beck committed
303
		return ir_sure_alias;
304
	ir_graph *const irg     = get_irn_irg(addr1);
Matthias Braun's avatar
Matthias Braun committed
305
	unsigned  const options = get_irg_memory_disambiguator_options(irg);
306
307
	if (options & aa_opt_always_alias)
		return ir_may_alias;
308
309
	/* The Armageddon switch */
	if (options & aa_opt_no_alias)
Michael Beck's avatar
Michael Beck committed
310
		return ir_no_alias;
311

Andreas Fried's avatar
Andreas Fried committed
312
	/* do the addresses have constants offsets from the same base?
Matthias Braun's avatar
Matthias Braun committed
313
	 *  Note: sub X, C is normalized to add X, -C */
Andreas Fried's avatar
Andreas Fried committed
314
315
316
317

	/*
	 * Currently, only expressions with at most one symbolic
	 * offset can be handled.  To extend this, change
318
	 * sym_offset to be a set, and compare the sets.
Andreas Fried's avatar
Andreas Fried committed
319
	 */
320
321
322
323
324
325
	address_info const info1   = get_address_info(addr1);
	address_info const info2   = get_address_info(addr2);
	long               offset1 = info1.offset;
	long               offset2 = info2.offset;
	addr1 = info1.base;
	addr2 = info2.base;
326

Michael Beck's avatar
Fixed:    
Michael Beck committed
327
	/* same base address -> compare offsets if possible.
Matthias Braun's avatar
Matthias Braun committed
328
	 * FIXME: type long is not sufficient for this task ... */
329
	if (addr1 == addr2 && info1.sym_offset == info2.sym_offset && info1.has_const_offset && info2.has_const_offset) {
330
331
		unsigned long first_offset;
		unsigned long last_offset;
Matthias Braun's avatar
Matthias Braun committed
332
		unsigned first_size;
333
334
335
336

		if (offset1 <= offset2) {
			first_offset = offset1;
			last_offset = offset2;
Matthias Braun's avatar
Matthias Braun committed
337
			first_size = size1;
338
339
340
		} else {
			first_offset = offset2;
			last_offset = offset1;
Matthias Braun's avatar
Matthias Braun committed
341
			first_size = size2;
342
343
		}

Matthias Braun's avatar
Matthias Braun committed
344
		return first_offset + first_size <= last_offset
345
		     ? ir_no_alias : ir_sure_alias;
346
	}
347

348
349
350
	/* skip Sels/Members */
	ir_entity     *ent1  = NULL;
	ir_entity     *ent2  = NULL;
351
352
	const ir_node *base1 = find_base_addr(addr1, &ent1);
	const ir_node *base2 = find_base_addr(addr2, &ent2);
353

354
	/* two struct accesses -> compare entities */
355
	if (ent1 != NULL && ent2 != NULL) {
356
357
358
359
360
		if (ent1 == ent2) {
			if (base1 == base2)
				return ir_sure_alias;
			goto check_classes;
		}
361
362
363
		ir_type *owner1 = get_entity_owner(ent1);
		ir_type *owner2 = get_entity_owner(ent2);
		if (owner1 != owner2) {
364
			/* TODO: We have to differentiate 3 cases:
365
			 * - owner1 or owner2 is a type used in a subtree of the other.
366
367
368
369
			 * - If there exists a union type where the first elements towards
			 *   owner1+owner2 and the fields inside owner1+owner2 are
			 *   compatible, then they may alias.
			 * - All other cases cannot alias.
370
			 * => for now we assume may alias
371
372
			 */
			goto check_classes;
373
374
		}
		/* same owner, different entities? They may only alias if we have a
375
		 * union or if one of them is a bitfield members. */
376
377
		/* TODO: can we test if the base units actually overlap in the bitfield
		 * case? */
378
379
380
		if (!is_Union_type(owner1) && get_entity_bitfield_size(ent1) == 0
		    && get_entity_bitfield_size(ent2) == 0)
		    return ir_no_alias;
381
	}
382

383
check_classes:;
384
	/* no alias if 1 is a primitive object and the other a compound object */
385
386
387
388
	const ir_storage_class_class_t mod1 = classify_pointer(addr1, base1);
	const ir_storage_class_class_t mod2 = classify_pointer(addr2, base2);
	if (((mod1 | mod2) & (ir_sc_modifier_obj_comp | ir_sc_modifier_obj_prim))
	    == (ir_sc_modifier_obj_comp | ir_sc_modifier_obj_prim))
389
390
		return ir_no_alias;

391
392
	const ir_storage_class_class_t class1 = mod1 & ~ir_sc_modifiers;
	const ir_storage_class_class_t class2 = mod2 & ~ir_sc_modifiers;
393
394
395
396
397
398
399
400
401
402
	ir_storage_class_class_t other_class;
	ir_storage_class_class_t other_mod;
	if (class1 == ir_sc_pointer) {
		other_class = class2;
		other_mod   = mod2;
		goto pointer;
	} else if (class2 == ir_sc_pointer) {
		other_class = class1;
		other_mod   = mod1;
pointer:
403
		/* a pointer and an object whose address was never taken */
404
		if (other_mod & ir_sc_modifier_nottaken)
Michael Beck's avatar
Michael Beck committed
405
			return ir_no_alias;
406
		/* the null pointer aliases nothing */
407
		if (other_class == ir_sc_null)
408
			return ir_no_alias;
Michael Beck's avatar
Michael Beck committed
409
	} else if (class1 != class2) {
410
		/* objects from different memory spaces cannot alias */
Michael Beck's avatar
Michael Beck committed
411
412
413
414
		return ir_no_alias;
	} else {
		/* both classes are equal */
		if (class1 == ir_sc_globalvar) {
415
416
			ir_entity *entity1 = get_Address_entity(base1);
			ir_entity *entity2 = get_Address_entity(base2);
417
418
419
420
421
			return entity1 != entity2 ? ir_no_alias : ir_may_alias;
		} else if (class1 == ir_sc_localvar) {
			ir_entity *entity1 = get_Member_entity(base1);
			ir_entity *entity2 = get_Member_entity(base2);
			return entity1 != entity2 ? ir_no_alias : ir_may_alias;
422
		} else if (class1 == ir_sc_globaladdr) {
423
424
			offset1 += get_Const_long(base1);
			offset2 += get_Const_long(base2);
425

Matthias Braun's avatar
Matthias Braun committed
426
			unsigned type_size = MAX(size1, size2);
427
			if ((unsigned long)labs(offset2 - offset1) >= type_size)
428
429
430
				return ir_no_alias;
			else
				return ir_sure_alias;
431
432
		} else if (class1 == ir_sc_malloced) {
			return base1 == base2 ? ir_sure_alias : ir_no_alias;
Michael Beck's avatar
Michael Beck committed
433
434
435
436
		}
	}

	/* Type based alias analysis */
437
438
439
440
	if (options & aa_opt_type_based) {
		ir_alias_relation rel;

		if (options & aa_opt_byte_type_may_alias) {
441
			if (get_type_size(objt1) == 1 || get_type_size(objt2) == 1) {
442
				/* One of the types address a byte. Assume a ir_may_alias and leave
443
444
445
446
447
				   the type based check. */
				goto leave_type_based_alias;
			}
		}

448
		/* cheap check: If the type sizes did not match, the types MUST be different */
449
		/* No, one might be part of the other. */
450
		/* if (get_type_size(objt1) != get_type_size(objt2)) */
451
		/*         return ir_no_alias; */
452

453
		/* cheap test: if only one is a reference type, no alias */
454
		if (is_Pointer_type(objt1) != is_Pointer_type(objt2)) {
Michael Beck's avatar
Michael Beck committed
455
			return ir_no_alias;
456
		}
Michael Beck's avatar
Michael Beck committed
457

458
459
460
		if (is_Primitive_type(objt1) && is_Primitive_type(objt2)) {
			const ir_mode *const mode1 = get_type_mode(objt1);
			const ir_mode *const mode2 = get_type_mode(objt2);
461
462
463
464

			/* cheap test: if arithmetic is different, no alias */
			if (get_mode_arithmetic(mode1) != get_mode_arithmetic(mode2))
				return ir_no_alias;
465
466
467
			/* no alias if 1 is a reference and the other isn't */
			if (mode_is_reference(mode1) != mode_is_reference(mode2))
				return ir_no_alias;
468
469
		}

470
		rel = different_types(objt1, objt2);
471
472
473
474
475
		if (rel != ir_may_alias)
			return rel;
leave_type_based_alias:;
	}

Michael Beck's avatar
Michael Beck committed
476
	return ir_may_alias;
477
}
478
479

ir_alias_relation get_alias_relation(
Matthias Braun's avatar
Matthias Braun committed
480
481
	const ir_node *const addr1, const ir_type *const type1, unsigned size1,
	const ir_node *const addr2, const ir_type *const type2, unsigned size2)
482
{
Matthias Braun's avatar
Matthias Braun committed
483
	ir_alias_relation rel = _get_alias_relation(addr1, type1, size1, addr2, type2, size2);
484
485
	DB((dbg, LEVEL_1, "alias(%+F, %+F) = %s\n", addr1, addr2,
	    get_ir_alias_relation_name(rel)));
486
	return rel;
487
}
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507

/**
 * 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
 */
508
static bool is_hidden_cast(const ir_mode *mode, const ir_mode *ent_mode)
509
{
510
511
512
	if (ent_mode == NULL)
		return false;

Matthias Braun's avatar
Matthias Braun committed
513
514
515
516
517
	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;
518
	}
519
	return false;
520
}
521
522

/**
Christoph Mallon's avatar
Christoph Mallon committed
523
 * Determine the usage state of a node (or its successor Sels).
524
525
526
 *
 * @param irn  the node
 */
Matthias Braun's avatar
Matthias Braun committed
527
static ir_entity_usage determine_entity_usage(const ir_node *irn,
528
                                              const ir_entity *entity)
529
{
Matthias Braun's avatar
Matthias Braun committed
530
	unsigned res = 0;
531
532
533
534
	for (int i = get_irn_n_outs(irn); i-- > 0; ) {
		int            succ_pos;
		const ir_node *succ  = get_irn_out_ex(irn, i, &succ_pos);

535
536
		switch (get_irn_opcode(succ)) {
		case iro_Load:
537
538
			/* beware: irn might be a Id node here, so irn might be not
			   equal to get_Load_ptr(succ) */
539
540
			res |= ir_usage_read;

541
			/* check if this load is not a hidden conversion */
Matthias Braun's avatar
Matthias Braun committed
542
543
			ir_mode *mode  = get_Load_mode(succ);
			ir_mode *emode = get_type_mode(get_entity_type(entity));
544
			if (is_hidden_cast(mode, emode))
545
				res |= ir_usage_reinterpret_cast;
546
547
548
549
			break;

		case iro_Store:
			/* check that the node is not the Store's value */
550
			if (succ_pos == n_Store_value) {
551
				res |= ir_usage_unknown;
552
			} else if (succ_pos == n_Store_ptr) {
553
554
555
				res |= ir_usage_write;

				/* check if this Store is not a hidden conversion */
Matthias Braun's avatar
Matthias Braun committed
556
557
558
				ir_node *value = get_Store_value(succ);
				ir_mode *mode  = get_irn_mode(value);
				ir_mode *emode = get_type_mode(get_entity_type(entity));
559
560
561
562
				if (is_hidden_cast(mode, emode))
					res |= ir_usage_reinterpret_cast;
			}
			assert(irn != get_Store_mem(succ));
563
564
			break;

Matthias Braun's avatar
Matthias Braun committed
565
		case iro_CopyB: {
566
			/* CopyB are like Loads/Stores */
567
			ir_type *tp = get_entity_type(entity);
568
569
			if (tp != get_CopyB_type(succ)) {
				/* bad, different types, might be a hidden conversion */
570
571
				res |= ir_usage_reinterpret_cast;
			}
572
			if (succ_pos == n_CopyB_dst) {
573
574
				res |= ir_usage_write;
			} else {
575
				assert(succ_pos == n_CopyB_src);
576
				res |= ir_usage_read;
577
578
			}
			break;
Matthias Braun's avatar
Matthias Braun committed
579
		}
580

581
		case iro_Sel:
582
583
		case iro_Add:
		case iro_Sub:
584
		case iro_Id:
585
586
587
			/* Check the successor of irn. */
			res |= determine_entity_usage(succ, entity);
			break;
588
589
590

		case iro_Member: {
			ir_entity *member_entity = get_Member_entity(succ);
591
			/* Check the successor of irn. */
592
			res |= determine_entity_usage(succ, member_entity);
593
594
595
596
			break;
		}

		case iro_Call:
597
			if (succ_pos == n_Call_ptr) {
598
599
600
601
602
603
				/* 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 {
604
605
606
607
608
609
610
611
				assert(succ_pos != n_Call_mem);
				int arg_nr = succ_pos - n_Call_max - 1;
				ir_type *type     = get_Call_type(succ);
				ir_type *arg_type = get_method_param_type(type, arg_nr);
				if (is_aggregate_type(arg_type))
					res |= ir_usage_read;
				else
					res |= ir_usage_unknown;
612
613
			}
			break;
614

615
		/* skip tuples */
616
617
		case iro_Tuple:
			foreach_irn_out_r(succ, k, proj) {
618
				if (is_Proj(proj) && get_Proj_num(proj) == (unsigned)succ_pos) {
619
620
					res |= determine_entity_usage(proj, entity);
					break;
621
622
623
				}
			}
			break;
624

625
626
627
628
629
630
631
632
633
634
		case iro_Builtin: {
			ir_builtin_kind kind = get_Builtin_kind(succ);
			/* the parameters of the may_alias builtin do not lead to
			 * read/write or address taken. */
			if (kind == ir_bk_may_alias)
				break;
			res |= ir_usage_unknown;
			break;
		}

635
		default:
636
637
			/* another op, we don't know anything (we could do more advanced
			 * things like a dataflow analysis here) */
638
639
			res |= ir_usage_unknown;
			break;
640
641
		}
	}
642

643
	return (ir_entity_usage) res;
644
}
645
646

/**
647
 * Update the usage flags of all frame entities.
648
 */
649
650
static void analyse_irg_entity_usage(ir_graph *irg)
{
651
652
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS);

653
	/* set initial state to not_taken, as this is the "smallest" state */
654
	ir_type *frame_type = get_irg_frame_type(irg);
655
656
	for (size_t i = 0, n = get_compound_n_members(frame_type); i < n; ++i) {
		ir_entity *ent = get_compound_member(frame_type, i);
657
		/* methods can only be analyzed globally */
658
659
660
661
662
663
		if (is_method_entity(ent))
			continue;
		ir_entity_usage flags = ir_usage_none;
		if (get_entity_linkage(ent) & IR_LINKAGE_HIDDEN_USER)
			flags = ir_usage_unknown;
		set_entity_usage(ent, flags);
664
665
	}

Matthias Braun's avatar
Matthias Braun committed
666
	ir_node *irg_frame = get_irg_frame(irg);
667

668
	foreach_irn_out_r(irg_frame, j, succ) {
669
		if (!is_Member(succ))
670
			continue;
671

672
673
		ir_entity *entity = get_Member_entity(succ);
		unsigned   flags  = get_entity_usage(entity);
674
		flags |= determine_entity_usage(succ, entity);
675
		set_entity_usage(entity, (ir_entity_usage) flags);
676
	}
677

678
	/* now computed */
679
	add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
680
}
681

Matthias Braun's avatar
Matthias Braun committed
682
683
void assure_irg_entity_usage_computed(ir_graph *irg)
{
684
	if (irg_has_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE))
685
		return;
686

687
688
	analyse_irg_entity_usage(irg);
}
689
690

/**
691
 * Initialize the entity_usage flag for a global type like type.
692
 */
Matthias Braun's avatar
Matthias Braun committed
693
694
static void init_entity_usage(ir_type *tp)
{
695
	/* We have to be conservative: All external visible entities are unknown */
Matthias Braun's avatar
Matthias Braun committed
696
697
698
	for (size_t i = 0, n = get_compound_n_members(tp); i < n; ++i) {
		ir_entity *ent   = get_compound_member(tp, i);
		unsigned   flags = ir_usage_none;
699

700
		if (entity_is_externally_visible(ent)) {
701
702
			flags |= ir_usage_unknown;
		}
703
		set_entity_usage(ent, (ir_entity_usage) flags);
704
	}
705
}
706

707
708
709
710
711
712
713
714
715
716
717
718
/**
 * Mark all entities used in the initializer's value as unknown usage.
 *
 * @param value  the value to check
 */
static void check_initializer_value(ir_node *value)
{
	/* Handle each node at most once. */
	if (irn_visited_else_mark(value))
		return;

	/* let's check if it's an address */
719
720
	if (is_Address(value)) {
		ir_entity *ent = get_Address_entity(value);
721
722
723
		set_entity_usage(ent, ir_usage_unknown);
	}

724
	foreach_irn_in(value, i, op) {
725
726
727
728
		check_initializer_value(op);
	}
}

Michael Beck's avatar
Michael Beck committed
729
730
731
732
733
/**
 * Mark all entities used in the initializer as unknown usage.
 *
 * @param initializer  the initializer to check
 */
734
735
static void check_initializer_nodes(ir_initializer_t *initializer)
{
Michael Beck's avatar
Michael Beck committed
736
	switch (initializer->kind) {
Matthias Braun's avatar
Matthias Braun committed
737
	case IR_INITIALIZER_CONST: {
738
739
740
741
742
743
		ir_node  *n   = initializer->consti.value;
		ir_graph *irg = get_irn_irg(n);
		ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
		inc_irg_visited(irg);
		check_initializer_value(n);
		ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
744
		return;
Matthias Braun's avatar
Matthias Braun committed
745
	}
746
747
748
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;
Michael Beck's avatar
Michael Beck committed
749
	case IR_INITIALIZER_COMPOUND:
Matthias Braun's avatar
Matthias Braun committed
750
		for (size_t i = 0; i < initializer->compound.n_initializers; ++i) {
751
752
753
754
755
756
			ir_initializer_t *sub_initializer
				= initializer->compound.initializers[i];
			check_initializer_nodes(sub_initializer);
		}
		return;
	}
Michael Beck's avatar
Michael Beck committed
757
	panic("invalid initializer found");
758
}
759

760
/**
Michael Beck's avatar
Michael Beck committed
761
762
 * Mark all entities used in the initializer for the given entity as unknown
 * usage.
Michael Beck's avatar
Michael Beck committed
763
764
 *
 * @param ent  the entity
765
 */
Matthias Braun's avatar
Matthias Braun committed
766
767
static void check_initializer(ir_entity *ent)
{
768
769
770
771
	if (get_entity_kind(ent) == IR_ENTITY_NORMAL) {
		ir_initializer_t *const init = get_entity_initializer(ent);
		if (init != NULL)
			check_initializer_nodes(init);
772
	}
Matthias Braun's avatar
Matthias Braun committed
773
}
774
775
776


/**
Michael Beck's avatar
Michael Beck committed
777
 * Mark all entities used in initializers as unknown usage.
Michael Beck's avatar
Michael Beck committed
778
779
 *
 * @param tp  a compound type
780
 */
781
782
static void check_initializers(ir_type *tp)
{
Matthias Braun's avatar
Matthias Braun committed
783
	for (size_t i = 0, n = get_compound_n_members(tp); i < n; ++i) {
784
785
786
787
		ir_entity *ent = get_compound_member(tp, i);

		check_initializer(ent);
	}
788
}
789

790
#ifdef DEBUG_libfirm
791
/**
792
 * Print the entity usage flags of all entities of a given type for debugging.
Michael Beck's avatar
Michael Beck committed
793
794
 *
 * @param tp  a compound type
795
 */
Michael Beck's avatar
Michael Beck committed
796
static void print_entity_usage_flags(const ir_type *tp)
797
{
Matthias Braun's avatar
Matthias Braun committed
798
799
	for (size_t i = 0, n = get_compound_n_members(tp); i < n; ++i) {
		ir_entity      *ent   = get_compound_member(tp, i);
800
801
802
803
		ir_entity_usage flags = get_entity_usage(ent);

		if (flags == 0)
			continue;
Christoph Mallon's avatar
Christoph Mallon committed
804
		ir_printf("%+F:", ent);
805
806
807
808
809
810
811
812
813
		if (flags & ir_usage_address_taken)
			printf(" address_taken");
		if (flags & ir_usage_read)
			printf(" read");
		if (flags & ir_usage_write)
			printf(" write");
		if (flags & ir_usage_reinterpret_cast)
			printf(" reinterp_cast");
		printf("\n");
814
	}
815
}
816
#endif /* DEBUG_libfirm */
817
818
819
820

/**
 * Post-walker: check for global entity address
 */
821
static void check_global_address(ir_node *irn, void *data)
822
{
Matthias Braun's avatar
Matthias Braun committed
823
	(void)data;
824
	if (!is_Address(irn))
825
826
		return;

827
	ir_entity *entity = get_Address_entity(irn);
Matthias Braun's avatar
Matthias Braun committed
828
829
830
	unsigned   flags  = get_entity_usage(entity);
	flags |= determine_entity_usage(irn, entity);
	set_entity_usage(entity, (ir_entity_usage) flags);
831
}
832
833

/**
834
 * Update the entity usage flags of all global entities.
835
 */
836
837
static void analyse_irp_globals_entity_usage(void)
{
Matthias Braun's avatar
Matthias Braun committed
838
	for (ir_segment_t s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s) {
839
840
841
		ir_type *type = get_segment_type(s);
		init_entity_usage(type);
	}
842

Matthias Braun's avatar
Matthias Braun committed
843
	for (ir_segment_t s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s) {
844
845
846
		ir_type *type = get_segment_type(s);
		check_initializers(type);
	}
847

848
	foreach_irp_irg(i, irg) {
849
		assure_irg_outs(irg);
850
		irg_walk_graph(irg, NULL, check_global_address, NULL);
851
	}
852
853
854

#ifdef DEBUG_libfirm
	if (firm_dbg_get_mask(dbg) & LEVEL_1) {
Matthias Braun's avatar
Matthias Braun committed
855
		for (ir_segment_t s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s) {
856
857
			print_entity_usage_flags(get_segment_type(s));
		}
858
859
	}
#endif /* DEBUG_libfirm */
860
861

	/* now computed */
862
863
	irp->globals_entity_usage_state = ir_entity_usage_computed;
}
864

865
866
ir_entity_usage_computed_state get_irp_globals_entity_usage_state(void)
{
867
868
	return irp->globals_entity_usage_state;
}
869

870
871
void set_irp_globals_entity_usage_state(ir_entity_usage_computed_state state)
{
872
873
	irp->globals_entity_usage_state = state;
}
874

875
876
void assure_irp_globals_entity_usage_computed(void)
{
877
878
879
880
881
	if (irp->globals_entity_usage_state != ir_entity_usage_not_computed)
		return;

	analyse_irp_globals_entity_usage();
}
882

883
884
void firm_init_memory_disambiguator(void)
{
885
	FIRM_DBG_REGISTER(dbg, "firm.ana.irmemory");
886
	FIRM_DBG_REGISTER(dbgcall, "firm.opt.cc");
887
888
}

889
890
891
892
893
/** Maps method types to cloned method types. */
static pmap *mtp_map;

/**
 * Clone a method type if not already cloned.
Michael Beck's avatar
Michael Beck committed
894
895
 *
 * @param tp  the type to clone
896
 */
897
static ir_type *clone_type_and_cache(ir_type *const tp, bool const is_variadic)
898
{
899
	ir_type *res = pmap_get(ir_type, mtp_map, tp);
900
	if (res == NULL) {
901
902
		mtp_additional_properties const props = get_method_additional_properties(tp);
		res = clone_type_method(tp, is_variadic, props | mtp_property_private);
903
904
		pmap_insert(mtp_map, tp, res);
	}
905
906

	return res;
907
}
908

909
/**
Michael Beck's avatar
Michael Beck committed
910
911
 * Walker: clone all call types of Calls to methods having the
 * mtp_property_private property set.
912
 */
913
914
static void update_calls_to_private(ir_node *call, void *env)
{
915
916
917
918
919
920
921
922
923
924
	(void)env;
	if (!is_Call(call))
		return;
	ir_entity *callee = get_Call_callee(call);
	if (callee == NULL)
		return;

	ir_type *ctp = get_Call_type(call);
	if ((get_entity_additional_properties(callee) & mtp_property_private)
		&& ((get_method_additional_properties(ctp) & mtp_property_private) == 0)) {
925
		ir_type *const entity_ctp = get_entity_type(callee);
926
927
		/* clear mismatches in variadicity that can happen in obscure C
		 * programs and break when changing to private calling convention. */
928
		ctp = clone_type_and_cache(ctp, is_method_variadic(entity_ctp));
929
930
931
932
		set_Call_type(call, ctp);
		DB((dbgcall, LEVEL_1,
		    "changed call to private method %+F using cloned type %+F\n",
		    callee, ctp));
933
	}
934
}
935

Matthias Braun's avatar
Matthias Braun committed
936
937
void mark_private_methods(void)
{
938
	assure_irp_globals_entity_usage_computed();
939
940
	mtp_map = pmap_create();

941
	/* first step: change the calling conventions of the local non-escaped entities */
Matthias Braun's avatar
Matthias Braun committed
942
	bool changed = false;
943
	foreach_irp_irg(i, irg) {
944
945
		ir_entity       *ent   = get_irg_entity(irg);
		ir_entity_usage  flags = get_entity_usage(ent);
946

Michael Beck's avatar
Michael Beck committed
947
		if (!(flags & ir_usage_address_taken) && !entity_is_externally_visible(ent)) {
948
949
			ir_type *mtp = get_entity_type(ent);

950
			add_entity_additional_properties(ent, mtp_property_private);
951
			DB((dbgcall, LEVEL_1, "found private method %+F\n", ent));
952
953
			if ((get_method_additional_properties(mtp) & mtp_property_private) == 0) {
				/* need a new type */
954
				mtp = clone_type_and_cache(mtp, is_method_variadic(mtp));
955
956
				set_entity_type(ent, mtp);
				DB((dbgcall, LEVEL_2, "changed entity type of %+F to %+F\n", ent, mtp));
Matthias Braun's avatar
Matthias Braun committed
957
				changed = true;
958
			}
959
960
961
962
		}
	}

	if (changed)
963
964
965
		all_irg_walk(NULL, update_calls_to_private, NULL);

	pmap_destroy(mtp_map);
966
}
Andreas Fried's avatar