X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Firmemory.c;h=5d984df40ffcd4e5a134009d5b3da42cb1c98169;hb=34ba4cf5428e344224af2e4c31b2120cdd2fd12e;hp=4e9964c18f890b24e226a35749bd0ce2f4de3de1;hpb=8c413e48919baf494cd98c7f08bf085268d15698;p=libfirm diff --git a/ir/ana/irmemory.c b/ir/ana/irmemory.c index 4e9964c18..5d984df40 100644 --- a/ir/ana/irmemory.c +++ b/ir/ana/irmemory.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -51,6 +51,18 @@ static DISAMBIGUATOR_FUNC language_disambuigator = NULL; /** The global memory disambiguator options. */ static unsigned global_mem_disamgig_opt = aa_opt_no_opt; +/* Returns a human readable name for an alias relation. */ +const char *get_ir_alias_relation_name(ir_alias_relation rel) { +#define X(a) case a: return #a + switch (rel) { + X(no_alias); + X(may_alias); + X(sure_alias); + default: assert(0); return "UNKNOWN"; + } +#undef X +} + /* Get the memory disambiguator options for a graph. */ unsigned get_irg_memory_disambiguator_options(ir_graph *irg) { unsigned opt = irg->mem_disambig_opt; @@ -88,40 +100,6 @@ static ir_node *find_base_adr(ir_node *sel, ir_entity **pEnt) { return ptr; } /* find_base_adr */ -/** - * Check if the address can be decomposed into base PLUS offset. - */ -static int has_offset(ir_node *adr, int *offset) { - if (is_SymConst(adr)) { - *offset = 0; - return 1; - } - if (is_Sel(adr)) { - ir_entity *ent = get_Sel_entity(adr); - ir_type *owner = get_entity_owner(ent); - - if (get_type_state(owner) != layout_fixed) { - /* The layout is NOT fixed yet, symbolic evaluation needed */ - } - } - return 0; -} /* has_offset */ - -/** - * Two address expressions have the same base address, - * check if there offsets are different. - * - * @param adr1 The first address. - * @param adr2 The second address. - */ -static ir_alias_relation different_offsets(ir_node *adr1, ir_node *adr2) { - int offset1, offset2; - if (has_offset(adr1, &offset1) && has_offset(adr2, &offset2)) { - /* */ - } - return may_alias; -} /* different_offsets */ - /** * Check if a given Const node is greater or equal a given size. * @@ -132,7 +110,7 @@ static ir_alias_relation check_const(ir_node *cns, int size) { tarval *tv_size; if (size == 0) - return classify_tarval(tv) != TV_CLASSIFY_NULL ? no_alias : may_alias; + return tarval_is_null(tv) ? may_alias : no_alias; tv_size = new_tarval_from_long(size, get_tarval_mode(tv)); return tarval_cmp(tv_size, tv) & (pn_Cmp_Eq|pn_Cmp_Lt) ? no_alias : may_alias; } /* check_const */ @@ -152,10 +130,69 @@ static ir_alias_relation different_index(ir_node *idx1, ir_node *idx2, int size) tarval *tv1 = get_Const_tarval(idx1); tarval *tv2 = get_Const_tarval(idx2); tarval *tv, *tv_size; + ir_mode *m1, *m2; if (size == 0) return tv1 == tv2 ? sure_alias : no_alias; + /* arg, modes may be different */ + m1 = get_tarval_mode(tv1); + m2 = get_tarval_mode(tv2); + 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 */ + return may_alias; + } + 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 */ + return may_alias; + } + 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)) { + tarval *t = tv1; + ir_mode *tm = m1; + tv1 = tv2; m1 = m2; + tv2 = t; m2 = tm; + } + + /* m1 is now the signed one */ + if (tarval_cmp(tv1, get_tarval_null(m1)) & (pn_Cmp_Eq|pn_Cmp_Gt)) { + /* tv1 is signed, but >= 0, simply cast into unsigned */ + tv1 = tarval_convert_to(tv1, m2); + } else { + tv_size = new_tarval_from_long(size, m2); + + if (tarval_cmp(tv2, tv_size) & (pn_Cmp_Eq|pn_Cmp_Gt)) { + /* tv1 is negative and tv2 >= tv_size, so the difference is bigger than size */ + return no_alias; + } + /* tv_size > tv2, so we can subtract without overflow */ + tv2 = tarval_sub(tv_size, tv2); + + /* 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 */ + return tarval_cmp(tv1, tv2) & (pn_Cmp_Eq|pn_Cmp_Gt) ? no_alias : may_alias; + } + } + } if (tarval_cmp(tv1, tv2) == pn_Cmp_Gt) { tarval *t = tv1; tv1 = tv2; @@ -178,7 +215,7 @@ static ir_alias_relation different_index(ir_node *idx1, ir_node *idx2, int size) return check_const(r1, size); } if (is_Add(idx2)) { - /* both are Adds, check if they are of x + c kind */ + /* both are Adds, check if they are of x + a == x + b kind */ ir_node *l2 = get_Add_left(idx2); ir_node *r2 = get_Add_right(idx2); @@ -214,7 +251,7 @@ static ir_alias_relation different_index(ir_node *idx1, ir_node *idx2, int size) } if (is_Sub(idx2)) { - /* both are Subs, check if they are of x - c kind */ + /* both are Subs, check if they are of x - a == x - b kind */ ir_node *l2 = get_Sub_left(idx2); if (l1 == l2) { @@ -244,6 +281,8 @@ static ir_alias_relation different_index(ir_node *idx1, ir_node *idx2, int size) * @param adr2 The second address. */ static ir_alias_relation different_sel_offsets(ir_node *sel1, ir_node *sel2) { + /* seems to be broken */ +#if 0 ir_entity *ent1 = get_Sel_entity(sel1); ir_entity *ent2 = get_Sel_entity(sel2); int i, check_arr = 0; @@ -281,6 +320,7 @@ static ir_alias_relation different_sel_offsets(ir_node *sel1, ir_node *sel2) { return have_no > 0 ? no_alias : sure_alias; } } +#endif return may_alias; } /* different_sel_offsets */ @@ -295,12 +335,12 @@ static ir_alias_relation different_types(ir_node *adr1, ir_node *adr2) { ir_entity *ent1 = NULL, *ent2 = NULL; - if (is_SymConst(adr1) && get_SymConst_kind(adr1) == symconst_addr_ent) + if (is_SymConst_addr_ent(adr1)) ent1 = get_SymConst_entity(adr1); else if (is_Sel(adr1)) ent1 = get_Sel_entity(adr1); - if (is_SymConst(adr2) && get_SymConst_kind(adr2) == symconst_addr_ent) + if (is_SymConst_addr_ent(adr2)) ent2 = get_SymConst_entity(adr2); else if (is_Sel(adr2)) ent2 = get_Sel_entity(adr2); @@ -363,7 +403,7 @@ static ir_alias_relation _different_pointer(ir_node *adr1, ir_node *adr2, int si if (is_Add(adr1)) { /* first address is the result of a pointer addition */ ir_node *l1 = get_Add_left(adr1); - ir_node *r1 = get_Add_right(adr1); + ir_node *r1 = get_Add_right(adr1); if (l1 == adr2) { found = check_const_offset(r1, size); @@ -428,9 +468,11 @@ static int is_arg_Proj(ir_node *node) { /** * Returns true if an address represents a global variable. + * + * @param irn the node representing the address */ static INLINE int is_global_var(ir_node *irn) { - return is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent; + return is_SymConst_addr_ent(irn); } /* is_global_var */ /** @@ -459,7 +501,7 @@ static ir_alias_relation _get_alias_relation( /* Two save some code, sort the addresses by its id's. Beware, this might break some things, so better check here. */ - assert(iro_SymConst < iro_Sel && iro_Sel < iro_Proj && "Code dependence breaked"); + assert(iro_SymConst < iro_Sel && iro_Sel < iro_Proj && "Code dependence broken"); op1 = get_irn_opcode(adr1); op2 = get_irn_opcode(adr2); @@ -492,8 +534,6 @@ static ir_alias_relation _get_alias_relation( /* base2 address is a global var (R1 a) */ if (adr1 != base2) return no_alias; - else - return different_offsets(adr1, adr2); } else if (base2 == get_irg_frame(irg)) { /* the second one is a local variable so they are always different (R1 b) */ @@ -523,13 +563,15 @@ static ir_alias_relation _get_alias_relation( ir_node *base2 = find_base_adr(adr2, &ent2); if (base1 == base2) { - /* identical bases: check for different offsets */ - return different_sel_offsets(adr1, adr2); - } else if (base2 == get_irg_frame(irg)) { - /* both addresses are local variables and we know - they are different (R1 a) */ - if (ent1 != ent2) + /* identical bases: both are local variables */ + if (ent1 != ent2) { + /* both addresses are local variables and we know + they are different (R1 a) */ return no_alias; + } else { + /* same local var */ + return different_sel_offsets(adr1, adr2); + } } else if (base2 == get_irg_tls(irg)) { /* the second one is a TLS variable so they are always different (R1 d) */ @@ -550,16 +592,17 @@ static ir_alias_relation _get_alias_relation( ir_node *base2 = find_base_adr(adr2, &ent2); if (base1 == base2) - return different_sel_offsets(adr1, adr2); + if (ent1 != ent2) { + /* both addresses are tls variables and we know + they are different (R1 a) */ + } else { + /* same tls var */ + return different_sel_offsets(adr1, adr2); + } else if (base2 == get_irg_frame(irg)) { - /* the second one is a local variable so they are always - different (R1 d) */ + /* the first one is a tls variable, the second a local one, + they are different (R1 d) */ return no_alias; - } else if (base2 == get_irg_tls(irg)) { - /* both addresses are TLS variables and we know - they are different (R1 a) */ - if (ent1 != ent2) - return no_alias; } } } else if (is_arg_Proj(base1)) { @@ -581,8 +624,10 @@ static ir_alias_relation _get_alias_relation( /* the second address is a Sel */ ir_node *base2 = find_base_adr(adr2, &ent2); - if (base1 == base2) + if (base1 == base2) { + /* same global var */ return different_sel_offsets(adr1, adr2); + } else if (base2 == get_irg_frame(irg)) { /* the second one is a local variable so they are always different (R1 a) */ @@ -628,6 +673,10 @@ static ir_alias_relation _get_alias_relation( if (get_mode_size_bits(mode1) != get_mode_size_bits(mode2)) return no_alias; + /* cheap test: if only one is a reference mode, no alias */ + if (mode_is_reference(mode1) != mode_is_reference(mode2)) + return no_alias; + /* try rule R5 */ rel = different_types(adr1, adr2); if (rel != may_alias) @@ -655,6 +704,7 @@ ir_alias_relation get_alias_relation( ir_node *adr2, ir_mode *mode2) { ir_alias_relation rel = _get_alias_relation(irg, adr1, mode1, adr2, mode2); + DB((dbg, LEVEL_1, "alias(%+F, %+f) = %s\n", adr1, adr2, get_ir_alias_relation_name(rel))); return rel; } /* get_alias_relation */ @@ -881,6 +931,7 @@ void assure_irg_address_taken_computed(ir_graph *irg) { analyse_irg_address_taken(irg); } /* assure_irg_address_taken_computed */ + /** * Initialize the address_taken flag for a global type like type. */ @@ -899,6 +950,56 @@ static void init_taken_flag(ir_type * tp) { } } /* init_taken_flag */ +/** + * Mark all entities used in the initializer for the given entity as address taken + */ +static void check_initializer(ir_entity *ent) { + ir_node *n; + int i; + + /* do not check uninitialized values */ + if (get_entity_variability(ent) == variability_uninitialized) + return; + + /* Beware: Methods initialized with "themself". This does not count as a taken + address. */ + if (is_Method_type(get_entity_type(ent))) + return; + + if (is_atomic_entity(ent)) { + /* let's check if it's an address */ + n = get_atomic_ent_value(ent); + if (is_SymConst_addr_ent(n)) { + ir_entity *ent = get_SymConst_entity(n); + set_entity_address_taken(ent, ir_address_taken); + } + } else { + for (i = get_compound_ent_n_values(ent) - 1; i >= 0; --i) { + n = get_compound_ent_value(ent, i); + + /* let's check if it's an address */ + if (is_SymConst_addr_ent(n)) { + ir_entity *ent = get_SymConst_entity(n); + set_entity_address_taken(ent, ir_address_taken); + } + } + } +} /* check_initializer */ + + +/** + * Mark all entities used in initializers as address taken + */ +static void check_initializers(ir_type *tp) { + int i; + + for (i = get_compound_n_members(tp) - 1; i >= 0; --i) { + ir_entity *ent = get_compound_member(tp, i); + + check_initializer(ent); + } +} /* check_initializers */ + #ifdef DEBUG_libfirm /** * Print the address taken state of all entities of a given type for debugging. @@ -925,7 +1026,7 @@ static void check_global_address(ir_node *irn, void *env) { ir_entity *ent; ir_address_taken_state state; - if (is_SymConst(irn) && get_SymConst_kind(irn) == symconst_addr_ent) { + if (is_SymConst_addr_ent(irn)) { /* A global. */ ent = get_SymConst_entity(irn); } else if (is_Sel(irn) && get_Sel_ptr(irn) == tls) { @@ -954,6 +1055,9 @@ static void analyse_irp_globals_address_taken(void) { init_taken_flag(get_glob_type()); init_taken_flag(get_tls_type()); + check_initializers(get_glob_type()); + check_initializers(get_tls_type()); + for (i = get_irp_n_irgs() - 1; i >= 0; --i) { ir_graph *irg = get_irp_irg(i); @@ -989,12 +1093,39 @@ void assure_irp_globals_address_taken_computed(void) { } /* assure_irp_globals_address_taken_computed */ +#include +#include "typerep.h" + DEBUG_ONLY(static firm_dbg_module_t *dbgcall = NULL;) +/** Maps method types to cloned method types. */ +static pmap *mtp_map; + +/** + * Clone a method type if not already cloned. + */ +static ir_type *clone_type_and_cache(ir_type *tp) { + static ident *prefix = NULL; + ir_type *res; + pmap_entry *e = pmap_find(mtp_map, tp); + + if (e) + return e->value; + + if (prefix == NULL) + prefix = new_id_from_chars("C", 1); + + res = clone_type_method(tp, prefix); + pmap_insert(mtp_map, tp, res); + DB((dbgcall, LEVEL_2, "cloned type %+F into %+F\n", tp, res)); + + return res; +} /* clone_type_and_cache */ + /** * Copy the calling conventions from the entities to the call type. */ -static void update_calls(ir_node *call, void *env) { +static void update_calls_to_private(ir_node *call, void *env) { (void) env; if (is_Call(call)) { ir_node *ptr = get_Call_ptr(call); @@ -1003,13 +1134,17 @@ static void update_calls(ir_node *call, void *env) { ir_entity *ent = get_SymConst_entity(ptr); ir_type *ctp = get_Call_type(call); - if (get_method_additional_properties(ctp) & mtp_property_private) { - set_method_additional_property(ctp, mtp_property_private); - DB((dbgcall, LEVEL_1, "changed call to private method %+F\n", ent)); + if (get_entity_additional_properties(ent) & mtp_property_private) { + if ((get_method_additional_properties(ctp) & mtp_property_private) == 0) { + ctp = clone_type_and_cache(ctp); + set_method_additional_property(ctp, mtp_property_private); + set_Call_type(call, ctp); + DB((dbgcall, LEVEL_1, "changed call to private method %+F\n", ent)); + } } } } -} +} /* update_calls_to_private */ /* Mark all private methods, i.e. those of which all call sites are known. */ void mark_private_methods(void) { @@ -1020,6 +1155,8 @@ void mark_private_methods(void) { assure_irp_globals_address_taken_computed(); + mtp_map = pmap_create(); + /* first step: change the calling conventions of the local non-escaped entities */ for (i = get_irp_n_irgs() - 1; i >= 0; --i) { ir_graph *irg = get_irp_irg(i); @@ -1030,12 +1167,20 @@ void mark_private_methods(void) { state == ir_address_not_taken) { ir_type *mtp = get_entity_type(ent); - set_method_additional_property(mtp, mtp_property_private); - changed = 1; + set_entity_additional_property(ent, mtp_property_private); DB((dbgcall, LEVEL_1, "found private method %+F\n", ent)); + if ((get_method_additional_properties(mtp) & mtp_property_private) == 0) { + /* need a new type */ + mtp = clone_type_and_cache(mtp); + set_entity_type(ent, mtp); + set_method_additional_property(mtp, mtp_property_private); + changed = 1; + } } } if (changed) - all_irg_walk(NULL, update_calls, NULL); -} + all_irg_walk(NULL, update_calls_to_private, NULL); + + pmap_destroy(mtp_map); +} /* mark_private_methods */