2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Memory disambiguator
23 * @author Michael Beck
34 #include "irgraph_t.h"
44 /** The source language specific language disambiguator function. */
45 static DISAMBIGUATOR_FUNC language_disambuigator = NULL;
47 /** The global memory disambiguator options. */
48 static unsigned global_mem_disamgig_opt = aa_opt_no_opt;
50 /* Get the memory disambiguator options for a graph. */
51 unsigned get_irg_memory_disambiguator_options(ir_graph *irg) {
52 unsigned opt = irg->mem_disambig_opt;
53 if (opt & aa_opt_inherited)
54 return global_mem_disamgig_opt;
56 } /* get_irg_memory_disambiguator_options */
58 /* Set the memory disambiguator options for a graph. */
59 void set_irg_memory_disambiguator_options(ir_graph *irg, unsigned options) {
60 irg->mem_disambig_opt = options & ~aa_opt_inherited;
61 } /* set_irg_memory_disambiguator_options */
63 /* Set the global disambiguator options for all graphs not having local options. */
64 void set_irp_memory_disambiguator_options(unsigned options) {
65 global_mem_disamgig_opt = options;
66 } /* set_irp_memory_disambiguator_options */
69 * Find the base address and entity of an Sel node.
72 * @param pEnt after return points to the base entity.
74 * @return the base address.
76 static ir_node *find_base_adr(ir_node *sel, ir_entity **pEnt) {
77 ir_node *ptr = get_Sel_ptr(sel);
81 ptr = get_Sel_ptr(sel);
83 *pEnt = get_Sel_entity(sel);
88 * Check if the address can be decomposed into base PLUS offset.
90 static int has_offset(ir_node *adr, int *offset) {
91 if (is_SymConst(adr)) {
96 ir_entity *ent = get_Sel_entity(adr);
97 ir_type *owner = get_entity_owner(ent);
99 if (get_type_state(owner) != layout_fixed) {
100 /* The layout is NOT fixed yet, symbolic evaluation needed */
107 * Two address expressions have the same base address,
108 * check if there offsets are different.
110 * @param adr1 The first address.
111 * @param adr2 The second address.
113 static ir_alias_relation different_offsets(ir_node *adr1, ir_node *adr2) {
114 int offset1, offset2;
115 if (has_offset(adr1, &offset1) && has_offset(adr2, &offset2)) {
119 } /* different_offsets */
122 * idx1 and idx2 represent two integer indexes. Check if they could be classified
124 static ir_alias_relation different_index(ir_node *idx1, ir_node *idx2) {
125 ir_alias_relation res = may_alias;
129 if (is_Const(idx1) && is_Const(idx2)) {
130 /* both are const, we can compare them */
131 return get_Const_tarval(idx1) == get_Const_tarval(idx2) ? sure_alias : no_alias;
134 /* Note: we rely here on the fact that normalization puts constants on the RIGHT side */
136 ir_node *l1 = get_Add_left(idx1);
137 ir_node *r1 = get_Add_right(idx1);
142 return classify_Const(r1) == CNST_NULL ? sure_alias : no_alias;
146 /* both are Adds, check if they are of x + c kind */
147 ir_node *l2 = get_Add_left(idx2);
148 ir_node *r2 = get_Add_right(idx2);
151 res = different_index(r1, r2);
153 res = different_index(r1, l2);
155 res = different_index(l1, l2);
157 res = different_index(l1, r2);
158 if (res != may_alias)
163 ir_node *l2 = get_Add_left(idx2);
164 ir_node *r2 = get_Add_right(idx2);
169 return classify_Const(r2) == CNST_NULL ? sure_alias : no_alias;
175 ir_node *l1 = get_Sub_left(idx1);
176 ir_node *r1 = get_Sub_right(idx1);
181 return classify_Const(r1) == CNST_NULL ? sure_alias : no_alias;
186 /* both are Subs, check if they are of x - c kind */
187 ir_node *l2 = get_Sub_left(idx2);
190 ir_node *r2 = get_Sub_right(idx2);
191 res = different_index(r1, r2);
194 if (res != may_alias)
198 ir_node *l2 = get_Sub_left(idx2);
199 ir_node *r2 = get_Sub_right(idx2);
204 return classify_Const(r2) == CNST_NULL ? sure_alias : no_alias;
210 } /* different_index */
213 * Two Sel addresses have the same base address, check if there offsets are different.
215 * @param adr1 The first address.
216 * @param adr2 The second address.
218 static ir_alias_relation different_sel_offsets(ir_node *sel1, ir_node *sel2) {
219 ir_entity *ent1 = get_Sel_entity(sel1);
220 ir_entity *ent2 = get_Sel_entity(sel2);
221 int i, check_arr = 0;
226 ir_type *tp1 = get_entity_type(ent1);
227 ir_type *tp2 = get_entity_type(ent2);
231 else if (get_type_state(tp1) == layout_fixed && get_type_state(tp2) == layout_fixed &&
232 get_type_size_bytes(tp1) == get_type_size_bytes(tp2))
236 /* we select an entity of same size, check for indexes */
237 int n = get_Sel_n_indexs(sel1);
240 if (n > 0 && n == get_Sel_n_indexs(sel2)) {
241 /* same non-zero number of indexes, an array access, check */
242 for (i = 0; i < n; ++i) {
243 ir_node *idx1 = get_Sel_index(sel1, i);
244 ir_node *idx2 = get_Sel_index(sel2, i);
245 ir_alias_relation res = different_index(idx1, idx2);
247 if (res == may_alias)
249 else if (res == no_alias)
252 /* if we have at least one no_alias, there is no alias relation, else we have sure */
253 return have_no > 0 ? no_alias : sure_alias;
257 } /* different_sel_offsets */
260 * Determine the alias relation by checking if adr1 and adr2 are pointer
263 * @param adr1 The first address.
264 * @param adr2 The second address.
266 static ir_alias_relation different_types(ir_node *adr1, ir_node *adr2)
268 ir_entity *ent1 = NULL, *ent2 = NULL;
270 if (is_SymConst(adr1) && get_SymConst_kind(adr1) == symconst_addr_ent)
271 ent1 = get_SymConst_entity(adr1);
272 else if (is_Sel(adr1))
273 ent1 = get_Sel_entity(adr1);
275 if (is_SymConst(adr2) && get_SymConst_kind(adr2) == symconst_addr_ent)
276 ent2 = get_SymConst_entity(adr2);
277 else if (is_Sel(adr2))
278 ent2 = get_Sel_entity(adr2);
280 if (ent1 != NULL && ent2 != NULL) {
281 ir_type *tp1 = get_entity_type(ent1);
282 ir_type *tp2 = get_entity_type(ent2);
285 if (is_Pointer_type(tp1) && is_Pointer_type(tp2)) {
286 /* do deref until no pointer types are found */
288 tp1 = get_pointer_points_to_type(tp1);
289 tp2 = get_pointer_points_to_type(tp2);
290 } while (is_Pointer_type(tp1) && is_Pointer_type(tp2));
293 if (get_type_tpop(tp1) != get_type_tpop(tp2)) {
294 /* different type structure */
297 if (is_Class_type(tp1)) {
298 /* check class hierarchy */
299 if (! is_SubClass_of(tp1, tp2) &&
300 ! is_SubClass_of(tp2, tp1))
303 /* different types */
309 } /* different_types */
312 * Returns non-zero if a node is a routine parameter.
314 * @param node the node to test
316 static int is_arg_Proj(ir_node *node) {
319 node = get_Proj_pred(node);
322 return pn_Start_T_args == get_Proj_proj(node) && is_Start(get_Proj_pred(node));
326 * Returns true if an address represents a global variable.
328 static INLINE int is_global_var(ir_node *irn) {
329 return is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent;
330 } /* is_global_var */
333 * Determine the alias relation between two addresses.
335 static ir_alias_relation _get_alias_relation(
337 ir_node *adr1, ir_mode *mode1,
338 ir_node *adr2, ir_mode *mode2)
341 ir_entity *ent1, *ent2;
344 if (! get_opt_alias_analysis())
350 options = get_irg_memory_disambiguator_options(irg);
352 /* The Armageddon switch */
353 if (options & aa_opt_no_alias)
356 /* Two save some code, sort the addresses by its id's. Beware, this
357 might break some things, so better check here. */
358 assert(iro_SymConst < iro_Sel && iro_Sel < iro_Proj && "Code dependence breaked");
359 op1 = get_irn_opcode(adr1);
360 op2 = get_irn_opcode(adr2);
371 if (is_global_var(adr1)) {
372 /* first address is a global variable */
374 if (is_global_var(adr2)) {
375 /* both addresses are global variables and we know
376 they are different (R1 a) */
377 if (get_SymConst_entity(adr1) != get_SymConst_entity(adr2))
380 /* equal addresses */
385 ir_node *base2 = find_base_adr(adr2, &ent2);
387 if (is_global_var(base2)) {
388 /* base2 address is a global var (R1 a) */
392 return different_offsets(adr1, adr2);
393 } else if (base2 == get_irg_frame(irg)) {
394 /* the second one is a local variable so they are always
397 } else if (base2 == get_irg_tls(irg)) {
398 /* the second one is a TLS variable so they are always
404 /* Here we are: the first is a global var, the second some pointer. */
405 ent1 = get_SymConst_entity(adr1);
406 if (get_entity_address_taken(ent1) == ir_address_not_taken) {
407 /* The address of the global variable was never taken, so
408 the pointer cannot match (R2). */
411 } else if (is_Sel(adr1)) {
412 /* the first address is a Sel */
413 ir_node *base1 = find_base_adr(adr1, &ent1);
415 if (base1 == get_irg_frame(irg)) {
416 /* the first is a local variable */
418 /* the second address is a Sel */
419 ir_node *base2 = find_base_adr(adr2, &ent2);
422 return different_sel_offsets(adr1, adr2);
423 else if (base2 == get_irg_frame(irg)) {
424 /* both addresses are local variables and we know
425 they are different (R1 a) */
428 } else if (base2 == get_irg_tls(irg)) {
429 /* the second one is a TLS variable so they are always
432 } else if (is_arg_Proj(base2)) {
433 /* the second one is an offset from a parameter so they are
434 always different (R1 e) */
437 } else if (is_arg_Proj(adr2)) {
438 /* a local variable and a parameter are always different (R1 e) */
441 } else if (base1 == get_irg_tls(irg)) {
442 /* the first is a TLS variable */
444 /* the second address is a Sel */
445 ir_node *base2 = find_base_adr(adr2, &ent2);
448 return different_sel_offsets(adr1, adr2);
449 else if (base2 == get_irg_frame(irg)) {
450 /* the second one is a local variable so they are always
453 } else if (base2 == get_irg_tls(irg)) {
454 /* both addresses are TLS variables and we know
455 they are different (R1 a) */
460 } else if (is_arg_Proj(base1)) {
461 /* the first one is an offset from a parameter */
463 /* the second address is a Sel */
464 ir_node *base2 = find_base_adr(adr2, &ent2);
466 if (base2 == get_irg_frame(irg)) {
467 /* the second one is a local variable so they are always
472 } else if (is_global_var(base1)) {
473 /* the first one is a global variable */
474 ent1 = get_SymConst_entity(base1);
476 /* the second address is a Sel */
477 ir_node *base2 = find_base_adr(adr2, &ent2);
480 return different_sel_offsets(adr1, adr2);
481 else if (base2 == get_irg_frame(irg)) {
482 /* the second one is a local variable so they are always
485 } else if (base2 == get_irg_tls(irg)) {
486 /* the second one is a TLS variable so they are always
489 } else if (is_arg_Proj(base2)) {
490 if (get_entity_address_taken(ent1) == ir_address_not_taken) {
491 /* The address of the global variable was never taken, so
492 the pointer cannot match (R2). */
495 } else if (is_global_var(base2)) {
496 ent2 = get_SymConst_entity(base2);
497 /* both addresses are global variables and we know
498 they are different (R1 a) */
506 if (options & aa_opt_type_based) { /* Type based alias analysis */
507 ir_alias_relation rel;
509 if (options & aa_opt_byte_type_may_alias) {
510 if (get_mode_size_bits(mode1) == 8 || get_mode_size_bits(mode2) == 8) {
511 /* One of the modes address a byte. Assume a may_alias and leave
512 the type based check. */
513 goto leave_type_based_alias;
516 /* cheap check: If the mode sizes did not match, the types MUST be different */
517 if (get_mode_size_bits(mode1) != get_mode_size_bits(mode2))
521 rel = different_types(adr1, adr2);
522 if (rel != may_alias)
524 leave_type_based_alias:;
527 /* do we have a language specific memory disambiguator? */
528 if (language_disambuigator) {
529 ir_alias_relation rel = (*language_disambuigator)(irg, adr1, mode1, adr2, mode2);
530 if (rel != may_alias)
534 /* access points-to information here */
536 } /* _get_alias_relation */
539 * Determine the alias relation between two addresses.
541 ir_alias_relation get_alias_relation(
543 ir_node *adr1, ir_mode *mode1,
544 ir_node *adr2, ir_mode *mode2)
546 ir_alias_relation rel = _get_alias_relation(irg, adr1, mode1, adr2, mode2);
548 } /* get_alias_relation */
550 /* Set a source language specific memory disambiguator function. */
551 void set_language_memory_disambiguator(DISAMBIGUATOR_FUNC func) {
552 language_disambuigator = func;
553 } /* set_language_memory_disambiguator */
555 /** The result cache for the memory disambiguator. */
556 static set *result_cache = NULL;
558 /** An entry in the relation cache. */
559 typedef struct mem_disambig_entry {
560 ir_node *adr1; /**< The first address. */
561 ir_node *adr2; /**< The second address. */
562 ir_alias_relation result; /**< The alias relation result. */
563 } mem_disambig_entry;
565 #define HASH_ENTRY(adr1, adr2) (HASH_PTR(adr1) ^ HASH_PTR(adr2))
568 * Compare two relation cache entries.
570 static int cmp_mem_disambig_entry(const void *elt, const void *key, size_t size) {
571 const mem_disambig_entry *p1 = elt;
572 const mem_disambig_entry *p2 = key;
574 return p1->adr1 == p2->adr1 && p1->adr2 == p2->adr2;
575 } /* cmp_mem_disambig_entry */
578 * Initialize the relation cache.
580 void mem_disambig_init(void) {
581 result_cache = new_set(cmp_mem_disambig_entry, 8);
582 } /* mem_disambig_init */
585 * Determine the alias relation between two addresses.
587 ir_alias_relation get_alias_relation_ex(
589 ir_node *adr1, ir_mode *mode1,
590 ir_node *adr2, ir_mode *mode2)
592 mem_disambig_entry key, *entry;
594 if (! get_opt_alias_analysis())
597 if (get_irn_opcode(adr1) > get_irn_opcode(adr2)) {
605 entry = set_find(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
607 return entry->result;
609 key.result = get_alias_relation(irg, adr1, mode1, adr2, mode2);
611 set_insert(result_cache, &key, sizeof(key), HASH_ENTRY(adr1, adr2));
613 } /* get_alias_relation_ex */
615 /* Free the relation cache. */
616 void mem_disambig_term(void) {
618 del_set(result_cache);
621 } /* mem_disambig_term */
624 * Check the mode of a Load/Store with the mode of the entity
626 * If the mode of the entity and the Load/Store mode do not match, we
627 * have the bad reinterpret case:
630 * char b = *(char *)&i;
632 * We do NOT count this as one value and return address_taken
634 * However, we support an often used case. If the mode is two-complement
635 * we allow casts between signed/unsigned.
637 * @param mode the mode of the Load/Store
638 * @param ent_mode the mode of the accessed entity
640 * @return non-zero if the Load/Store is a hidden cast, zero else
642 static int is_hidden_cast(ir_mode *mode, ir_mode *ent_mode) {
643 if (ent_mode != mode) {
644 if (ent_mode == NULL ||
645 get_mode_size_bits(ent_mode) != get_mode_size_bits(mode) ||
646 get_mode_sort(ent_mode) != get_mode_sort(mode) ||
647 get_mode_arithmetic(ent_mode) != irma_twos_complement ||
648 get_mode_arithmetic(mode) != irma_twos_complement)
652 } /* is_hidden_cast */
655 * Determine the address_taken state of a node (or it's successor Sels).
657 * @param irn the node
659 static ir_address_taken_state find_address_taken_state(ir_node *irn) {
661 ir_mode *emode, *mode;
665 for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
666 ir_node *succ = get_irn_out(irn, i);
668 switch (get_irn_opcode(succ)) {
670 /* check if this load is not a hidden conversion */
671 mode = get_Load_mode(succ);
672 ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
673 emode = get_type_mode(get_entity_type(ent));
674 if (is_hidden_cast(mode, emode))
675 return ir_address_taken;
679 /* check that the node is not the Store's value */
680 value = get_Store_value(succ);
682 return ir_address_taken;
683 /* check if this Store is not a hidden conversion */
684 mode = get_irn_mode(value);
685 ent = is_SymConst(irn) ? get_SymConst_entity(irn) : get_Sel_entity(irn);
686 emode = get_type_mode(get_entity_type(ent));
687 if (is_hidden_cast(mode, emode))
688 return ir_address_taken;
692 /* Check the successor of irn. */
693 ir_address_taken_state res = find_address_taken_state(succ);
694 if (res != ir_address_not_taken)
700 /* Only the call address is not an address taker but
701 this is an uninteresting case, so we ignore it here. */
702 return ir_address_taken;
705 /* another op, the address may be taken */
706 return ir_address_taken_unknown;
709 /* All successors finished, the address is not taken. */
710 return ir_address_not_taken;
711 } /* find_address_taken_state */
714 * Update the "address taken" flag of all frame entities.
716 static void analyse_irg_address_taken(ir_graph *irg) {
717 ir_type *ft = get_irg_frame_type(irg);
721 /* set initial state to not_taken, as this is the "smallest" state */
722 for (i = get_class_n_members(ft) - 1; i >= 0; --i) {
723 ir_entity *ent = get_class_member(ft, i);
725 set_entity_address_taken(ent, ir_address_not_taken);
728 assure_irg_outs(irg);
730 irg_frame = get_irg_frame(irg);
732 for (i = get_irn_n_outs(irg_frame) - 1; i >= 0; --i) {
733 ir_node *succ = get_irn_out(irg_frame, i);
734 ir_address_taken_state state;
737 ir_entity *ent = get_Sel_entity(succ);
739 if (get_entity_address_taken(ent) == ir_address_taken)
742 state = find_address_taken_state(succ);
743 if (state > get_entity_address_taken(ent))
744 set_entity_address_taken(ent, state);
748 irg->adr_taken_state = ir_address_taken_computed;
749 } /* analyse_address_taken */
751 /* Returns the current address taken state of the graph. */
752 ir_address_taken_computed_state get_irg_address_taken_state(const ir_graph *irg) {
753 return irg->adr_taken_state;
754 } /* get_irg_address_taken_state */
756 /* Sets the current address taken state of the graph. */
757 void set_irg_address_taken_state(ir_graph *irg, ir_address_taken_computed_state state) {
758 irg->adr_taken_state = state;
759 } /* set_irg_address_taken_state */
761 /* Assure that the address taken flag is computed for the given graph. */
762 void assure_irg_address_taken_computed(ir_graph *irg) {
763 if (irg->adr_taken_state == ir_address_taken_not_computed)
764 analyse_irg_address_taken(irg);
765 } /* assure_irg_address_taken_computed */
768 * Initialize the address_taken flag for a global type like type.
770 static void init_taken_flag(ir_type * tp) {
773 /* All external visible entities are at least
774 ir_address_taken_unknown. This is very conservative. */
775 for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
776 ir_entity *ent = get_compound_member(tp, i);
777 ir_address_taken_state state;
779 state = get_entity_visibility(ent) == visibility_external_visible ?
780 ir_address_taken_unknown : ir_address_not_taken ;
781 set_entity_address_taken(ent, state);
783 } /* init_taken_flag */
787 * Print the address taken state of all entities of a given type for debugging.
789 static void print_address_taken_state(ir_type *tp) {
791 for (i = get_compound_n_members(tp) - 1; i >= 0; --i) {
792 ir_entity *ent = get_compound_member(tp, i);
793 ir_address_taken_state state = get_entity_address_taken(ent);
795 if (state != ir_address_not_taken) {
796 assert(ir_address_not_taken <= state && state <= ir_address_taken);
797 ir_printf("%+F: %s\n", ent, get_address_taken_state_name(state));
800 } /* print_address_taken_state */
804 * Post-walker: check for global entity address
806 static void check_global_address(ir_node *irn, void *env) {
809 ir_address_taken_state state;
811 if (is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent) {
813 ent = get_SymConst_entity(irn);
814 } else if (is_Sel(irn) && get_Sel_ptr(irn) == tls) {
815 /* A TLS variable. */
816 ent = get_Sel_entity(irn);
820 if (get_entity_address_taken(ent) >= ir_address_taken) {
821 /* Already at the maximum. */
824 state = find_address_taken_state(irn);
825 if (state > get_entity_address_taken(ent))
826 set_entity_address_taken(ent, state);
827 } /* check_global_address */
830 * Update the "address taken" flag of all global entities.
832 static void analyse_irp_globals_address_taken(void) {
835 init_taken_flag(get_glob_type());
836 init_taken_flag(get_tls_type());
838 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
839 ir_graph *irg = get_irp_irg(i);
841 assure_irg_outs(irg);
842 irg_walk_graph(irg, NULL, check_global_address, get_irg_tls(irg));
844 //print_address_taken_state(get_glob_type());
845 //print_address_taken_state(get_tls_type());
848 irp->globals_adr_taken_state = ir_address_taken_computed;
849 } /* analyse_irp_globals_address_taken */
851 /* Returns the current address taken state of the globals. */
852 ir_address_taken_computed_state get_irp_globals_address_taken_state(void) {
853 return irp->globals_adr_taken_state;
854 } /* get_irp_globals_address_taken_state */
856 /* Sets the current address taken state of the graph. */
857 void set_irp_globals_address_taken_state(ir_address_taken_computed_state state) {
858 irp->globals_adr_taken_state = state;
859 } /* set_irg_address_taken_state */
861 /* Assure that the address taken flag is computed for the globals. */
862 void assure_irp_globals_address_taken_computed(void) {
863 if (irp->globals_adr_taken_state == ir_address_taken_not_computed)
864 analyse_irp_globals_address_taken();
865 } /* assure_irp_globals_address_taken_computed */