/*
- * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
* @brief Dataflow driven Load/Store optimizations, uses some ideas from
* VanDrunen's LEPRE
* @author Michael Beck
- * @version $Id$
*/
#include "config.h"
#include "irgopt.h"
#include "iropt.h"
#include "iroptimize.h"
-#include "irnodemap.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 (pn_Load_max > pn_Store_max ? pn_Load_max : pn_Store_max)
+#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.
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]; /**< Projs of this memory op */
+ ir_node *projs[MAX_PROJ+1]; /**< Projs of this memory op */
};
/**
* Metadata for this pass.
*/
typedef struct ldst_env_t {
- struct obstack obst; /**< obstack for temporary data */
- ir_nodemap_t adr_map; /**< Map addresses to */
+ 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 */
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) */
- unsigned rbs_size; /**< size of all bitsets in bytes */
+ 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
#endif
} ldst_env;
+/* the one and only environment */
+static ldst_env env;
+
#ifdef DEBUG_libfirm
static firm_dbg_module_t *dbg;
-/* the one and only environment */
-static ldst_env env;
-
/**
* Dumps the block list.
*
* @param ldst environment
*/
-static void dump_block_list(ldst_env *env) {
+static void dump_block_list(ldst_env *env)
+{
block_t *entry;
memop_t *op;
int i;
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));
+ }
+ 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)
* @param bl current block
* @param s name of the set
*/
-static void dump_curr(block_t *bl, const char *s) {
- unsigned end = env.rbs_size - 1;
- unsigned pos;
- int i;
+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;
} /* dump_curr */
#else
-#define dump_block_list()
-#define dump_curr(bl, s)
+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) {
+static block_t *get_block_entry(const ir_node *block)
+{
assert(is_Block(block));
- return get_irn_link(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) {
+static memop_t *get_irn_memop(const ir_node *irn)
+{
assert(! is_Block(irn));
- return get_irn_link(irn);
+ return (memop_t*)get_irn_link(irn);
} /* get_irn_memop */
/**
* @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) {
+static void walk_memory(ir_node *irn, irg_walk_func *pre, irg_walk_func *post, void *ctx)
+{
int i;
ir_mode *mode;
* @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) {
+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);
*
* @return the allocated id
*/
-static unsigned register_address(ir_node *adr) {
+static unsigned register_address(ir_node *adr)
+{
address_entry *entry;
/* skip Confirms and Casts */
goto restart;
}
- entry = ir_nodemap_get(&env.adr_map, adr);
+ entry = (address_entry*)ir_nodehashmap_get(&env.adr_map, adr);
if (entry == NULL) {
/* new address */
- entry = obstack_alloc(&env.obst, sizeof(*entry));
+ entry = OALLOC(&env.obst, address_entry);
entry->id = env.curr_adr_id++;
- ir_nodemap_insert(&env.adr_map, adr, entry);
+ ir_nodehashmap_insert(&env.adr_map, adr, entry);
DB((dbg, LEVEL_3, "ADDRESS %+F has ID %u\n", adr, entry->id));
#ifdef DEBUG_libfirm
* @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) {
+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 */
-/**
- * Get the effective block of an address in the pos'th predecessor
- * of the given block.
- *
- * @param address the address
- * @param block the block
- * @param pos the position of the predecessor in block
- */
-static ir_node *get_effective_block(ir_node *address, ir_node *block, int pos) {
- address = phi_translate(address, block, pos);
- return get_nodes_block(address);
-} /* get_effective_block */
-
/**
* Walker: allocate an block entry for every block
* and register all potential addresses.
*/
-static void prepare_blocks(ir_node *irn, void *ctx) {
+static void prepare_blocks(ir_node *irn, void *ctx)
+{
(void)ctx;
if (is_Block(irn)) {
- block_t *entry = obstack_alloc(&env.obst, sizeof(*entry));
+ block_t *entry = OALLOC(&env.obst, block_t);
int n;
entry->memop_forward = NULL;
/**
* Post-Walker, link in all Phi's
*/
-static void link_phis(ir_node *irn, void *ctx) {
+static void link_phis(ir_node *irn, void *ctx)
+{
(void)ctx;
if (is_Phi(irn)) {
/**
* Block walker: creates the inverse post-order list for the CFG.
*/
-static void inverse_post_order(ir_node *block, void *ctx) {
+static void inverse_post_order(ir_node *block, void *ctx)
+{
block_t *entry = get_block_entry(block);
(void)ctx;
/**
* Block walker: create backward links for the memops of a block.
*/
-static void collect_backward(ir_node *block, void *ctx) {
+static void collect_backward(ir_node *block, void *ctx)
+{
block_t *entry = get_block_entry(block);
memop_t *last, *op;
*
* @return the allocated memop
*/
-static memop_t *alloc_memop(ir_node *irn) {
- memop_t *m = obstack_alloc(&env.obst, sizeof(*m));
+static memop_t *alloc_memop(ir_node *irn)
+{
+ memop_t *m = OALLOC(&env.obst, memop_t);
m->value.address = NULL;
m->value.value = NULL;
* @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 = obstack_alloc(&env.obst, sizeof(*m));
+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;
*
* return a bitset of mtp_property_const and mtp_property_pure
*/
-static unsigned get_Call_memory_properties(ir_node *call) {
+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);
/* try the called entity */
ir_node *ptr = get_Call_ptr(call);
- if (is_Global(ptr)) {
- ir_entity *ent = get_Global_entity(ptr);
+ if (is_SymConst_addr_ent(ptr)) {
+ ir_entity *ent = get_SymConst_entity(ptr);
prop = get_entity_additional_properties(ent);
}
*
* @return an entity or NULL
*/
-static ir_entity *find_constant_entity(ir_node *ptr) {
+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);
int i, n;
for (i = 0, n = get_Sel_n_indexs(ptr); i < n; ++i) {
- ir_node *bound;
- tarval *tlower, *tupper;
- ir_node *index = get_Sel_index(ptr, i);
- tarval *tv = computed_value(index);
+ 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)
if (tlower == tarval_bad || tupper == tarval_bad)
return NULL;
- if (tarval_cmp(tv, tlower) & pn_Cmp_Lt)
+ if (tarval_cmp(tv, tlower) == ir_relation_less)
return NULL;
- if (tarval_cmp(tupper, tv) & pn_Cmp_Lt)
+ if (tarval_cmp(tupper, tv) == ir_relation_less)
return NULL;
/* ok, bounds check finished */
}
}
- if (variability_constant == get_entity_variability(ent))
+ if (get_entity_linkage(ent) == IR_LINKAGE_CONSTANT)
return ent;
/* try next */
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))
+ if (get_irn_mode(l) == get_irn_mode(ptr) && is_Const(r))
ptr = l;
else
return NULL;
/**
* Return the Selection index of a Sel node from dimension n
*/
-static long get_Sel_array_index_long(ir_node *n, int dim) {
+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));
* @param depth current depth in steps upward from the root
* of the address
*/
-static compound_graph_path *rec_get_accessed_path(ir_node *ptr, int depth) {
+static compound_graph_path *rec_get_accessed_path(ir_node *ptr, size_t depth)
+{
compound_graph_path *res = NULL;
ir_entity *root, *field, *ent;
- int path_len, pos, idx;
- tarval *tv;
+ size_t path_len, pos, idx;
+ ir_tarval *tv;
ir_type *tp;
if (is_SymConst(ptr)) {
set_compound_graph_path_array_index(res, pos, get_Sel_array_index_long(ptr, 0));
}
} else if (is_Add(ptr)) {
- ir_node *l = get_Add_left(ptr);
- ir_node *r = get_Add_right(ptr);
- ir_mode *mode = get_irn_mode(ptr);
- tarval *tmp;
-
- if (is_Const(r) && get_irn_mode(l) == mode) {
- ptr = l;
- tv = get_Const_tarval(r);
- } else {
- ptr = r;
- tv = get_Const_tarval(l);
+ ir_mode *mode;
+ ir_tarval *tmp;
+
+ {
+ ir_node *l = get_Add_left(ptr);
+ ir_node *r = get_Add_right(ptr);
+ if (is_Const(r) && get_irn_mode(l) == get_irn_mode(ptr)) {
+ ptr = l;
+ tv = get_Const_tarval(r);
+ } else {
+ ptr = r;
+ tv = get_Const_tarval(l);
+ }
}
ptr_arith:
mode = get_tarval_mode(tv);
}
idx = 0;
for (ent = field;;) {
- unsigned size;
- tarval *sz, *tv_index, *tlower, *tupper;
- ir_node *bound;
+ unsigned size;
+ ir_tarval *sz, *tv_index, *tlower, *tupper;
+ ir_node *bound;
tp = get_entity_type(ent);
if (! is_Array_type(tp))
if (tlower == tarval_bad || tupper == tarval_bad)
return NULL;
- if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt)
+ if (tarval_cmp(tv_index, tlower) == ir_relation_less)
return NULL;
- if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt)
+ if (tarval_cmp(tupper, tv_index) == ir_relation_less)
return NULL;
/* ok, bounds check finished */
pos = path_len - depth - idx;
for (ent = field;;) {
- unsigned size;
- tarval *sz, *tv_index;
- long index;
+ unsigned size;
+ ir_tarval *sz, *tv_index;
+ long index;
tp = get_entity_type(ent);
if (! is_Array_type(tp))
* Returns an access path or NULL. The access path is only
* valid, if the graph is in phase_high and _no_ address computation is used.
*/
-static compound_graph_path *get_accessed_path(ir_node *ptr) {
+static compound_graph_path *get_accessed_path(ir_node *ptr)
+{
compound_graph_path *gr = rec_get_accessed_path(ptr, 0);
return gr;
} /* get_accessed_path */
typedef struct path_entry {
ir_entity *ent;
struct path_entry *next;
- long index;
+ size_t index;
} path_entry;
-static ir_node *rec_find_compound_ent_value(ir_node *ptr, path_entry *next) {
+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;
- tarval *tv;
+ ir_tarval *tv;
ir_type *tp;
- unsigned n;
+ size_t n;
entry.next = next;
if (is_SymConst(ptr)) {
continue;
}
}
- if (p->index >= (int) n)
+ if (p->index >= n)
return NULL;
initializer = get_initializer_compound_value(initializer, p->index);
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 {
- int i, n_members = get_compound_n_members(tp);
+ 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;
}
return rec_find_compound_ent_value(get_Sel_ptr(ptr), &entry);
} else if (is_Add(ptr)) {
- ir_node *l = get_Add_left(ptr);
- ir_node *r = get_Add_right(ptr);
- ir_mode *mode;
+ ir_mode *mode;
unsigned pos;
- if (is_Const(r)) {
- ptr = l;
- tv = get_Const_tarval(r);
- } else {
- ptr = r;
- tv = get_Const_tarval(l);
+ {
+ 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);
/* fill them up */
pos = 0;
for (ent = field;;) {
- unsigned size;
- tarval *sz, *tv_index, *tlower, *tupper;
- long index;
- ir_node *bound;
+ 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))
if (tlower == tarval_bad || tupper == tarval_bad)
return NULL;
- if (tarval_cmp(tv_index, tlower) & pn_Cmp_Lt)
+ if (tarval_cmp(tv_index, tlower) == ir_relation_less)
return NULL;
- if (tarval_cmp(tupper, tv_index) & pn_Cmp_Lt)
+ if (tarval_cmp(tupper, tv_index) == ir_relation_less)
return NULL;
/* ok, bounds check finished */
return NULL;
} /* rec_find_compound_ent_value */
-static ir_node *find_compound_ent_value(ir_node *ptr) {
+static ir_node *find_compound_ent_value(ir_node *ptr)
+{
return rec_find_compound_ent_value(ptr, NULL);
} /* find_compound_ent_value */
*
* @param op the Load memop
*/
-static void mark_replace_load(memop_t *op, ir_node *def) {
+static void mark_replace_load(memop_t *op, ir_node *def)
+{
op->replace = def;
op->flags |= FLAG_KILLED_NODE;
env.changed = 1;
*
* @param op the Store memop
*/
-static void mark_remove_store(memop_t *op) {
+static void mark_remove_store(memop_t *op)
+{
op->flags |= FLAG_KILLED_NODE;
env.changed = 1;
} /* mark_remove_store */
*
* @param m the memop
*/
-static void update_Load_memop(memop_t *m) {
+static void update_Load_memop(memop_t *m)
+{
int i;
ir_node *load = m->node;
ir_node *ptr;
/* check if we can determine the entity that will be loaded */
ent = find_constant_entity(ptr);
- if (ent != NULL &&
- allocation_static == get_entity_allocation(ent) &&
- visibility_external_allocated != get_entity_visibility(ent)) {
+ 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]) {
- exchange(m->projs[pn_Load_X_except], new_Bad());
+ 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(current_ir_graph, get_nodes_block(load)));
+ 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 (variability_constant == get_entity_variability(ent)) {
- if (is_atomic_entity(ent)) {
- /* Might not be atomic after lowering of Sels. In this case we
- * could also load, but it's more complicated. */
- /* more simpler case: we load the content of a constant value:
- * replace it by the constant itself */
- value = get_atomic_ent_value(ent);
- } else if (ent->has_initializer) {
+ if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT) {
+ if (ent->initializer) {
/* new style initializer */
value = find_compound_ent_value(ptr);
- } else {
+ } else if (entity_has_compound_ent_values(ent)) {
/* old style initializer */
compound_graph_path *path = get_accessed_path(ptr);
*
* @param m the memop
*/
-static void update_Store_memop(memop_t *m) {
+static void update_Store_memop(memop_t *m)
+{
int i;
ir_node *store = m->node;
ir_node *adr = get_Store_ptr(store);
*
* @param m the memop
*/
-static void update_Call_memop(memop_t *m) {
+static void update_Call_memop(memop_t *m)
+{
ir_node *call = m->node;
unsigned prop = get_Call_memory_properties(call);
int i;
case pn_Call_X_except:
m->flags |= FLAG_EXCEPTION;
break;
- case pn_Call_M_regular:
+ case pn_Call_M:
m->mem = proj;
break;
}
} /* update_Call_memop */
/**
- * Update a memop for a Div/Mod/Quot/DivMod.
+ * Update a memop for a Div/Mod.
*
* @param m the memop
*/
-static void update_DivOp_memop(memop_t *m) {
+static void update_Div_memop(memop_t *m)
+{
ir_node *div = m->node;
int i;
continue;
switch (get_Proj_proj(proj)) {
- case pn_Generic_X_except:
+ case pn_Div_X_except:
m->flags |= FLAG_EXCEPTION;
break;
- case pn_Generic_M_regular:
+ case pn_Div_M:
m->mem = proj;
break;
}
}
-} /* update_DivOp_memop */
+}
+
+static void update_Mod_memop(memop_t *m)
+{
+ ir_node *div = m->node;
+ int i;
+
+ for (i = get_irn_n_outs(div) - 1; i >= 0; --i) {
+ 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 it's own mem */
+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) {
+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 */
- if (irn != get_irg_initial_mem(current_ir_graph))
+ ir_graph *irg = get_irn_irg(irn);
+ if (irn != get_irg_initial_mem(irg))
return;
}
/* we can those to find the memory edge */
break;
case iro_Div:
- case iro_DivMod:
- case iro_Quot:
+ update_Div_memop(op);
+ break;
case iro_Mod:
- update_DivOp_memop(op);
+ update_Mod_memop(op);
break;
case iro_Builtin:
* not exists in the set or cannot be converted into
* the requested mode
*/
-static memop_t *find_address(const value_t *value) {
+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];
* Find an address in the avail_out set.
*
* @param bl the block
- * @param value the value to be searched for
*/
-static memop_t *find_address_avail(const block_t *bl, const value_t *value) {
- if (rbitset_is_set(bl->avail_out, value->id)) {
- memop_t *res = bl->id_2_memop_avail[value->id];
+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 == value->mode)
+ if (res->value.mode == 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))
+ get_mode_arithmetic(mode) == irma_twos_complement &&
+ get_mode_size_bits(res->value.mode) == get_mode_size_bits(mode))
return res;
}
return NULL;
/**
* Kill all addresses from the current set.
*/
-static void kill_all(void) {
+static void kill_all(void)
+{
rbitset_clear_all(env.curr_set, env.rbs_size);
/* set sentinel */
*
* @param value the Store value
*/
-static void kill_memops(const value_t *value) {
- unsigned end = env.rbs_size - 1;
- unsigned pos;
+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(current_ir_graph, value->address, value->mode,
+ 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;
*
* @param op the memory op
*/
-static void add_memop(memop_t *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 */
* @param bl the block
* @param op the memory op
*/
-static void add_memop_avail(block_t *bl, memop_t *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 */
* @param from the original mode
* @param to the destination mode
*/
-static int can_convert_to(const ir_mode *from, const ir_mode *to) {
+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 the possible converted node or NULL
* if the conversion is not possible
*/
-static ir_node *conv_to(ir_node *irn, ir_mode *mode) {
+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(current_ir_graph, block, irn, mode);
+ return new_r_Conv(block, irn, mode);
}
/* otherwise not possible ... yet */
return NULL;
*
* @param value the value whose address is updated
*/
-static void update_address(value_t *value) {
+static void update_address(value_t *value)
+{
if (is_Proj(value->address)) {
ir_node *load = get_Proj_pred(value->address);
*
* @param bl the block
*/
-static void calc_gen_kill_avail(block_t *bl) {
+static void calc_gen_kill_avail(block_t *bl)
+{
memop_t *op;
ir_node *def;
*
* @param block the block
*/
-static void forward_avail(block_t *bl) {
+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;
*
* @return non-zero if the set has changed since last iteration
*/
-static int backward_antic(block_t *bl) {
+static int backward_antic(block_t *bl)
+{
memop_t *op;
ir_node *block = bl->block;
int n = get_Block_n_cfg_outs(block);
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);
- unsigned end = env.rbs_size;
- unsigned pos;
+ size_t end = env.rbs_size - 1;
+ size_t pos;
kill_all();
if (bl->trans_results == NULL) {
/* allocate the translate cache */
- unsigned size = env.curr_adr_id * sizeof(bl->trans_results[0]);
- bl->trans_results = obstack_alloc(&env.obst, size);
- memset(bl->trans_results, 0, size);
+ bl->trans_results = OALLOCNZ(&env.obst, memop_t*, env.curr_adr_id);
}
/* check for partly redundant values */
new_op->node = op->node; /* we need the node to decide if Load/Store */
new_op->flags = op->flags;
- bl->trans_results[pos] = op;
+ 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);
- env.curr_id_2_memop[pos] = op;
}
} else if (n > 1) {
ir_node *succ = get_Block_cfg_out(block, 0);
block_t *succ_bl = get_block_entry(succ);
int i;
- rbitset_cpy(env.curr_set, succ_bl->anticL_in, env.rbs_size);
+ 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 */
}
memcpy(bl->id_2_memop_antic, env.curr_id_2_memop, env.rbs_size * sizeof(env.curr_id_2_memop[0]));
- if (! rbitset_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
+ if (! rbitsets_equal(bl->anticL_in, env.curr_set, env.rbs_size)) {
/* changed */
- rbitset_cpy(bl->anticL_in, env.curr_set, env.rbs_size);
+ rbitset_copy(bl->anticL_in, env.curr_set, env.rbs_size);
dump_curr(bl, "AnticL_in*");
return 1;
}
*
* @param op the Load memop
*/
-static void replace_load(memop_t *op) {
+static void replace_load(memop_t *op)
+{
ir_node *load = op->node;
ir_node *def = skip_Id(op->replace);
ir_node *proj;
/* a hidden cast */
dbg_info *db = get_irn_dbg_info(load);
ir_node *block = get_nodes_block(proj);
- def = new_rd_Conv(db, current_ir_graph, block, def, mode);
+ def = new_rd_Conv(db, block, def, mode);
}
exchange(proj, def);
}
proj = op->projs[pn_Load_X_except];
if (proj != NULL) {
- exchange(proj, new_Bad());
+ 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(current_ir_graph, get_nodes_block(load)));
+ exchange(proj, new_r_Jmp(get_nodes_block(load)));
}
} /* replace_load */
*
* @param op the Store memop
*/
-static void remove_store(memop_t *op) {
+static void remove_store(memop_t *op)
+{
ir_node *store = op->node;
ir_node *proj;
}
proj = op->projs[pn_Store_X_except];
if (proj != NULL) {
- exchange(proj, new_Bad());
+ 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(current_ir_graph, get_nodes_block(store)));
+ exchange(proj, new_r_Jmp(get_nodes_block(store)));
}
} /* remove_store */
*
* @param bl the block
*/
-static void do_replacements(block_t *bl) {
+static void do_replacements(block_t *bl)
+{
memop_t *op;
for (op = bl->memop_forward; op != NULL; op = op->next) {
/**
* Calculate the Avail_out sets for all basic blocks.
*/
-static void calcAvail(void) {
+static void calcAvail(void)
+{
memop_t **tmp_memop = env.curr_id_2_memop;
unsigned *tmp_set = env.curr_set;
block_t *bl;
/**
* Calculate the Antic_in sets for all basic blocks.
*/
-static void calcAntic(void) {
+static void calcAntic(void)
+{
int i, need_iter;
/* calculate antic_out */
*
* @param bl the block
*/
-static ir_node *find_last_memory(block_t *bl) {
+static ir_node *find_last_memory(block_t *bl)
+{
for (;;) {
if (bl->memop_backward != NULL) {
return bl->memop_backward->mem;
* @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) {
+static void reroute_all_mem_users(ir_node *omem, ir_node *nmem)
+{
int i;
for (i = get_irn_n_outs(omem) - 1; i >= 0; --i) {
* @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) {
+static void reroute_mem_through(ir_node *omem, ir_node *nmem, ir_node *pass_bl)
+{
int i, j, n = get_irn_n_outs(omem);
ir_def_use_edge *edges = NEW_ARR_D(ir_def_use_edge, &env.obst, n + 1);
/**
* insert Loads, making partly redundant Loads fully redundant
*/
-static int insert_Load(block_t *bl) {
+static int insert_Load(block_t *bl)
+{
ir_node *block = bl->block;
int i, n = get_Block_n_cfgpreds(block);
- unsigned end = env.rbs_size - 1;
- unsigned pos;
+ size_t end = env.rbs_size - 1;
DB((dbg, LEVEL_3, "processing %+F\n", block));
if (n > 1) {
ir_node **ins;
+ size_t pos;
NEW_ARR_A(ir_node *, ins, n);
}
/*
* Ensure that all values are in the map: build Phi's if necessary:
- * Note: the last bit is the sentinel and ALWAYS set, so start with -2.
+ * Note: the last bit is the sentinel and ALWAYS set, so end with -2.
*/
- for (pos = env.rbs_size - 2; pos >= 0; --pos) {
+ 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 {
block_t *pred_bl = get_block_entry(pred);
int need_phi = 0;
memop_t *first = NULL;
- ir_mode *mode;
+ ir_mode *mode = NULL;
for (i = 0; i < n; ++i) {
memop_t *mop;
}
if (need_phi) {
/* build a Phi */
- ir_node *phi = new_r_Phi(current_ir_graph, bl->block, n, ins, mode);
+ ir_node *phi = new_r_Phi(bl->block, n, ins, mode);
memop_t *phiop = alloc_memop(phi);
phiop->value = first->value;
ir_node *pred = get_Block_cfgpred_block(bl->block, 0);
block_t *pred_bl = get_block_entry(pred);
- rbitset_cpy(env.curr_set, pred_bl->avail_out, env.rbs_size);
+ 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;
for (i = n - 1; i >= 0; --i) {
ir_node *pred = get_Block_cfgpred_block(block, i);
block_t *pred_bl = get_block_entry(pred);
- memop_t *e = find_address_avail(pred_bl, &op->value);
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_effective_block(op->value.address, block, i);
+ 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 is cannot be moved into predecessor %+F\n", op->node, pred));
+ 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));
assert(last_mem != NULL);
adr = phi_translate(op->value.address, block, i);
- load = new_rd_Load(db, current_ir_graph, pred, last_mem, adr, mode, cons_none);
- def = new_r_Proj(current_ir_graph, pred, load, mode, pn_Load_res);
+ 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(current_ir_graph, pred, load, mode_M, pn_Load_M);
+ 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;
}
in[i] = conv_to(pred_bl->avail->value.value, mode);
}
- phi = new_r_Phi(current_ir_graph, block, n, in, 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);
/* 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 (!rbitset_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
+ if (!rbitsets_equal(bl->avail_out, env.curr_set, env.rbs_size)) {
/* the avail set has changed */
- rbitset_cpy(bl->avail_out, env.curr_set, env.rbs_size);
+ rbitset_copy(bl->avail_out, env.curr_set, env.rbs_size);
dump_curr(bl, "Avail_out*");
return 1;
}
/**
* Insert Loads upwards.
*/
-static void insert_Loads_upwards(void) {
+static void insert_Loads_upwards(void)
+{
int i, need_iter;
block_t *bl;
*
* @param irg the graph to operate on
*/
-static void kill_unreachable_blocks(ir_graph *irg) {
+static void kill_unreachable_blocks(ir_graph *irg)
+{
block_t *bl;
ir_node **ins;
int changed = 0;
}
} /* kill_unreachable_blocks */
-int opt_ldst(ir_graph *irg) {
- block_t *bl;
- ir_graph *rem = current_ir_graph;
-
- current_ir_graph = irg;
+int opt_ldst(ir_graph *irg)
+{
+ block_t *bl;
FIRM_DBG_REGISTER(dbg, "firm.opt.ldst");
-// firm_dbg_set_mask(dbg, -1);
DB((dbg, LEVEL_1, "\nDoing Load/Store optimization on %+F\n", irg));
/* we need landing pads */
remove_critical_cf_edges(irg);
-// dump_ir_block_graph(irg, "-XXX");
-
if (get_opt_alias_analysis()) {
assure_irg_entity_usage_computed(irg);
assure_irp_globals_entity_usage_computed();
}
obstack_init(&env.obst);
- ir_nodemap_init(&env.adr_map);
+ ir_nodehashmap_init(&env.adr_map);
env.forward = NULL;
env.backward = NULL;
/* create address sets: for now, only the existing addresses are allowed plus one
needed for the sentinel */
- env.rbs_size = env.n_mem_ops + 1;
+ env.rbs_size = env.curr_adr_id + 1;
/* create the current set */
env.curr_set = rbitset_obstack_alloc(&env.obst, env.rbs_size);
memset(bl->id_2_memop_antic, 0, env.rbs_size * sizeof(bl->id_2_memop_antic[0]));
}
-// dump_block_list(&env);
+ (void) dump_block_list;
calcAvail();
calcAntic();
/* not only invalidate but free them. We might allocate new out arrays
on our obstack which will be deleted yet. */
free_irg_outs(irg);
- set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
+ clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE);
}
end:
ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_BLOCK_MARK);
- ir_nodemap_destroy(&env.adr_map);
+ ir_nodehashmap_destroy(&env.adr_map);
obstack_free(&env.obst, NULL);
-// dump_ir_block_graph(irg, "-YYY");
-
#ifdef DEBUG_libfirm
DEL_ARR_F(env.id_2_address);
#endif
- current_ir_graph = rem;
return env.changed != 0;
} /* opt_ldst */
+
+ir_graph_pass_t *opt_ldst_pass(const char *name)
+{
+ return def_graph_pass_ret(name ? name : "ldst_df", opt_ldst);
+} /* opt_ldst_pass */
projects / libfirm / blobdiff