/* * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * * This file may be distributed and/or modified under the terms of the * GNU General Public License version 2 as published by the Free Software * Foundation and appearing in the file LICENSE.GPL included in the * packaging of this file. * * Licensees holding valid libFirm Professional Edition licenses may use * this file in accordance with the libFirm Commercial License. * Agreement provided with the Software. * * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE. */ /** * @file * @brief Dataflow driven Load/Store optimizations, uses some ideas from * VanDrunen's LEPRE * @author Michael Beck */ #include "config.h" #include "irnode_t.h" #include "irflag_t.h" #include "array_t.h" #include "ircons.h" #include "irdom.h" #include "irgmod.h" #include "irgwalk.h" #include "irouts.h" #include "irgraph.h" #include "irgopt.h" #include "iropt.h" #include "iroptimize.h" #include "irnodehashmap.h" #include "raw_bitset.h" #include "debug.h" #include "error.h" #include "irpass.h" /* maximum number of output Proj's */ #define MAX_PROJ ((long)pn_Load_max > (long)pn_Store_max ? (long)pn_Load_max : (long)pn_Store_max) /** * Mapping an address to an dense ID. */ typedef struct address_entry_t { unsigned id; /**< The ID */ } address_entry; /** * Memop-flags. */ enum memop_flags { FLAG_KILL_ALL = 1, /**< KILL all addresses */ FLAG_KILLED_NODE = 2, /**< this node was killed */ FLAG_EXCEPTION = 4, /**< this node has exception flow */ FLAG_IGNORE = 8, /**< ignore this node (volatile or other) */ }; /** * A value: This represents a value stored at a given address in * memory. Do not confuse with values from value numbering. */ typedef struct value_t value_t; struct value_t { ir_node *address; /**< the address of this value */ ir_node *value; /**< the value itself */ ir_mode *mode; /**< the mode of the value */ unsigned id; /**< address id */ }; /** * A memop describes an memory-related operation. * These are Loads/Store and all other ops that might modify * memory (Calls, CopyB) or causing exceptions. */ typedef struct memop_t memop_t; struct memop_t { value_t value; /**< the value of this memop: only defined for Load/Store */ ir_node *node; /**< the memory op itself */ ir_node *mem; /**< the memory FROM this node */ ir_node *replace; /**< the replacement node if this memop is replaced */ memop_t *next; /**< links to the next memory op in the block in forward order. */ memop_t *prev; /**< links to the previous memory op in the block in forward order. */ unsigned flags; /**< memop flags */ ir_node *projs[MAX_PROJ+1]; /**< Projs of this memory op */ }; /** * Additional data for every basic block. */ typedef struct block_t block_t; struct block_t { memop_t *memop_forward; /**< topologically sorted list of memory ops in this block */ memop_t *memop_backward; /**< last memop in the list */ unsigned *avail_out; /**< out-set of available addresses */ memop_t **id_2_memop_avail; /**< maps avail address ids to memops */ unsigned *anticL_in; /**< in-set of anticipated Load addresses */ memop_t **id_2_memop_antic; /**< maps anticipated address ids to memops */ ir_node *block; /**< the associated block */ block_t *forward_next; /**< next block entry for forward iteration */ block_t *backward_next; /**< next block entry for backward iteration */ memop_t *avail; /**< used locally for the avail map */ memop_t **trans_results; /**< used to cached translated nodes due antic calculation. */ }; /** * Metadata for this pass. */ typedef struct ldst_env_t { struct obstack obst; /**< obstack for temporary data */ ir_nodehashmap_t adr_map; /**< Map addresses to */ block_t *forward; /**< Inverse post-order list of all blocks Start->End */ block_t *backward; /**< Inverse post-order list of all blocks End->Start */ ir_node *start_bl; /**< start block of the current graph */ ir_node *end_bl; /**< end block of the current graph */ unsigned *curr_set; /**< current set of addresses */ memop_t **curr_id_2_memop; /**< current map of address ids to memops */ unsigned curr_adr_id; /**< number for address mapping */ unsigned n_mem_ops; /**< number of memory operations (Loads/Stores) */ size_t rbs_size; /**< size of all bitsets in bytes */ int max_cfg_preds; /**< maximum number of block cfg predecessors */ int changed; /**< Flags for changed graph state */ #ifdef DEBUG_libfirm ir_node **id_2_address; /**< maps an id to the used address */ #endif } ldst_env; /* the one and only environment */ static ldst_env env; #ifdef DEBUG_libfirm static firm_dbg_module_t *dbg; /** * Dumps the block list. * * @param ldst environment */ static void dump_block_list(ldst_env *env) { block_t *entry; memop_t *op; int i; for (entry = env->forward; entry != NULL; entry = entry->forward_next) { DB((dbg, LEVEL_2, "%+F {", entry->block)); i = 0; for (op = entry->memop_forward; op != NULL; op = op->next) { if (i == 0) { DB((dbg, LEVEL_2, "\n\t")); } DB((dbg, LEVEL_2, "%+F", op->node)); if ((op->flags & FLAG_KILL_ALL) == FLAG_KILL_ALL) DB((dbg, LEVEL_2, "X")); else if (op->flags & FLAG_KILL_ALL) DB((dbg, LEVEL_2, "K")); DB((dbg, LEVEL_2, ", ")); i = (i + 1) & 3; } DB((dbg, LEVEL_2, "\n}\n\n")); } } /* dump_block_list */ /** * Dumps the current set. * * @param bl current block * @param s name of the set */ static void dump_curr(block_t *bl, const char *s) { size_t end = env.rbs_size - 1; size_t pos; int i; DB((dbg, LEVEL_2, "%s[%+F] = {", s, bl->block)); i = 0; for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) { memop_t *op = env.curr_id_2_memop[pos]; if (i == 0) { DB((dbg, LEVEL_2, "\n\t")); } DB((dbg, LEVEL_2, "<%+F, %+F>, ", op->value.address, op->value.value)); i = (i + 1) & 3; } DB((dbg, LEVEL_2, "\n}\n")); } /* dump_curr */ #else static void dump_block_list(ldst_env *env) { (void) env; } static void dump_curr(block_t *bl, const char *s) { (void) bl; (void) s; } #endif /* DEBUG_libfirm */ /** Get the block entry for a block node */ static block_t *get_block_entry(const ir_node *block) { assert(is_Block(block)); return (block_t*)get_irn_link(block); } /* get_block_entry */ /** Get the memop entry for a memory operation node */ static memop_t *get_irn_memop(const ir_node *irn) { assert(! is_Block(irn)); return (memop_t*)get_irn_link(irn); } /* get_irn_memop */ /** * Walk over the memory edges from definition to users. * This ensures, that even operation without memory output are found. * * @param irn start node * @param pre pre walker function * @param post post walker function * @param ctx context parameter for the walker functions */ static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx) { ir_mode *mode; mark_irn_visited(irn); if (pre) pre(irn, ctx); mode = get_irn_mode(irn); if (mode == mode_M) { /* every successor uses memory */ for (unsigned i = get_irn_n_outs(irn); i-- > 0; ) { ir_node *succ = get_irn_out(irn, i); if (! irn_visited(succ)) walk_memory(succ, pre, post, ctx); } } else if (mode == mode_T) { /* only some Proj's uses memory */ for (unsigned i = get_irn_n_outs(irn); i-- > 0; ) { ir_node *proj = get_irn_out(irn, i); if (get_irn_mode(proj) == mode_M && ! irn_visited(proj)) walk_memory(proj, pre, post, ctx); } } if (post) post(irn, ctx); } /* walk_memory */ /** * Walks over all memory nodes of a graph. * * @param irg a graph * @param pre pre walker function * @param post post walker function * @param ctx context parameter for the walker functions */ static void walk_memory_irg(ir_graph *irg, irg_walk_func pre, irg_walk_func post, void *ctx) { inc_irg_visited(irg); ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); /* * there are two possible sources for memory: initial_mem and nomem * we ignore nomem as this should NOT change the memory */ walk_memory(get_irg_initial_mem(irg), pre, post, ctx); ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); } /* walk_memory_irg */ /** * Register an address and allocate a (sparse, 0..n) ID for it. * * @param adr the IR-node representing the address * * @return the allocated id */ static unsigned register_address(ir_node *adr) { address_entry *entry; /* skip Confirms and Casts */ restart: if (is_Confirm(adr)) { adr = get_Confirm_value(adr); goto restart; } if (is_Cast(adr)) { adr = get_Cast_op(adr); goto restart; } entry = ir_nodehashmap_get(address_entry, &env.adr_map, adr); if (entry == NULL) { /* new address */ entry = OALLOC(&env.obst, address_entry); entry->id = env.curr_adr_id++; ir_nodehashmap_insert(&env.adr_map, adr, entry); DB((dbg, LEVEL_3, "ADDRESS %+F has ID %u\n", adr, entry->id)); #ifdef DEBUG_libfirm ARR_APP1(ir_node *, env.id_2_address, adr); #endif } return entry->id; } /* register_address */ /** * translate an address through a Phi node into a given predecessor * block. * * @param address the address * @param block the block * @param pos the position of the predecessor in block */ static ir_node *phi_translate(ir_node *address, const ir_node *block, int pos) { if (is_Phi(address) && get_nodes_block(address) == block) address = get_Phi_pred(address, pos); return address; } /* phi_translate */ /** * Walker: allocate an block entry for every block * and register all potential addresses. */ static void prepare_blocks(ir_node *irn, void *ctx) { (void)ctx; if (is_Block(irn)) { block_t *entry = OALLOC(&env.obst, block_t); int n; entry->memop_forward = NULL; entry->memop_backward = NULL; entry->avail_out = NULL; entry->id_2_memop_avail = NULL; entry->anticL_in = NULL; entry->id_2_memop_antic = NULL; entry->block = irn; entry->forward_next = NULL; entry->backward_next = NULL; entry->avail = NULL; entry->trans_results = NULL; set_irn_link(irn, entry); set_Block_phis(irn, NULL); /* use block marks to track unreachable blocks */ set_Block_mark(irn, 0); n = get_Block_n_cfgpreds(irn); if (n > env.max_cfg_preds) env.max_cfg_preds = n; } else { ir_mode *mode = get_irn_mode(irn); if (mode_is_reference(mode)) { /* * Register ALL possible addresses: this is overkill yet but * simpler then doing it for all possible translated addresses * (which would be sufficient in the moment. */ (void)register_address(irn); } } } /* prepare_blocks */ /** * Post-Walker, link in all Phi's */ static void link_phis(ir_node *irn, void *ctx) { (void)ctx; if (is_Phi(irn)) { ir_node *block = get_nodes_block(irn); add_Block_phi(block, irn); } } /* link_phis */ /** * Block walker: creates the inverse post-order list for the CFG. */ static void inverse_post_order(ir_node *block, void *ctx) { block_t *entry = get_block_entry(block); (void)ctx; /* mark this block IS reachable from start */ set_Block_mark(block, 1); /* create the list in inverse order */ entry->forward_next = env.forward; env.forward = entry; /* remember the first visited (last in list) entry, needed for later */ if (env.backward == NULL) env.backward = entry; } /* inverse_post_order */ /** * Block walker: create backward links for the memops of a block. */ static void collect_backward(ir_node *block, void *ctx) { block_t *entry = get_block_entry(block); memop_t *last, *op; (void)ctx; /* * Do NOT link in the end block yet. We want it to be * the first in the list. This is NOT guaranteed by the walker * if we have endless loops. */ if (block != env.end_bl) { entry->backward_next = env.backward; /* create the list in inverse order */ env.backward = entry; } /* create backward links for all memory ops */ last = NULL; for (op = entry->memop_forward; op != NULL; op = op->next) { op->prev = last; last = op; } entry->memop_backward = last; } /* collect_backward */ /** * Allocate a memop. * * @param irn the IR-node representing the memop or NULL * if this is a translated (virtual) memop * * @return the allocated memop */ static memop_t *alloc_memop(ir_node *irn) { memop_t *m = OALLOC(&env.obst, memop_t); m->value.address = NULL; m->value.value = NULL; m->value.mode = NULL; m->node = irn; m->mem = NULL; m->replace = NULL; m->next = NULL; m->flags = 0; memset(m->projs, 0, sizeof(m->projs)); if (irn != NULL) set_irn_link(irn, m); return m; } /* alloc_memop */ /** * Create a memop for a Phi-replacement. * * @param op the memop to clone * @param phi the Phi-node representing the new value */ static memop_t *clone_memop_phi(memop_t *op, ir_node *phi) { memop_t *m = OALLOC(&env.obst, memop_t); m->value = op->value; m->value.value = phi; m->node = phi; m->replace = NULL; m->next = NULL; m->flags = 0; set_irn_link(phi, m); return m; } /* clone_memop_phi */ /** * Return the memory properties of a call node. * * @param call the call node * * return a bitset of mtp_property_const and mtp_property_pure */ static unsigned get_Call_memory_properties(ir_node *call) { ir_type *call_tp = get_Call_type(call); unsigned prop = get_method_additional_properties(call_tp); /* check first the call type */ if ((prop & (mtp_property_const|mtp_property_pure)) == 0) { /* try the called entity */ ir_node *ptr = get_Call_ptr(call); if (is_SymConst_addr_ent(ptr)) { ir_entity *ent = get_SymConst_entity(ptr); prop = get_entity_additional_properties(ent); } } return prop & (mtp_property_const|mtp_property_pure); } /* get_Call_memory_properties */ /** * Returns an entity if the address ptr points to a constant one. * * @param ptr the address * * @return an entity or NULL */ static ir_entity *find_constant_entity(ir_node *ptr) { for (;;) { if (is_SymConst(ptr) && get_SymConst_kind(ptr) == symconst_addr_ent) { return get_SymConst_entity(ptr); } else if (is_Sel(ptr)) { ir_entity *ent = get_Sel_entity(ptr); ir_type *tp = get_entity_owner(ent); /* Do not fiddle with polymorphism. */ if (is_Class_type(get_entity_owner(ent)) && ((get_entity_n_overwrites(ent) != 0) || (get_entity_n_overwrittenby(ent) != 0) ) ) return NULL; if (is_Array_type(tp)) { /* check bounds */ int i, n; for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) { ir_node *bound; ir_tarval *tlower, *tupper; ir_node *index = get_Sel_index(ptr, i); ir_tarval *tv = computed_value(index); /* check if the index is constant */ if (tv == tarval_bad) return NULL; bound = get_array_lower_bound(tp, i); tlower = computed_value(bound); bound = get_array_upper_bound(tp, i); tupper = computed_value(bound); if (tlower == tarval_bad || tupper == tarval_bad) return NULL; if (tarval_cmp(tv, tlower) == ir_relation_less) return NULL; if (tarval_cmp(tupper, tv) == ir_relation_less) return NULL; /* ok, bounds check finished */ } } if (get_entity_linkage(ent) == IR_LINKAGE_CONSTANT) return ent; /* try next */ ptr = get_Sel_ptr(ptr); } else if (is_Add(ptr)) { ir_node *l = get_Add_left(ptr); ir_node *r = get_Add_right(ptr); if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r)) ptr = l; else if (get_irn_mode(r) == get_irn_mode(ptr) && is_Const(l)) ptr = r; else return NULL; /* for now, we support only one addition, reassoc should fold all others */ if (! is_SymConst(ptr) && !is_Sel(ptr)) return NULL; } else if (is_Sub(ptr)) { ir_node *l = get_Sub_left(ptr); ir_node *r = get_Sub_right(ptr); if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r)) ptr = l; else return NULL; /* for now, we support only one subtraction, reassoc should fold all others */ if (! is_SymConst(ptr) && !is_Sel(ptr)) return NULL; } else return NULL; } } /* find_constant_entity */ /** * Return the Selection index of a Sel node from dimension n */ static long get_Sel_array_index_long(ir_node *n, int dim) { ir_node *index = get_Sel_index(n, dim); assert(is_Const(index)); return get_tarval_long(get_Const_tarval(index)); } /* get_Sel_array_index_long */ typedef struct path_entry { ir_entity *ent; struct path_entry *next; size_t index; } path_entry; static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next) { path_entry entry, *p; ir_entity *ent, *field; ir_initializer_t *initializer; ir_tarval *tv; ir_type *tp; size_t n; entry.next = next; if (is_SymConst(ptr)) { /* found the root */ ent = get_SymConst_entity(ptr); initializer = get_entity_initializer(ent); for (p = next; p != NULL;) { if (initializer->kind != IR_INITIALIZER_COMPOUND) return NULL; n = get_initializer_compound_n_entries(initializer); tp = get_entity_type(ent); if (is_Array_type(tp)) { ent = get_array_element_entity(tp); if (ent != p->ent) { /* a missing [0] */ if (0 >= n) return NULL; initializer = get_initializer_compound_value(initializer, 0); continue; } } if (p->index >= n) return NULL; initializer = get_initializer_compound_value(initializer, p->index); ent = p->ent; p = p->next; } tp = get_entity_type(ent); while (is_Array_type(tp)) { ent = get_array_element_entity(tp); tp = get_entity_type(ent); /* a missing [0] */ n = get_initializer_compound_n_entries(initializer); if (0 >= n) return NULL; initializer = get_initializer_compound_value(initializer, 0); } switch (initializer->kind) { case IR_INITIALIZER_CONST: return get_initializer_const_value(initializer); case IR_INITIALIZER_TARVAL: case IR_INITIALIZER_NULL: default: return NULL; } } else if (is_Sel(ptr)) { entry.ent = field = get_Sel_entity(ptr); tp = get_entity_owner(field); if (is_Array_type(tp)) { assert(get_Sel_n_indexs(ptr) == 1 && "multi dim arrays not implemented"); entry.index = get_Sel_array_index_long(ptr, 0) - get_array_lower_bound_int(tp, 0); } else { size_t i, n_members = get_compound_n_members(tp); for (i = 0; i < n_members; ++i) { if (get_compound_member(tp, i) == field) break; } if (i >= n_members) { /* not found: should NOT happen */ return NULL; } entry.index = i; } return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry); } else if (is_Add(ptr)) { ir_mode *mode; unsigned pos; { ir_node *l = get_Add_left(ptr); ir_node *r = get_Add_right(ptr); if (is_Const(r)) { ptr = l; tv = get_Const_tarval(r); } else { ptr = r; tv = get_Const_tarval(l); } } ptr_arith: mode = get_tarval_mode(tv); /* ptr must be a Sel or a SymConst, this was checked in find_constant_entity() */ if (is_Sel(ptr)) { field = get_Sel_entity(ptr); } else { field = get_SymConst_entity(ptr); } /* count needed entries */ pos = 0; for (ent = field;;) { tp = get_entity_type(ent); if (! is_Array_type(tp)) break; ent = get_array_element_entity(tp); ++pos; } /* should be at least ONE entry */ if (pos == 0) return NULL; /* allocate the right number of entries */ NEW_ARR_A(path_entry, p, pos); /* fill them up */ pos = 0; for (ent = field;;) { unsigned size; ir_tarval *sz, *tv_index, *tlower, *tupper; size_t index; ir_node *bound; tp = get_entity_type(ent); if (! is_Array_type(tp)) break; ent = get_array_element_entity(tp); p[pos].ent = ent; p[pos].next = &p[pos + 1]; size = get_type_size_bytes(get_entity_type(ent)); sz = new_tarval_from_long(size, mode); tv_index = tarval_div(tv, sz); tv = tarval_mod(tv, sz); if (tv_index == tarval_bad || tv == tarval_bad) return NULL; assert(get_array_n_dimensions(tp) == 1 && "multiarrays not implemented"); bound = get_array_lower_bound(tp, 0); tlower = computed_value(bound); bound = get_array_upper_bound(tp, 0); tupper = computed_value(bound); if (tlower == tarval_bad || tupper == tarval_bad) return NULL; if (tarval_cmp(tv_index, tlower) == ir_relation_less) return NULL; if (tarval_cmp(tupper, tv_index) == ir_relation_less) return NULL; /* ok, bounds check finished */ index = get_tarval_long(tv_index); p[pos].index = index; ++pos; } if (! tarval_is_null(tv)) { /* hmm, wrong access */ return NULL; } p[pos - 1].next = next; return rec_find_compound_ent_value(ptr, p); } else if (is_Sub(ptr)) { ir_node *l = get_Sub_left(ptr); ir_node *r = get_Sub_right(ptr); ptr = l; tv = get_Const_tarval(r); tv = tarval_neg(tv); goto ptr_arith; } return NULL; } /* rec_find_compound_ent_value */ static ir_node *find_compound_ent_value(ir_node *ptr) { return rec_find_compound_ent_value(ptr, NULL); } /* find_compound_ent_value */ /** * Mark a Load memop to be replace by a definition * * @param op the Load memop */ static void mark_replace_load(memop_t *op, ir_node *def) { op->replace = def; op->flags |= FLAG_KILLED_NODE; env.changed = 1; } /* mark_replace_load */ /** * Mark a Store memop to be removed. * * @param op the Store memop */ static void mark_remove_store(memop_t *op) { op->flags |= FLAG_KILLED_NODE; env.changed = 1; } /* mark_remove_store */ /** * Update a memop for a Load. * * @param m the memop */ static void update_Load_memop(memop_t *m) { ir_node *load = m->node; ir_node *ptr; ir_entity *ent; if (get_Load_volatility(load) == volatility_is_volatile) m->flags |= FLAG_IGNORE; ptr = get_Load_ptr(load); m->value.address = ptr; for (unsigned i = get_irn_n_outs(load); i-- > 0; ) { ir_node *proj = get_irn_out(load, i); long pn; /* beware of keep edges */ if (is_End(proj)) continue; pn = get_Proj_proj(proj); m->projs[pn] = proj; switch (pn) { case pn_Load_res: m->value.value = proj; m->value.mode = get_irn_mode(proj); break; case pn_Load_X_except: m->flags |= FLAG_EXCEPTION; break; case pn_Load_M: m->mem = proj; break; case pn_Load_X_regular: break; default: panic("Unsupported Proj from Load %+F", proj); } } /* check if we can determine the entity that will be loaded */ ent = find_constant_entity(ptr); if (ent != NULL && get_entity_visibility(ent) != ir_visibility_external) { /* a static allocation that is not external: there should be NO exception * when loading even if we cannot replace the load itself. */ ir_node *value = NULL; /* no exception, clear the m fields as it might be checked later again */ if (m->projs[pn_Load_X_except]) { ir_graph *irg = get_irn_irg(ptr); exchange(m->projs[pn_Load_X_except], new_r_Bad(irg, mode_X)); m->projs[pn_Load_X_except] = NULL; m->flags &= ~FLAG_EXCEPTION; env.changed = 1; } if (m->projs[pn_Load_X_regular]) { exchange(m->projs[pn_Load_X_regular], new_r_Jmp(get_nodes_block(load))); m->projs[pn_Load_X_regular] = NULL; env.changed = 1; } if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT) { if (ent->initializer) { /* new style initializer */ value = find_compound_ent_value(ptr); } if (value != NULL) value = can_replace_load_by_const(load, value); } if (value != NULL) { /* we completely replace the load by this value */ DB((dbg, LEVEL_1, "Replacing Load %+F by constant %+F\n", m->node, value)); mark_replace_load(m, value); return; } } if (m->value.value != NULL && !(m->flags & FLAG_IGNORE)) { /* only create an address if this node is NOT killed immediately or ignored */ m->value.id = register_address(ptr); ++env.n_mem_ops; } else { /* no user, KILL it */ mark_replace_load(m, NULL); } } /* update_Load_memop */ /** * Update a memop for a Store. * * @param m the memop */ static void update_Store_memop(memop_t *m) { ir_node *store = m->node; ir_node *adr = get_Store_ptr(store); if (get_Store_volatility(store) == volatility_is_volatile) { m->flags |= FLAG_IGNORE; } else { /* only create an address if this node is NOT ignored */ m->value.id = register_address(adr); ++env.n_mem_ops; } m->value.address = adr; for (unsigned i = get_irn_n_outs(store); i-- > 0; ) { ir_node *proj = get_irn_out(store, i); long pn; /* beware of keep edges */ if (is_End(proj)) continue; pn = get_Proj_proj(proj); m->projs[pn] = proj; switch (pn) { case pn_Store_X_except: m->flags |= FLAG_EXCEPTION; break; case pn_Store_M: m->mem = proj; break; case pn_Store_X_regular: break; default: panic("Unsupported Proj from Store %+F", proj); } } m->value.value = get_Store_value(store); m->value.mode = get_irn_mode(m->value.value); } /* update_Store_memop */ /** * Update a memop for a Call. * * @param m the memop */ static void update_Call_memop(memop_t *m) { ir_node *call = m->node; unsigned prop = get_Call_memory_properties(call); if (prop & mtp_property_const) { /* A constant call did NOT use memory at all, we can kick it from the list. */ } else if (prop & mtp_property_pure) { /* pure calls READ memory */ m->flags = 0; } else m->flags = FLAG_KILL_ALL; for (unsigned i = get_irn_n_outs(call); i-- > 0; ) { ir_node *proj = get_irn_out(call, i); /* beware of keep edges */ if (is_End(proj)) continue; switch (get_Proj_proj(proj)) { case pn_Call_X_except: m->flags |= FLAG_EXCEPTION; break; case pn_Call_M: m->mem = proj; break; } } } /* update_Call_memop */ /** * Update a memop for a Div/Mod. * * @param m the memop */ static void update_Div_memop(memop_t *m) { ir_node *div = m->node; for (unsigned i = get_irn_n_outs(div); i-- > 0; ) { ir_node *proj = get_irn_out(div, i); /* beware of keep edges */ if (is_End(proj)) continue; switch (get_Proj_proj(proj)) { case pn_Div_X_except: m->flags |= FLAG_EXCEPTION; break; case pn_Div_M: m->mem = proj; break; } } } static void update_Mod_memop(memop_t *m) { ir_node *div = m->node; for (unsigned i = get_irn_n_outs(div); i-- > 0; ) { ir_node *proj = get_irn_out(div, i); /* beware of keep edges */ if (is_End(proj)) continue; switch (get_Proj_proj(proj)) { case pn_Mod_X_except: m->flags |= FLAG_EXCEPTION; break; case pn_Mod_M: m->mem = proj; break; } } } /** * Update a memop for a Phi. * * @param m the memop */ static void update_Phi_memop(memop_t *m) { /* the Phi is its own mem */ m->mem = m->node; } /* update_Phi_memop */ /** * Memory walker: collect all memory ops and build topological lists. */ static void collect_memops(ir_node *irn, void *ctx) { memop_t *op; ir_node *block; block_t *entry; (void) ctx; if (is_Proj(irn)) { /* we can safely ignore ProjM's except the initial memory */ ir_graph *irg = get_irn_irg(irn); if (irn != get_irg_initial_mem(irg)) return; } op = alloc_memop(irn); block = get_nodes_block(irn); entry = get_block_entry(block); if (is_Phi(irn)) { update_Phi_memop(op); /* Phis must be always placed first */ op->next = entry->memop_forward; entry->memop_forward = op; if (entry->memop_backward == NULL) entry->memop_backward = op; } else { switch (get_irn_opcode(irn)) { case iro_Load: update_Load_memop(op); break; case iro_Store: update_Store_memop(op); break; case iro_Call: update_Call_memop(op); break; case iro_Sync: case iro_Pin: op->mem = irn; break; case iro_Proj: /* initial memory */ op->mem = irn; break; case iro_Return: case iro_End: /* we can those to find the memory edge */ break; case iro_Div: update_Div_memop(op); break; case iro_Mod: update_Mod_memop(op); break; case iro_Builtin: /* TODO: handle some builtins */ default: /* unsupported operation */ op->flags = FLAG_KILL_ALL; } /* all other should be placed last */ if (entry->memop_backward == NULL) { entry->memop_forward = entry->memop_backward = op; } else { entry->memop_backward->next = op; entry->memop_backward = op; } } } /* collect_memops */ /** * Find an address in the current set. * * @param value the value to be searched for * * @return a memop for the value or NULL if the value does * not exists in the set or cannot be converted into * the requested mode */ static memop_t *find_address(const value_t *value) { if (rbitset_is_set(env.curr_set, value->id)) { memop_t *res = env.curr_id_2_memop[value->id]; if (res->value.mode == value->mode) return res; /* allow hidden casts */ if (get_mode_arithmetic(res->value.mode) == irma_twos_complement && get_mode_arithmetic(value->mode) == irma_twos_complement && get_mode_size_bits(res->value.mode) == get_mode_size_bits(value->mode)) return res; } return NULL; } /* find_address */ /** * Find an address in the avail_out set. * * @param bl the block */ static memop_t *find_address_avail(const block_t *bl, unsigned id, const ir_mode *mode) { if (rbitset_is_set(bl->avail_out, id)) { memop_t *res = bl->id_2_memop_avail[id]; if (res->value.mode == mode) return res; /* allow hidden casts */ if (get_mode_arithmetic(res->value.mode) == irma_twos_complement && get_mode_arithmetic(mode) == irma_twos_complement && get_mode_size_bits(res->value.mode) == get_mode_size_bits(mode)) return res; } return NULL; } /* find_address_avail */ /** * Kill all addresses from the current set. */ static void kill_all(void) { rbitset_clear_all(env.curr_set, env.rbs_size); /* set sentinel */ rbitset_set(env.curr_set, env.rbs_size - 1); } /* kill_all */ /** * Kill memops that are not alias free due to a Store value from the current set. * * @param value the Store value */ static void kill_memops(const value_t *value) { size_t end = env.rbs_size - 1; size_t pos; for (pos = rbitset_next(env.curr_set, 0, 1); pos < end; pos = rbitset_next(env.curr_set, pos + 1, 1)) { memop_t *op = env.curr_id_2_memop[pos]; if (ir_no_alias != get_alias_relation(value->address, value->mode, op->value.address, op->value.mode)) { rbitset_clear(env.curr_set, pos); env.curr_id_2_memop[pos] = NULL; DB((dbg, LEVEL_2, "KILLING %+F because of possible alias address %+F\n", op->node, value->address)); } } } /* kill_memops */ /** * Add the value of a memop to the current set. * * @param op the memory op */ static void add_memop(memop_t *op) { rbitset_set(env.curr_set, op->value.id); env.curr_id_2_memop[op->value.id] = op; } /* add_memop */ /** * Add the value of a memop to the avail_out set. * * @param bl the block * @param op the memory op */ static void add_memop_avail(block_t *bl, memop_t *op) { rbitset_set(bl->avail_out, op->value.id); bl->id_2_memop_avail[op->value.id] = op; } /* add_memop_avail */ /** * Check, if we can convert a value of one mode to another mode * without changing the representation of bits. * * @param from the original mode * @param to the destination mode */ static int can_convert_to(const ir_mode *from, const ir_mode *to) { if (get_mode_arithmetic(from) == irma_twos_complement && get_mode_arithmetic(to) == irma_twos_complement && get_mode_size_bits(from) == get_mode_size_bits(to)) return 1; return 0; } /* can_convert_to */ /** * Add a Conv to the requested mode if needed. * * @param irn the IR-node to convert * @param mode the destination mode * * @return the possible converted node or NULL * if the conversion is not possible */ static ir_node *conv_to(ir_node *irn, ir_mode *mode) { ir_mode *other = get_irn_mode(irn); if (other != mode) { /* different modes: check if conversion is possible without changing the bits */ if (can_convert_to(other, mode)) { ir_node *block = get_nodes_block(irn); return new_r_Conv(block, irn, mode); } /* otherwise not possible ... yet */ return NULL; } return irn; } /* conv_to */ /** * Update the address of an value if this address was a load result * and the load is killed now. * * @param value the value whose address is updated */ static void update_address(value_t *value) { if (is_Proj(value->address)) { ir_node *load = get_Proj_pred(value->address); if (is_Load(load)) { const memop_t *op = get_irn_memop(load); if (op->flags & FLAG_KILLED_NODE) value->address = op->replace; } } } /* update_address */ /** * Do forward dataflow analysis on the given block and calculate the * GEN and KILL in the current (avail) set. * * @param bl the block */ static void calc_gen_kill_avail(block_t *bl) { memop_t *op; ir_node *def; for (op = bl->memop_forward; op != NULL; op = op->next) { switch (get_irn_opcode(op->node)) { case iro_Phi: /* meet */ break; case iro_Sync: /* join */ break; case iro_Load: if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) { /* do we have this already? */ memop_t *other; update_address(&op->value); other = find_address(&op->value); if (other != NULL && other != op) { def = conv_to(other->value.value, op->value.mode); if (def != NULL) { #ifdef DEBUG_libfirm if (is_Store(other->node)) { /* RAW */ DB((dbg, LEVEL_1, "RAW %+F <- %+F(%+F)\n", op->node, def, other->node)); } else { /* RAR */ DB((dbg, LEVEL_1, "RAR %+F <- %+F(%+F)\n", op->node, def, other->node)); } #endif mark_replace_load(op, def); /* do NOT change the memop table */ continue; } } /* add this value */ add_memop(op); } break; case iro_Store: if (! (op->flags & FLAG_KILLED_NODE)) { /* do we have this store already */ memop_t *other; update_address(&op->value); other = find_address(&op->value); if (other != NULL) { if (is_Store(other->node)) { if (op != other && !(other->flags & FLAG_IGNORE) && get_nodes_block(other->node) == get_nodes_block(op->node)) { /* * A WAW in the same block we can kick the first store. * This is a shortcut: we know that the second Store will be anticipated * then in an case. */ DB((dbg, LEVEL_1, "WAW %+F <- %+F\n", other->node, op->node)); mark_remove_store(other); /* FIXME: a Load might be get freed due to this killed store */ } } else if (other->value.value == op->value.value && !(op->flags & FLAG_IGNORE)) { /* WAR */ DB((dbg, LEVEL_1, "WAR %+F <- %+F\n", op->node, other->node)); mark_remove_store(op); /* do NOT change the memop table */ continue; } } /* KILL all possible aliases */ kill_memops(&op->value); /* add this value */ add_memop(op); } break; default: if (op->flags & FLAG_KILL_ALL) kill_all(); } } } /* calc_gen_kill_avail */ #define BYTE_SIZE(x) (((x) + 7) >> 3) /** * Do forward dataflow analysis on a given block to calculate the avail_out set * for this block only. * * @param block the block */ static void forward_avail(block_t *bl) { /* fill the data from the current block */ env.curr_id_2_memop = bl->id_2_memop_avail; env.curr_set = bl->avail_out; calc_gen_kill_avail(bl); dump_curr(bl, "Avail_out"); } /* forward_avail */ /** * Do backward dataflow analysis on a given block to calculate the antic set * of Loaded addresses. * * @param bl the block * * @return non-zero if the set has changed since last iteration */ static int backward_antic(block_t *bl) { memop_t *op; ir_node *block = bl->block; int n = get_Block_n_cfg_outs(block); if (n == 1) { ir_node *succ = get_Block_cfg_out(block, 0); block_t *succ_bl = get_block_entry(succ); int pred_pos = get_Block_cfgpred_pos(succ, block); size_t end = env.rbs_size - 1; size_t pos; kill_all(); if (bl->trans_results == NULL) { /* allocate the translate cache */ bl->trans_results = OALLOCNZ(&env.obst, memop_t*, env.curr_adr_id); } /* check for partly redundant values */ for (pos = rbitset_next(succ_bl->anticL_in, 0, 1); pos < end; pos = rbitset_next(succ_bl->anticL_in, pos + 1, 1)) { /* * do Phi-translation here: Note that at this point the nodes are * not changed, so we can safely cache the results. * However: Loads of Load results ARE bad, because we have no way to translate them yet ... */ memop_t *op = bl->trans_results[pos]; if (op == NULL) { /* not yet translated */ ir_node *adr, *trans_adr; op = succ_bl->id_2_memop_antic[pos]; adr = op->value.address; trans_adr = phi_translate(adr, succ, pred_pos); if (trans_adr != adr) { /* create a new entry for the translated one */ memop_t *new_op; new_op = alloc_memop(NULL); new_op->value.address = trans_adr; new_op->value.id = register_address(trans_adr); new_op->value.mode = op->value.mode; new_op->node = op->node; /* we need the node to decide if Load/Store */ new_op->flags = op->flags; bl->trans_results[pos] = new_op; op = new_op; } } env.curr_id_2_memop[op->value.id] = op; rbitset_set(env.curr_set, op->value.id); } } else if (n > 1) { ir_node *succ = get_Block_cfg_out(block, 0); block_t *succ_bl = get_block_entry(succ); int i; rbitset_copy(env.curr_set, succ_bl->anticL_in, env.rbs_size); memcpy(env.curr_id_2_memop, succ_bl->id_2_memop_antic, env.rbs_size * sizeof(env.curr_id_2_memop[0])); /* Hmm: probably we want kill merges of Loads ans Stores here */ for (i = n - 1; i > 0; --i) { ir_node *succ = get_Block_cfg_out(bl->block, i); block_t *succ_bl = get_block_entry(succ); rbitset_and(env.curr_set, succ_bl->anticL_in, env.rbs_size); } } else { /* block ends with a noreturn call */ kill_all(); } dump_curr(bl, "AnticL_out"); for (op = bl->memop_backward; op != NULL; op = op->prev) { switch (get_irn_opcode(op->node)) { case iro_Phi: /* meet */ break; case iro_Sync: /* join */ break; case iro_Load: if (! (op->flags & (FLAG_KILLED_NODE|FLAG_IGNORE))) { /* always add it */ add_memop(op); } break; case iro_Store: if (! (op->flags & FLAG_KILLED_NODE)) { /* a Store: check which memops must be killed */ kill_memops(&op->value); } break; default: if (op->flags & FLAG_KILL_ALL) kill_all(); } } memcpy(bl->id_2_memop_antic, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0])); if (! rbitsets_equal(bl->anticL_in, env.curr_set, env.rbs_size)) { /* changed */ rbitset_copy(bl->anticL_in, env.curr_set, env.rbs_size); dump_curr(bl, "AnticL_in*"); return 1; } dump_curr(bl, "AnticL_in"); return 0; } /* backward_antic */ /** * Replace a Load memop by a already known value. * * @param op the Load memop */ static void replace_load(memop_t *op) { ir_node *load = op->node; ir_node *def = skip_Id(op->replace); ir_node *proj; ir_mode *mode; if (def != NULL) DB((dbg, LEVEL_1, "Replacing %+F by definition %+F\n", load, is_Proj(def) ? get_Proj_pred(def) : def)); else { if (op->flags & FLAG_EXCEPTION) { /* bad: this node is unused and executed for exception only */ DB((dbg, LEVEL_1, "Unused %+F executed for exception only ...\n", load)); return; } DB((dbg, LEVEL_1, "Killing unused %+F\n", load)); } if (op->mem != NULL) { /* in rare cases a Load might have NO memory */ exchange(op->mem, get_Load_mem(load)); } proj = op->projs[pn_Load_res]; if (proj != NULL) { mode = get_irn_mode(proj); if (get_irn_mode(def) != mode) { /* a hidden cast */ dbg_info *db = get_irn_dbg_info(load); ir_node *block = get_nodes_block(proj); def = new_rd_Conv(db, block, def, mode); } exchange(proj, def); } proj = op->projs[pn_Load_X_except]; if (proj != NULL) { ir_graph *irg = get_irn_irg(load); exchange(proj, new_r_Bad(irg, mode_X)); } proj = op->projs[pn_Load_X_regular]; if (proj != NULL) { exchange(proj, new_r_Jmp(get_nodes_block(load))); } } /* replace_load */ /** * Remove a Store memop. * * @param op the Store memop */ static void remove_store(memop_t *op) { ir_node *store = op->node; ir_node *proj; DB((dbg, LEVEL_1, "Removing %+F\n", store)); if (op->mem != NULL) { /* in rare cases a Store might have no memory */ exchange(op->mem, get_Store_mem(store)); } proj = op->projs[pn_Store_X_except]; if (proj != NULL) { ir_graph *irg = get_irn_irg(store); exchange(proj, new_r_Bad(irg, mode_X)); } proj = op->projs[pn_Store_X_regular]; if (proj != NULL) { exchange(proj, new_r_Jmp(get_nodes_block(store))); } } /* remove_store */ /** * Do all necessary replacements for a given block. * * @param bl the block */ static void do_replacements(block_t *bl) { memop_t *op; for (op = bl->memop_forward; op != NULL; op = op->next) { if (op->flags & FLAG_KILLED_NODE) { switch (get_irn_opcode(op->node)) { case iro_Load: replace_load(op); break; case iro_Store: remove_store(op); break; } } } } /* do_replacements */ /** * Calculate the Avail_out sets for all basic blocks. */ static void calcAvail(void) { memop_t **tmp_memop = env.curr_id_2_memop; unsigned *tmp_set = env.curr_set; block_t *bl; /* calculate avail_out */ DB((dbg, LEVEL_2, "Calculate Avail_out\n")); /* iterate over all blocks in in any order, skip the start block */ for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) { forward_avail(bl); } /* restore the current sets */ env.curr_id_2_memop = tmp_memop; env.curr_set = tmp_set; } /* calcAvail */ /** * Calculate the Antic_in sets for all basic blocks. */ static void calcAntic(void) { int i, need_iter; /* calculate antic_out */ DB((dbg, LEVEL_2, "Calculate Antic_in\n")); i = 0; do { block_t *bl; DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i)); need_iter = 0; /* over all blocks in reverse post order */ for (bl = env.backward->backward_next; bl != NULL; bl = bl->backward_next) { need_iter |= backward_antic(bl); } ++i; } while (need_iter); DB((dbg, LEVEL_2, "Get anticipated Load set after %d iterations\n", i)); } /* calcAntic */ /** * Return the node representing the last memory in a block. * * @param bl the block */ static ir_node *find_last_memory(block_t *bl) { for (;;) { if (bl->memop_backward != NULL) { return bl->memop_backward->mem; } /* if there is NO memory in this block, go to the dominator */ bl = get_block_entry(get_Block_idom(bl->block)); } } /* find_last_memory */ /** * Reroute all memory users of old memory * to a new memory IR-node. * * @param omem the old memory IR-node * @param nmem the new memory IR-node */ static void reroute_all_mem_users(ir_node *omem, ir_node *nmem) { for (unsigned i = get_irn_n_outs(omem); i-- > 0; ) { int n_pos; ir_node *user = get_irn_out_ex(omem, i, &n_pos); set_irn_n(user, n_pos, nmem); } /* all edges previously point to omem now point to nmem */ nmem->o.out = omem->o.out; } /* reroute_all_mem_users */ /** * Reroute memory users of old memory that are dominated by a given block * to a new memory IR-node. * * @param omem the old memory IR-node * @param nmem the new memory IR-node * @param pass_bl the block the memory must pass */ static void reroute_mem_through(ir_node *omem, ir_node *nmem, ir_node *pass_bl) { unsigned n = get_irn_n_outs(omem); ir_def_use_edges *new_out = OALLOCF(&env.obst, ir_def_use_edges, edges, n); unsigned j = 0; for (unsigned i = 0; i < n; ++i) { int n_pos; ir_node *user = get_irn_out_ex(omem, i, &n_pos); ir_node *use_bl = get_nodes_block(user); if (is_Phi(user)) { use_bl = get_Block_cfgpred_block(use_bl, n_pos); } if (block_dominates(pass_bl, use_bl)) { /* found an user that is dominated */ new_out->edges[j].pos = n_pos; new_out->edges[j].use = user; ++j; set_irn_n(user, n_pos, nmem); } } new_out->n_edges = j; /* Modify the out structure: we create a new out edge array on our temporary obstack here. This should be no problem, as we invalidate the edges at the end either. */ /* first entry is used for the length */ nmem->o.out = new_out; } /* reroute_mem_through */ /** * insert Loads, making partly redundant Loads fully redundant */ static int insert_Load(block_t *bl) { ir_node *block = bl->block; int i, n = get_Block_n_cfgpreds(block); size_t end = env.rbs_size - 1; DB((dbg, LEVEL_3, "processing %+F\n", block)); if (n == 0) { /* might still happen for an unreachable block (end for instance) */ return 0; } if (n > 1) { ir_node **ins; size_t pos; NEW_ARR_A(ir_node *, ins, n); rbitset_set_all(env.curr_set, env.rbs_size); /* More than one predecessors, calculate the join for all avail_outs ignoring unevaluated Blocks. These put in Top anyway. */ for (i = n - 1; i >= 0; --i) { ir_node *pred = skip_Proj(get_Block_cfgpred(block, i)); ir_node *blk = get_nodes_block(pred); block_t *pred_bl; pred_bl = get_block_entry(blk); rbitset_and(env.curr_set, pred_bl->avail_out, env.rbs_size); if (is_Load(pred) || is_Store(pred)) { /* We reached this block by an exception from a Load or Store: * the memop creating the exception was NOT completed than, kill it */ memop_t *exc_op = get_irn_memop(pred); rbitset_clear(env.curr_set, exc_op->value.id); } } /* * Ensure that all values are in the map: build Phi's if necessary: * Note: the last bit is the sentinel and ALWAYS set, so end with -2. */ for (pos = 0; pos < env.rbs_size - 1; ++pos) { if (! rbitset_is_set(env.curr_set, pos)) env.curr_id_2_memop[pos] = NULL; else { int need_phi = 0; memop_t *first = NULL; ir_mode *mode = NULL; for (i = 0; i < n; ++i) { ir_node *pred = get_Block_cfgpred_block(bl->block, i); block_t *pred_bl = get_block_entry(pred); memop_t *mop = pred_bl->id_2_memop_avail[pos]; if (first == NULL) { first = mop; ins[0] = first->value.value; mode = get_irn_mode(ins[0]); /* no Phi needed so far */ env.curr_id_2_memop[pos] = first; } else { ins[i] = conv_to(mop->value.value, mode); if (ins[i] != ins[0]) { if (ins[i] == NULL) { /* conversion failed */ env.curr_id_2_memop[pos] = NULL; rbitset_clear(env.curr_set, pos); break; } need_phi = 1; } } } if (need_phi) { /* build a Phi */ ir_node *phi = new_r_Phi(bl->block, n, ins, mode); memop_t *phiop = alloc_memop(phi); phiop->value = first->value; phiop->value.value = phi; /* no need to link it in, as it is a DATA phi */ env.curr_id_2_memop[pos] = phiop; DB((dbg, LEVEL_3, "Created new %+F on merging value for address %+F\n", phi, first->value.address)); } } } } else { /* only one predecessor, simply copy the map */ ir_node *pred = get_Block_cfgpred_block(bl->block, 0); block_t *pred_bl = get_block_entry(pred); rbitset_copy(env.curr_set, pred_bl->avail_out, env.rbs_size); memcpy(env.curr_id_2_memop, pred_bl->id_2_memop_avail, env.rbs_size * sizeof(bl->id_2_memop_avail[0])); } if (n > 1) { size_t pos; /* check for partly redundant values */ for (pos = rbitset_next(bl->anticL_in, 0, 1); pos < end; pos = rbitset_next(bl->anticL_in, pos + 1, 1)) { memop_t *op = bl->id_2_memop_antic[pos]; int have_some, all_same; ir_node *first; if (rbitset_is_set(env.curr_set, pos)) { /* already avail */ continue; } assert(is_Load(op->node)); DB((dbg, LEVEL_3, "anticipated %+F\n", op->node)); have_some = 0; all_same = 1; first = 0; for (i = n - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred_block(block, i); block_t *pred_bl = get_block_entry(pred); ir_mode *mode = op->value.mode; memop_t *e; ir_node *adr; adr = phi_translate(op->value.address, block, i); DB((dbg, LEVEL_3, ".. using address %+F in pred %d\n", adr, i)); e = find_address_avail(pred_bl, register_address(adr), mode); if (e == NULL) { ir_node *ef_block = get_nodes_block(adr); if (! block_dominates(ef_block, pred)) { /* cannot place a copy here */ have_some = 0; DB((dbg, LEVEL_3, "%+F cannot be moved into predecessor %+F\n", op->node, pred)); break; } DB((dbg, LEVEL_3, "%+F is not available in predecessor %+F\n", op->node, pred)); pred_bl->avail = NULL; all_same = 0; } else { if (e->value.mode != mode && !can_convert_to(e->value.mode, mode)) { /* cannot create a Phi due to different modes */ have_some = 0; break; } pred_bl->avail = e; have_some = 1; DB((dbg, LEVEL_3, "%+F is available for %+F in predecessor %+F\n", e->node, op->node, pred)); if (first == NULL) first = e->node; else if (first != e->node) all_same = 0; } } if (have_some && !all_same) { ir_mode *mode = op->value.mode; ir_node **in, *phi; memop_t *phi_op; NEW_ARR_A(ir_node *, in, n); for (i = n - 1; i >= 0; --i) { ir_node *pred = get_Block_cfgpred_block(block, i); block_t *pred_bl = get_block_entry(pred); if (pred_bl->avail == NULL) { /* create a new Load here and make to make it fully redundant */ dbg_info *db = get_irn_dbg_info(op->node); ir_node *last_mem = find_last_memory(pred_bl); ir_node *load, *def, *adr; memop_t *new_op; assert(last_mem != NULL); adr = phi_translate(op->value.address, block, i); load = new_rd_Load(db, pred, last_mem, adr, mode, cons_none); def = new_r_Proj(load, mode, pn_Load_res); DB((dbg, LEVEL_1, "Created new %+F in %+F for party redundant %+F\n", load, pred, op->node)); new_op = alloc_memop(load); new_op->mem = new_r_Proj(load, mode_M, pn_Load_M); new_op->value.address = adr; new_op->value.id = op->value.id; new_op->value.mode = mode; new_op->value.value = def; new_op->projs[pn_Load_M] = new_op->mem; new_op->projs[pn_Load_res] = def; new_op->prev = pred_bl->memop_backward; if (pred_bl->memop_backward != NULL) pred_bl->memop_backward->next = new_op; pred_bl->memop_backward = new_op; if (pred_bl->memop_forward == NULL) pred_bl->memop_forward = new_op; if (get_nodes_block(last_mem) == pred) { /* We have add a new last memory op in pred block. If pred had already a last mem, reroute all memory users. */ reroute_all_mem_users(last_mem, new_op->mem); } else { /* reroute only those memory going through the pre block */ reroute_mem_through(last_mem, new_op->mem, pred); } /* we added this load at the end, so it will be avail anyway */ add_memop_avail(pred_bl, new_op); pred_bl->avail = new_op; } in[i] = conv_to(pred_bl->avail->value.value, mode); } phi = new_r_Phi(block, n, in, mode); DB((dbg, LEVEL_1, "Created new %+F in %+F for now redundant %+F\n", phi, block, op->node)); phi_op = clone_memop_phi(op, phi); add_memop(phi_op); } } } /* recalculate avail by gen and kill */ calc_gen_kill_avail(bl); /* always update the map after gen/kill, as values might have been changed due to RAR/WAR/WAW */ memcpy(bl->id_2_memop_avail, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0])); if (!rbitsets_equal(bl->avail_out, env.curr_set, env.rbs_size)) { /* the avail set has changed */ rbitset_copy(bl->avail_out, env.curr_set, env.rbs_size); dump_curr(bl, "Avail_out*"); return 1; } dump_curr(bl, "Avail_out"); return 0; } /* insert_Load */ /** * Insert Loads upwards. */ static void insert_Loads_upwards(void) { int i, need_iter; block_t *bl; /* recalculate antic_out and insert Loads */ DB((dbg, LEVEL_2, "Inserting Loads\n")); i = 0; do { DB((dbg, LEVEL_2, "Iteration %d:\n=========\n", i)); need_iter = 0; /* over all blocks in reverse post order, skip the start block */ for (bl = env.forward->forward_next; bl != NULL; bl = bl->forward_next) { need_iter |= insert_Load(bl); } ++i; } while (need_iter); DB((dbg, LEVEL_2, "Finished Load inserting after %d iterations\n", i)); } /* insert_Loads_upwards */ void opt_ldst(ir_graph *irg) { block_t *bl; FIRM_DBG_REGISTER(dbg, "firm.opt.ldst"); DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg)); assure_irg_properties(irg, IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES /* we need landing pads */ | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE | IR_GRAPH_PROPERTY_CONSISTENT_OUTS | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE | IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE); if (get_opt_alias_analysis()) { assure_irp_globals_entity_usage_computed(); } obstack_init(&env.obst); ir_nodehashmap_init(&env.adr_map); env.forward = NULL; env.backward = NULL; env.curr_adr_id = 0; env.n_mem_ops = 0; env.max_cfg_preds = 0; env.changed = 0; env.start_bl = get_irg_start_block(irg); env.end_bl = get_irg_end_block(irg); #ifdef DEBUG_libfirm env.id_2_address = NEW_ARR_F(ir_node *, 0); #endif ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK); /* first step: allocate block entries. Note that some blocks might be unreachable here. Using the normal walk ensures that ALL blocks are initialized. */ irg_walk_graph(irg, prepare_blocks, link_phis, NULL); /* produce an inverse post-order list for the CFG: this links only reachable blocks */ irg_out_block_walk(get_irg_start_block(irg), NULL, inverse_post_order, NULL); if (! get_Block_mark(env.end_bl)) { /* * The end block is NOT reachable due to endless loops * or no_return calls. * Place the end block last. * env.backward points to the last block in the list for this purpose. */ env.backward->forward_next = get_block_entry(env.end_bl); set_Block_mark(env.end_bl, 1); } /* second step: find and sort all memory ops */ walk_memory_irg(irg, collect_memops, NULL, NULL); #ifdef DEBUG_libfirm /* check that the backward map is correct */ assert((unsigned)ARR_LEN(env.id_2_address) == env.curr_adr_id); #endif if (env.n_mem_ops == 0) { /* no memory ops */ goto no_changes; } /* create the backward links. */ env.backward = NULL; irg_block_walk_graph(irg, NULL, collect_backward, NULL); /* link the end block in */ bl = get_block_entry(env.end_bl); bl->backward_next = env.backward; env.backward = bl; /* check that we really start with the start / end block */ assert(env.forward->block == env.start_bl); assert(env.backward->block == env.end_bl); /* create address sets: for now, only the existing addresses are allowed plus one needed for the sentinel */ env.rbs_size = env.curr_adr_id + 1; /* create the current set */ env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size); rbitset_set(env.curr_set, env.rbs_size - 1); env.curr_id_2_memop = NEW_ARR_DZ(memop_t*, &env.obst, env.rbs_size); for (bl = env.forward; bl != NULL; bl = bl->forward_next) { /* set sentinel bits */ bl->avail_out = rbitset_obstack_alloc(&env.obst, env.rbs_size); rbitset_set(bl->avail_out, env.rbs_size - 1); bl->id_2_memop_avail = NEW_ARR_DZ(memop_t*, &env.obst, env.rbs_size); bl->anticL_in = rbitset_obstack_alloc(&env.obst, env.rbs_size); rbitset_set(bl->anticL_in, env.rbs_size - 1); bl->id_2_memop_antic = NEW_ARR_DZ(memop_t*, &env.obst, env.rbs_size); } (void) dump_block_list; calcAvail(); calcAntic(); insert_Loads_upwards(); if (env.changed) { /* over all blocks in reverse post order */ for (bl = env.forward; bl != NULL; bl = bl->forward_next) { do_replacements(bl); } /* not only invalidate but free them. We might allocate new out arrays on our obstack which will be deleted yet. */ confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_CONTROL_FLOW); } else { no_changes: confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_ALL); } ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK); ir_nodehashmap_destroy(&env.adr_map); obstack_free(&env.obst, NULL); #ifdef DEBUG_libfirm DEL_ARR_F(env.id_2_address); #endif } /* opt_ldst */ ir_graph_pass_t *opt_ldst_pass(const char *name) { return def_graph_pass(name ? name : "ldst_df", opt_ldst); } /* opt_ldst_pass */