From 1013579946ac0cdb7e1461a6b52006e01d87716b Mon Sep 17 00:00:00 2001 From: Sebastian Hack Date: Tue, 20 Sep 2005 12:50:32 +0000 Subject: [PATCH] Added uses module --- ir/be/beuses.c | 168 +++++++++++++++++++++++++++++++++++++++++++++++ ir/be/beuses.h | 30 +++++++++ ir/be/beuses_t.h | 49 ++++++++++++++ 3 files changed, 247 insertions(+) create mode 100644 ir/be/beuses.c create mode 100644 ir/be/beuses.h create mode 100644 ir/be/beuses_t.h diff --git a/ir/be/beuses.c b/ir/be/beuses.c new file mode 100644 index 000000000..9d2c7dadc --- /dev/null +++ b/ir/be/beuses.c @@ -0,0 +1,168 @@ +/** + * @file beuse.c + * @date 27.06.2005 + * @author Sebastian Hack + * + * Methods to compute when a value will be used again. + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#include +#include + +#include "config.h" +#include "obst.h" +#include "pmap.h" +#include "debug.h" + +#include "irgwalk.h" +#include "irnode_t.h" +#include "ircons_t.h" +#include "irgraph_t.h" +#include "iredges_t.h" +#include "irdom_t.h" + +#include "be_t.h" +#include "beutil.h" +#include "belive_t.h" +#include "benode_t.h" +#include "besched_t.h" +#include "beirgmod.h" +#include "bearch.h" +#include "beuses_t.h" + +typedef struct _be_use_t { + const ir_node *bl; + const ir_node *irn; + unsigned next_use; +} be_use_t; + +struct _be_uses_t { + set *uses; + ir_graph *irg; + firm_dbg_module_t *dbg; + const arch_env_t *arch_env; +}; + + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) + +static INLINE unsigned sadd(unsigned a, unsigned b) +{ + return a + b; +} + +static INLINE unsigned sdiv(unsigned a, unsigned b) +{ + return a / b; +} + +static int cmp_use(const void *a, const void *b, size_t n) +{ + const be_use_t *p = a; + const be_use_t *q = b; + return !(p->bl == q->bl && p->irn == q->irn); +} + +static INLINE be_use_t *get_or_set_use(be_uses_t *uses, + const ir_node *bl, const ir_node *irn, unsigned next_use) +{ + unsigned hash = HASH_COMBINE(HASH_PTR(bl), HASH_PTR(irn)); + be_use_t templ; + + templ.bl = bl; + templ.irn = irn; + templ.next_use = next_use; + return set_insert(uses->uses, &templ, sizeof(templ), hash); +} + +unsigned be_get_next_use(be_uses_t *uses, const ir_node *from, + unsigned from_step, const ir_node *def); + +static unsigned get_next_use_bl(be_uses_t *uses, const ir_node *bl, + const ir_node *def) +{ + be_use_t *u; + + u = get_or_set_use(uses, bl, def, 0); + if(USES_IS_INIFINITE(u->next_use)) + return u->next_use; + + u->next_use = USES_INFINITY; + u->next_use = be_get_next_use(uses, sched_first(bl), 0, def); + return u->next_use; +} + +unsigned be_get_next_use(be_uses_t *uses, + const ir_node *from, unsigned from_step, const ir_node *def) +{ + unsigned next_use = USES_INFINITY; + unsigned step = from_step; + unsigned n = 0; + const ir_node *irn; + const ir_node *bl = get_block(from); + const ir_edge_t *succ_edge; + + sched_foreach_from(from, irn) { + int i, n; + + for(i = 0, n = get_irn_arity(irn); i < n; ++i) { + ir_node *operand = get_irn_n(irn, i); + + if(operand == def) { + DBG((uses->dbg, LEVEL_3, "found use of %+F at %+F\n", operand, irn)); + return step; + } + } + + step++; + } + + next_use = step; + foreach_block_succ(bl, succ_edge) { + const ir_node *succ_bl = succ_edge->src; + if(is_live_in(succ_bl, def)) { + unsigned next = get_next_use_bl(uses, succ_bl, def); + + DBG((uses->dbg, LEVEL_2, "\t\tnext use in succ %+F: %d\n", succ_bl, next)); + next_use = sadd(next_use, next); + n++; + } + } + + if(n > 1) + next_use = sdiv(next_use, n); + + return sadd(next_use, step); +} + +be_uses_t *be_begin_uses( + ir_graph *irg, + const arch_env_t *arch_env, + const arch_register_class_t *cls) +{ + be_uses_t *uses = malloc(sizeof(uses[0])); + + edges_assure(irg); + + uses->arch_env = arch_env; + uses->uses = new_set(cmp_use, 512); + uses->dbg = firm_dbg_register("be.uses"); + + return uses; +} + +void be_end_uses(be_uses_t *uses) +{ + del_set(uses->uses); + free(uses); +} + +int loc_compare(const void *a, const void *b) +{ + const loc_t *p = a; + const loc_t *q = b; + return p->time - q->time; +} diff --git a/ir/be/beuses.h b/ir/be/beuses.h new file mode 100644 index 000000000..06a97b0f2 --- /dev/null +++ b/ir/be/beuses.h @@ -0,0 +1,30 @@ +/** + * @file beuse.h + * @date 27.06.2005 + * @author Sebastian Hack + * + * Determine future usages of values. + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifndef _BEUSES_H +#define _BEUSES_H + +#define USES_INFINITY 1000000 +#define USES_IS_INIFINITE(x) ((x) >= USES_INFINITY) + +typedef struct _loc_t loc_t; +typedef struct _be_uses_t be_uses_t; + +unsigned be_get_next_use(be_uses_t *uses, const ir_node *from, + unsigned from_step, const ir_node *def); + +be_uses_t *be_begin_uses(ir_graph *irg, + const arch_env_t *arch_env, + const arch_register_class_t *cls); + +void be_end_uses(be_uses_t *uses); + +#endif /* _BEUSES_H */ diff --git a/ir/be/beuses_t.h b/ir/be/beuses_t.h new file mode 100644 index 000000000..73c706b6f --- /dev/null +++ b/ir/be/beuses_t.h @@ -0,0 +1,49 @@ + +/** + * @file beuses_t.h + * @date 27.06.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#ifndef _BEUSES_T_H +#define _BEUSES_T_H + +#include "firm_config.h" + +#include "beuses.h" + +/** + * An association between a node and a point in time. + */ +struct _loc_t { + const ir_node *irn; /**< A node. */ + unsigned time; /**< A time. */ +}; + +#define LOC_IS_INFINITE(loc) USES_IS_INIFINITE((loc)->time) + +/** + * Comparison function for locations. + * @param a The first location. + * @param b The second one. + * @return see qsort(3) for semantic of the compare functions. + */ +int loc_compare(const void *loc1, const void *loc2); + + +static INLINE loc_t * +be_get_next_use_loc( + be_uses_t *uses, + const loc_t *from, + loc_t *loc) +{ + loc->time = be_get_next_use(uses, from->irn, from->time, loc->irn); + return loc; +} + + + +#endif /* _BEUSES_T_H */ -- 2.20.1