4 * @author Sebastian Hack, Matthias Braun
6 * Methods to compute when a value will be used again.
8 * Copyright (C) 2005 Universitaet Karlsruhe
9 * Released under the GPL
26 #include "irgraph_t.h"
27 #include "iredges_t.h"
34 #include "besched_t.h"
38 #include "benodesets.h"
40 #define SCAN_INTERBLOCK_USES
42 typedef struct _be_use_t {
51 const exec_freq_t *execfreqs;
53 DEBUG_ONLY(firm_dbg_module_t *dbg;)
56 static int cmp_use(const void *a, const void *b, size_t n)
58 const be_use_t *p = a;
59 const be_use_t *q = b;
60 return !(p->block == q->block && p->node == q->node);
63 static const be_use_t *get_or_set_use_block(be_uses_t *uses,
67 unsigned hash = HASH_COMBINE(nodeset_hash(block), nodeset_hash(def));
73 result = set_find(uses->uses, &temp, sizeof(temp), hash);
76 // insert templ first as we might end in a loop in the get_next_use
78 temp.next_use = USES_INFINITY;
79 result = set_insert(uses->uses, &temp, sizeof(temp), hash);
81 result->next_use = be_get_next_use(uses, sched_first(block), 0, def, 0);
87 unsigned be_get_next_use(be_uses_t *uses, const ir_node *from,
88 unsigned from_step, const ir_node *def,
91 unsigned step = from_step;
92 ir_node *block = get_nodes_block(from);
94 const ir_edge_t *edge;
98 node = sched_next(node);
101 sched_foreach_from(from, node) {
104 arity = get_irn_arity(node);
105 for (i = 0; i < arity; ++i) {
106 const ir_node *operand = get_irn_n(node, i);
108 if (operand == def) {
109 DBG((uses->dbg, LEVEL_3, "found use of %+F at %+F\n", operand, node));
117 if(be_is_live_end(uses->lv, block, def))
120 #ifdef SCAN_INTERBLOCK_USES
122 double best_execfreq = -1;
123 unsigned next_use = USES_INFINITY;
125 foreach_block_succ(block, edge) {
127 const ir_node *succ_block = get_edge_src_irn(edge);
128 double execfreq = get_block_execfreq(uses->execfreqs, succ_block);
130 //execfreq_sum += execfreq;
132 if(execfreq > best_execfreq) {
133 best_execfreq = execfreq;
135 if(!be_is_live_in(uses->lv, succ_block, def)) {
136 next_use = USES_INFINITY;
140 use = get_or_set_use_block(uses, succ_block, def);
141 //if(USES_IS_INFINITE(use->next_use))
144 next_use = use->next_use;
147 //next_use += use->next_use / execfreq;
151 return USES_INFINITY;*/
153 //next_use /= execfreq_sum;
155 return ((unsigned) next_use) + step;
158 return USES_INFINITY;
162 be_uses_t *be_begin_uses(ir_graph *irg, const exec_freq_t *execfreqs, const be_lv_t *lv)
164 be_uses_t *uses = xmalloc(sizeof(uses[0]));
168 uses->uses = new_set(cmp_use, 512);
170 uses->execfreqs = execfreqs;
172 FIRM_DBG_REGISTER(uses->dbg, "firm.be.uses");
177 void be_end_uses(be_uses_t *uses)