projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
C99 feature removed.
[libfirm]
/
ir
/
be
/
becopyheur.c
diff --git
a/ir/be/becopyheur.c
b/ir/be/becopyheur.c
index
ab6b3d1
..
5e8805f
100644
(file)
--- a/
ir/be/becopyheur.c
+++ b/
ir/be/becopyheur.c
@@
-1,5
+1,5
@@
/*
/*
- * Copyright (C) 1995-200
7
University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-200
8
University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
*
* This file is part of libFirm.
*
@@
-32,9
+32,7
@@
* and the qnode is reinserted in the queue. The first qnode colored without
* conflicts is the best one.
*/
* and the qnode is reinserted in the queue. The first qnode colored without
* conflicts is the best one.
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
#include "config.h"
-#endif
#include "debug.h"
#include "bitset.h"
#include "debug.h"
#include "bitset.h"
@@
-43,9
+41,9
@@
#include "becopyopt_t.h"
#include "becopystat.h"
#include "becopyopt_t.h"
#include "becopystat.h"
-#include "benodesets.h"
#include "beintlive_t.h"
#include "beintlive_t.h"
-#include "beirg_t.h"
+#include "beirg.h"
+#include "bemodule.h"
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
@@
-56,7
+54,7
@@
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
#define SLOTS_CHANGED_NODES 32
#define list_entry_queue(lh) list_entry(lh, qnode_t, queue)
#define SLOTS_CHANGED_NODES 32
#define list_entry_queue(lh) list_entry(lh, qnode_t, queue)
-#define HASH_CONFLICT(c) (
nodeset_hash(c.n1) ^ nodeset_hash
(c.n2))
+#define HASH_CONFLICT(c) (
hash_irn(c.n1) ^ hash_irn
(c.n2))
/**
* Modeling additional conflicts between nodes. NOT live range interference
/**
* Modeling additional conflicts between nodes. NOT live range interference
@@
-91,12
+89,12
@@
typedef struct _qnode_t {
static pset *pinned_global; /**< optimized nodes should not be altered any more */
static pset *pinned_global; /**< optimized nodes should not be altered any more */
-static
INLINE
int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
+static
inline
int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
{
if (env->ifg)
return be_ifg_connected(env->ifg, a, b);
else
{
if (env->ifg)
return be_ifg_connected(env->ifg, a, b);
else
- return
values_interfere(env->birg
, a, b);
+ return
be_values_interfere(env->birg->lv
, a, b);
}
static int set_cmp_conflict_t(const void *x, const void *y, size_t size) {
}
static int set_cmp_conflict_t(const void *x, const void *y, size_t size) {
@@
-111,11
+109,11
@@
static int set_cmp_conflict_t(const void *x, const void *y, size_t size) {
* If a local pinned conflict occurs, a new edge in the conflict graph is added.
* The next maximum independent set build, will regard it.
*/
* If a local pinned conflict occurs, a new edge in the conflict graph is added.
* The next maximum independent set build, will regard it.
*/
-static
INLINE
void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, const ir_node *n2) {
+static
inline
void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, const ir_node *n2) {
conflict_t c;
DBG((dbg, LEVEL_4, "\t %+F -- %+F\n", n1, n2));
conflict_t c;
DBG((dbg, LEVEL_4, "\t %+F -- %+F\n", n1, n2));
- if (get_irn_
node_nr(n1) < get_irn_node_nr
(n2)) {
+ if (get_irn_
idx(n1) < get_irn_idx
(n2)) {
c.n1 = n1;
c.n2 = n2;
} else {
c.n1 = n1;
c.n2 = n2;
} else {
@@
-128,63
+126,63
@@
static INLINE void qnode_add_conflict(const qnode_t *qn, const ir_node *n1, cons
/**
* Checks if two nodes are in a conflict.
*/
/**
* Checks if two nodes are in a conflict.
*/
-static
INLINE
int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, const ir_node *n2) {
+static
inline
int qnode_are_conflicting(const qnode_t *qn, const ir_node *n1, const ir_node *n2) {
conflict_t c;
/* search for live range interference */
if (n1!=n2 && nodes_interfere(qn->ou->co->cenv, n1, n2))
return 1;
/* search for recoloring conflicts */
conflict_t c;
/* search for live range interference */
if (n1!=n2 && nodes_interfere(qn->ou->co->cenv, n1, n2))
return 1;
/* search for recoloring conflicts */
- if (get_irn_
node_nr(n1) < get_irn_node_nr
(n2)) {
+ if (get_irn_
idx(n1) < get_irn_idx
(n2)) {
c.n1 = n1;
c.n2 = n2;
} else {
c.n1 = n2;
c.n2 = n1;
}
c.n1 = n1;
c.n2 = n2;
} else {
c.n1 = n2;
c.n2 = n1;
}
- return
(int) set_find(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c))
;
+ return
set_find(qn->conflicts, &c, sizeof(c), HASH_CONFLICT(c)) != 0
;
}
static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) {
(void) size;
}
static int set_cmp_node_stat_t(const void *x, const void *y, size_t size) {
(void) size;
- return ((
node_stat_t *)x)->irn != ((node_stat_t
*)y)->irn;
+ return ((
const node_stat_t*)x)->irn != ((const node_stat_t
*)y)->irn;
}
/**
* Finds a node status entry of a node if existent. Otherwise return NULL
*/
}
/**
* Finds a node status entry of a node if existent. Otherwise return NULL
*/
-static
INLINE
node_stat_t *qnode_find_node(const qnode_t *qn, ir_node *irn) {
+static
inline const
node_stat_t *qnode_find_node(const qnode_t *qn, ir_node *irn) {
node_stat_t find;
find.irn = irn;
node_stat_t find;
find.irn = irn;
- return set_find(qn->changed_nodes, &find, sizeof(find),
nodeset_hash
(irn));
+ return set_find(qn->changed_nodes, &find, sizeof(find),
hash_irn
(irn));
}
/**
* Finds a node status entry of a node if existent. Otherwise it will return
* an initialized new entry for this node.
*/
}
/**
* Finds a node status entry of a node if existent. Otherwise it will return
* an initialized new entry for this node.
*/
-static
INLINE
node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, ir_node *irn) {
+static
inline
node_stat_t *qnode_find_or_insert_node(const qnode_t *qn, ir_node *irn) {
node_stat_t find;
find.irn = irn;
find.new_color = NO_COLOR;
find.pinned_local = 0;
node_stat_t find;
find.irn = irn;
find.new_color = NO_COLOR;
find.pinned_local = 0;
- return set_insert(qn->changed_nodes, &find, sizeof(find),
nodeset_hash
(irn));
+ return set_insert(qn->changed_nodes, &find, sizeof(find),
hash_irn
(irn));
}
/**
* Returns the virtual color of a node if set before, else returns the real color.
*/
}
/**
* Returns the virtual color of a node if set before, else returns the real color.
*/
-static
INLINE
int qnode_get_new_color(const qnode_t *qn, ir_node *irn) {
- node_stat_t *found = qnode_find_node(qn, irn);
+static
inline
int qnode_get_new_color(const qnode_t *qn, ir_node *irn) {
+
const
node_stat_t *found = qnode_find_node(qn, irn);
if (found)
return found->new_color;
else
if (found)
return found->new_color;
else
- return get_irn_col(
qn->ou->co,
irn);
+ return get_irn_col(irn);
}
/**
* Sets the virtual color of a node.
*/
}
/**
* Sets the virtual color of a node.
*/
-static
INLINE
void qnode_set_new_color(const qnode_t *qn, ir_node *irn, int color) {
+static
inline
void qnode_set_new_color(const qnode_t *qn, ir_node *irn, int color) {
node_stat_t *found = qnode_find_or_insert_node(qn, irn);
found->new_color = color;
DBG((dbg, LEVEL_3, "\t col(%+F) := %d\n", irn, color));
node_stat_t *found = qnode_find_or_insert_node(qn, irn);
found->new_color = color;
DBG((dbg, LEVEL_3, "\t col(%+F) := %d\n", irn, color));
@@
-195,8
+193,8
@@
static INLINE void qnode_set_new_color(const qnode_t *qn, ir_node *irn, int colo
* to the same optimization unit and has been optimized before the current
* processed node.
*/
* to the same optimization unit and has been optimized before the current
* processed node.
*/
-static
INLINE
int qnode_is_pinned_local(const qnode_t *qn, ir_node *irn) {
- node_stat_t *found = qnode_find_node(qn, irn);
+static
inline
int qnode_is_pinned_local(const qnode_t *qn, ir_node *irn) {
+
const
node_stat_t *found = qnode_find_node(qn, irn);
if (found)
return found->pinned_local;
else
if (found)
return found->pinned_local;
else
@@
-207,11
+205,11
@@
static INLINE int qnode_is_pinned_local(const qnode_t *qn, ir_node *irn) {
* Local-pins a node, so optimizations of further nodes of the same opt unit
* can handle situations in which a color change would undo prior optimizations.
*/
* Local-pins a node, so optimizations of further nodes of the same opt unit
* can handle situations in which a color change would undo prior optimizations.
*/
-static
INLINE
void qnode_pin_local(const qnode_t *qn, ir_node *irn) {
+static
inline
void qnode_pin_local(const qnode_t *qn, ir_node *irn) {
node_stat_t *found = qnode_find_or_insert_node(qn, irn);
found->pinned_local = 1;
if (found->new_color == NO_COLOR)
node_stat_t *found = qnode_find_or_insert_node(qn, irn);
found->pinned_local = 1;
if (found->new_color == NO_COLOR)
- found->new_color = get_irn_col(
qn->ou->co,
irn);
+ found->new_color = get_irn_col(irn);
}
}
@@
-243,7
+241,6
@@
static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const
copy_opt_t *co = qn->ou->co;
const be_chordal_env_t *chordal_env = co->cenv;
const arch_register_class_t *cls = co->cls;
copy_opt_t *co = qn->ou->co;
const be_chordal_env_t *chordal_env = co->cenv;
const arch_register_class_t *cls = co->cls;
- const arch_env_t *arch_env = co->aenv;
int irn_col = qnode_get_new_color(qn, irn);
ir_node *sub_res, *curr;
be_ifg_t *ifg = chordal_env->ifg;
int irn_col = qnode_get_new_color(qn, irn);
ir_node *sub_res, *curr;
be_ifg_t *ifg = chordal_env->ifg;
@@
-279,7
+276,7
@@
static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const
bitset_flip_all(free_cols);
/* Exclude colors not assignable to the irn */
bitset_flip_all(free_cols);
/* Exclude colors not assignable to the irn */
- req = arch_get_register_req
(arch_env, irn, -1
);
+ req = arch_get_register_req
_out(irn
);
if (arch_register_req_is(req, limited)) {
bitset_t *limited = bitset_alloca(cls->n_regs);
rbitset_copy_to_bitset(req->limited, limited);
if (arch_register_req_is(req, limited)) {
bitset_t *limited = bitset_alloca(cls->n_regs);
rbitset_copy_to_bitset(req->limited, limited);
@@
-303,7
+300,7
@@
static ir_node *qnode_color_irn(const qnode_t *qn, ir_node *irn, int col, const
#endif /* SEARCH_FREE_COLORS */
/* If target color is not allocatable changing color is impossible */
#endif /* SEARCH_FREE_COLORS */
/* If target color is not allocatable changing color is impossible */
- if (!arch_reg_
is_allocatable(arch_env, irn, -1
, arch_register_for_index(cls, col))) {
+ if (!arch_reg_
out_is_allocatable(irn
, arch_register_for_index(cls, col))) {
DBG((dbg, LEVEL_3, "\t %+F impossible\n", irn));
return CHANGE_IMPOSSIBLE;
}
DBG((dbg, LEVEL_3, "\t %+F impossible\n", irn));
return CHANGE_IMPOSSIBLE;
}
@@
-383,22
+380,22
@@
static int qnode_try_color(const qnode_t *qn) {
* Determines a maximum weighted independent set with respect to
* the interference and conflict edges of all nodes in a qnode.
*/
* Determines a maximum weighted independent set with respect to
* the interference and conflict edges of all nodes in a qnode.
*/
-static
INLINE
void qnode_max_ind_set(qnode_t *qn, const unit_t *ou) {
+static
inline
void qnode_max_ind_set(qnode_t *qn, const unit_t *ou) {
ir_node **safe, **unsafe;
int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
bitset_t *curr, *best;
bitset_pos_t pos;
ir_node **safe, **unsafe;
int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
bitset_t *curr, *best;
bitset_pos_t pos;
- int
max,
next, curr_weight, best_weight = 0;
+ int next, curr_weight, best_weight = 0;
/* assign the nodes into two groups.
* safe: node has no interference, hence it is in every max stable set.
* unsafe: node has an interference
*/
/* assign the nodes into two groups.
* safe: node has no interference, hence it is in every max stable set.
* unsafe: node has an interference
*/
- safe
= alloca((ou->node_count-1) * sizeof(*safe)
);
- safe_costs = 0;
- safe_count = 0;
- unsafe
= alloca((ou->node_count-1) * sizeof(*unsafe)
);
- unsafe_costs =
alloca((ou->node_count-1) * sizeof(*unsafe_costs)
);
+ safe
= ALLOCAN(ir_node*, ou->node_count - 1
);
+ safe_costs
= 0;
+ safe_count
= 0;
+ unsafe
= ALLOCAN(ir_node*, ou->node_count - 1
);
+ unsafe_costs =
ALLOCAN(int, ou->node_count - 1
);
unsafe_count = 0;
for(i=1; i<ou->node_count; ++i) {
int is_safe = 1;
unsafe_count = 0;
for(i=1; i<ou->node_count; ++i) {
int is_safe = 1;
@@
-442,7
+439,7
@@
static INLINE void qnode_max_ind_set(qnode_t *qn, const unit_t *ou) {
/* Exact Algorithm: Brute force */
curr = bitset_alloca(unsafe_count);
bitset_set_all(curr);
/* Exact Algorithm: Brute force */
curr = bitset_alloca(unsafe_count);
bitset_set_all(curr);
- while (
(max = bitset_popcnt(curr)) != 0
) {
+ while (
!bitset_is_empty(curr)
) {
/* check if curr is a stable set */
for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
for (o=bitset_next_set(curr, i); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to ou_max_ind_set_costs(): NOT (curr, i+1) */
/* check if curr is a stable set */
for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
for (o=bitset_next_set(curr, i); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to ou_max_ind_set_costs(): NOT (curr, i+1) */
@@
-480,12
+477,12
@@
no_stable_set:
/**
* Creates a new qnode
*/
/**
* Creates a new qnode
*/
-static
INLINE
qnode_t *new_qnode(const unit_t *ou, int color) {
- qnode_t *qn =
xmalloc(sizeof(*qn)
);
- qn->ou = ou;
- qn->color = color;
- qn->mis
= xmalloc(ou->node_count * sizeof(*qn->mis)
);
- qn->conflicts = new_set(set_cmp_conflict_t, SLOTS_CONFLICTS);
+static
inline
qnode_t *new_qnode(const unit_t *ou, int color) {
+ qnode_t *qn =
XMALLOC(qnode_t
);
+ qn->ou
= ou;
+ qn->color
= color;
+ qn->mis
= XMALLOCN(ir_node*, ou->node_count
);
+ qn->conflicts
= new_set(set_cmp_conflict_t, SLOTS_CONFLICTS);
qn->changed_nodes = new_set(set_cmp_node_stat_t, SLOTS_CHANGED_NODES);
return qn;
}
qn->changed_nodes = new_set(set_cmp_node_stat_t, SLOTS_CHANGED_NODES);
return qn;
}
@@
-493,7
+490,7
@@
static INLINE qnode_t *new_qnode(const unit_t *ou, int color) {
/**
* Frees space used by a queue node
*/
/**
* Frees space used by a queue node
*/
-static
INLINE
void free_qnode(qnode_t *qn) {
+static
inline
void free_qnode(qnode_t *qn) {
del_set(qn->conflicts);
del_set(qn->changed_nodes);
xfree(qn->mis);
del_set(qn->conflicts);
del_set(qn->changed_nodes);
xfree(qn->mis);
@@
-504,7
+501,7
@@
static INLINE void free_qnode(qnode_t *qn) {
* Inserts a qnode in the sorted queue of the optimization unit. Queue is
* ordered by field 'size' (the size of the mis) in decreasing order.
*/
* Inserts a qnode in the sorted queue of the optimization unit. Queue is
* ordered by field 'size' (the size of the mis) in decreasing order.
*/
-static
INLINE
void ou_insert_qnode(unit_t *ou, qnode_t *qn) {
+static
inline
void ou_insert_qnode(unit_t *ou, qnode_t *qn) {
struct list_head *lh;
if (qnode_are_conflicting(qn, ou->nodes[0], ou->nodes[0])) {
struct list_head *lh;
if (qnode_are_conflicting(qn, ou->nodes[0], ou->nodes[0])) {
@@
-534,12
+531,13
@@
static INLINE void ou_insert_qnode(unit_t *ou, qnode_t *qn) {
* nodes. (All other phi classes are reduced to this case.)
*/
static void ou_optimize(unit_t *ou) {
* nodes. (All other phi classes are reduced to this case.)
*/
static void ou_optimize(unit_t *ou) {
- int i;
- qnode_t *curr = NULL, *tmp;
- const arch_env_t *aenv = ou->co->aenv;
- const arch_register_class_t *cls = ou->co->cls;
- bitset_pos_t idx;
- bitset_t *pos_regs = bitset_alloca(cls->n_regs);
+ qnode_t *curr = NULL;
+ qnode_t *tmp;
+ const arch_register_req_t *req;
+ bitset_t const* ignore;
+ bitset_pos_t n_regs;
+ bitset_pos_t idx;
+ int i;
DBG((dbg, LEVEL_1, "\tOptimizing unit:\n"));
for (i=0; i<ou->node_count; ++i)
DBG((dbg, LEVEL_1, "\tOptimizing unit:\n"));
for (i=0; i<ou->node_count; ++i)
@@
-548,19
+546,32
@@
static void ou_optimize(unit_t *ou) {
/* init queue */
INIT_LIST_HEAD(&ou->queue);
/* init queue */
INIT_LIST_HEAD(&ou->queue);
- arch_get_allocatable_regs(aenv, ou->nodes[0], -1, pos_regs);
+ req = arch_get_register_req_out(ou->nodes[0]);
+ ignore = ou->co->cenv->ignore_colors;
+ n_regs = req->cls->n_regs;
+ if (arch_register_req_is(req, limited)) {
+ rawbs_base_t const* limited = req->limited;
- /* exclude ingore colors */
- bitset_andnot(pos_regs, ou->co->cenv->ignore_colors);
+ for (idx = 0; idx != n_regs; ++idx) {
+ if (bitset_is_set(ignore, idx))
+ continue;
+ if (!rbitset_is_set(limited, idx))
+ continue;
- assert(bitset_popcnt(pos_regs) != 0 && "No register is allowed for this node !!?");
+ ou_insert_qnode(ou, new_qnode(ou, idx));
+ }
+ } else {
+ for (idx = 0; idx != n_regs; ++idx) {
+ if (bitset_is_set(ignore, idx))
+ continue;
- /* create new qnode */
- bitset_foreach(pos_regs, idx)
- ou_insert_qnode(ou, new_qnode(ou, idx));
+ ou_insert_qnode(ou, new_qnode(ou, idx));
+ }
+ }
/* search best */
/* search best */
- while (!list_empty(&ou->queue)) {
+ for (;;) {
+ assert(!list_empty(&ou->queue));
/* get head of queue */
curr = list_entry_queue(ou->queue.next);
list_del(&curr->queue);
/* get head of queue */
curr = list_entry_queue(ou->queue.next);
list_del(&curr->queue);
@@
-606,9
+617,12
@@
static void ou_optimize(unit_t *ou) {
free_qnode(curr);
}
free_qnode(curr);
}
+/**
+ * Solves the problem using a heuristic approach
+ * Uses the OU data structure
+ */
int co_solve_heuristic(copy_opt_t *co) {
unit_t *curr;
int co_solve_heuristic(copy_opt_t *co) {
unit_t *curr;
- FIRM_DBG_REGISTER(dbg, "ir.be.copyoptheur");
ASSERT_OU_AVAIL(co);
ASSERT_OU_AVAIL(co);
@@
-620,3
+634,15
@@
int co_solve_heuristic(copy_opt_t *co) {
del_pset(pinned_global);
return 0;
}
del_pset(pinned_global);
return 0;
}
+
+void be_init_copyheur(void)
+{
+ static co_algo_info copyheur = {
+ co_solve_heuristic, 0
+ };
+
+ be_register_copyopt("heur1", ©heur);
+ FIRM_DBG_REGISTER(dbg, "ir.be.copyoptheur");
+}
+
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyheur);