projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Improved doxygen docu.
[libfirm]
/
ir
/
be
/
becopyilp2.c
diff --git
a/ir/be/becopyilp2.c
b/ir/be/becopyilp2.c
index
b0cd699
..
36dad10
100644
(file)
--- a/
ir/be/becopyilp2.c
+++ b/
ir/be/becopyilp2.c
@@
-30,19
+30,19
@@
* - Clique-star constraints
*
*
* - Clique-star constraints
*
*
- *
\min \sum_{ (i,j) \in Q } w_ij y_ij
+ * \min \sum_{ (i,j) \in Q } w_ij y_ij
*
*
- *
\sum_c x_nc = 1
n \in N, c \in C
+ *
\sum_c x_nc = 1
n \in N, c \in C
*
*
- *
x_nc = 0
n \in N, c \not\in C(n)
+ *
x_nc = 0
n \in N, c \not\in C(n)
*
*
- *
\sum x_nc <= 1
x_nc \in Clique \in AllCliques, c \in C
+ *
\sum x_nc <= 1
x_nc \in Clique \in AllCliques, c \in C
*
*
- *
\sum_{e \in p} y_e >= 1 p \in P
path constraints
+ *
\sum_{e \in p} y_e >= 1 p \in P
path constraints
*
*
- *
\sum_{e \in cs} y_e >= |cs| - 1 cs \in CP
clique-star constraints
+ *
\sum_{e \in cs} y_e >= |cs| - 1 cs \in CP
clique-star constraints
*
*
- *
x_nc, y_ij \in N, w_ij \in R^+
+ * x_nc, y_ij \in N, w_ij \in R^+
*/
#include "config.h"
*/
#include "config.h"
@@
-55,12
+55,13
@@
#include "irtools.h"
#include "irgwalk.h"
#include "becopyilp_t.h"
#include "irtools.h"
#include "irgwalk.h"
#include "becopyilp_t.h"
-#include "beifg_t.h"
-#include "besched_t.h"
+#include "beifg.h"
+#include "besched.h"
+#include "bemodule.h"
#define DEBUG_LVL 1
#define DEBUG_LVL 1
-typedef struct
_
local_env_t {
+typedef struct local_env_t {
double time_limit;
int first_x_var, last_x_var;
int n_colors;
double time_limit;
int first_x_var, last_x_var;
int n_colors;
@@
-69,18
+70,19
@@
typedef struct _local_env_t {
DEBUG_ONLY(firm_dbg_module_t *dbg;)
} local_env_t;
DEBUG_ONLY(firm_dbg_module_t *dbg;)
} local_env_t;
-static void build_coloring_cstr(ilp_env_t *ienv) {
+static void build_coloring_cstr(ilp_env_t *ienv)
+{
be_ifg_t *ifg = ienv->co->cenv->ifg;
be_ifg_t *ifg = ienv->co->cenv->ifg;
-
void *iter = be_ifg_nodes_iter_alloca(ifg)
;
+
nodes_iter_t iter
;
bitset_t *colors;
ir_node *irn;
char buf[16];
colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls));
bitset_t *colors;
ir_node *irn;
char buf[16];
colors = bitset_alloca(arch_register_class_n_regs(ienv->co->cls));
- be_ifg_foreach_node(ifg, iter, irn)
+ be_ifg_foreach_node(ifg,
&
iter, irn)
if (!sr_is_removed(ienv->sr, irn)) {
if (!sr_is_removed(ienv->sr, irn)) {
-
bitset_pos
_t col;
+
size
_t col;
int cst_idx;
const arch_register_req_t *req;
int curr_node_color = get_irn_col(irn);
int cst_idx;
const arch_register_req_t *req;
int curr_node_color = get_irn_col(irn);
@@
-131,7
+133,7
@@
static void build_interference_cstr(ilp_env_t *ienv)
local_env_t *lenv = ienv->env;
be_ifg_t *ifg = ienv->co->cenv->ifg;
int n_colors = lenv->n_colors;
local_env_t *lenv = ienv->env;
be_ifg_t *ifg = ienv->co->cenv->ifg;
int n_colors = lenv->n_colors;
-
void *iter = be_ifg_cliques_iter_alloca(ifg)
;
+
cliques_iter_t iter
;
ir_node **clique = ALLOCAN(ir_node*, n_colors);
int size;
int col;
ir_node **clique = ALLOCAN(ir_node*, n_colors);
int size;
int col;
@@
-140,7
+142,7
@@
static void build_interference_cstr(ilp_env_t *ienv)
char buf[16];
/* for each maximal clique */
char buf[16];
/* for each maximal clique */
- be_ifg_foreach_clique(ifg, iter, clique, &size) {
+ be_ifg_foreach_clique(ifg,
&
iter, clique, &size) {
int realsize = 0;
for (i=0; i<size; ++i)
int realsize = 0;
for (i=0; i<size; ++i)
@@
-173,7
+175,8
@@
static void build_interference_cstr(ilp_env_t *ienv)
* by walking over all affinity edges. Graph structure
* does not provide this walker, yet.
*/
* by walking over all affinity edges. Graph structure
* does not provide this walker, yet.
*/
-static void build_affinity_cstr(ilp_env_t *ienv) {
+static void build_affinity_cstr(ilp_env_t *ienv)
+{
local_env_t *lenv = ienv->env;
int n_colors = lenv->n_colors;
unit_t *curr;
local_env_t *lenv = ienv->env;
int n_colors = lenv->n_colors;
unit_t *curr;
@@
-215,11
+218,12
@@
static void build_affinity_cstr(ilp_env_t *ienv) {
/**
* Helping stuff for build_clique_star_cstr
*/
/**
* Helping stuff for build_clique_star_cstr
*/
-typedef struct
_
edge_t {
+typedef struct edge_t {
ir_node *n1, *n2;
} edge_t;
ir_node *n1, *n2;
} edge_t;
-static int compare_edge_t(const void *k1, const void *k2, size_t size) {
+static int compare_edge_t(const void *k1, const void *k2, size_t size)
+{
const edge_t *e1 = k1;
const edge_t *e2 = k2;
(void) size;
const edge_t *e1 = k1;
const edge_t *e2 = k2;
(void) size;
@@
-229,7
+233,8
@@
static int compare_edge_t(const void *k1, const void *k2, size_t size) {
#define HASH_EDGE(e) (hash_irn((e)->n1) ^ hash_irn((e)->n2))
#define HASH_EDGE(e) (hash_irn((e)->n1) ^ hash_irn((e)->n2))
-static inline edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) {
+static inline edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counter)
+{
edge_t new_edge;
if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
edge_t new_edge;
if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
@@
-243,7
+248,8
@@
static inline edge_t *add_edge(set *edges, ir_node *n1, ir_node *n2, int *counte
return set_insert(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
}
return set_insert(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
}
-static inline edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) {
+static inline edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2)
+{
edge_t new_edge;
if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
edge_t new_edge;
if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
@@
-256,7
+262,8
@@
static inline edge_t *find_edge(set *edges, ir_node *n1, ir_node *n2) {
return set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
}
return set_find(edges, &new_edge, sizeof(new_edge), HASH_EDGE(&new_edge));
}
-static inline void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counter) {
+static inline void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counter)
+{
edge_t new_edge, *e;
if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
edge_t new_edge, *e;
if (PTR_TO_INT(n1) < PTR_TO_INT(n2)) {
@@
-274,14
+281,15
@@
static inline void remove_edge(set *edges, ir_node *n1, ir_node *n2, int *counte
}
}
}
}
-#define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset))
+#define pset_foreach(pset, irn) for
(irn=pset_first(pset); irn; irn=pset_next(pset))
/**
* Search for an interference clique and an external node
* with affinity edges to all nodes of the clique.
* At most 1 node of the clique can be colored equally with the external node.
*/
/**
* Search for an interference clique and an external node
* with affinity edges to all nodes of the clique.
* At most 1 node of the clique can be colored equally with the external node.
*/
-static void build_clique_star_cstr(ilp_env_t *ienv) {
+static void build_clique_star_cstr(ilp_env_t *ienv)
+{
affinity_node_t *aff;
/* for each node with affinity edges */
affinity_node_t *aff;
/* for each node with affinity edges */
@@
-293,7
+301,7
@@
static void build_clique_star_cstr(ilp_env_t *ienv) {
set *edges;
int i, o, n_nodes, n_edges;
set *edges;
int i, o, n_nodes, n_edges;
- if (arch_irn_is
(aff->irn, ignore
))
+ if (arch_irn_is
_ignore(aff->irn
))
continue;
obstack_init(&ob);
continue;
obstack_init(&ob);
@@
-302,7
+310,7
@@
static void build_clique_star_cstr(ilp_env_t *ienv) {
/* get all affinity neighbours */
n_nodes = 0;
co_gs_foreach_neighb(aff, nbr) {
/* get all affinity neighbours */
n_nodes = 0;
co_gs_foreach_neighb(aff, nbr) {
- if (!arch_irn_is
(nbr->irn, ignore
)) {
+ if (!arch_irn_is
_ignore(nbr->irn
)) {
obstack_ptr_grow(&ob, nbr->irn);
++n_nodes;
}
obstack_ptr_grow(&ob, nbr->irn);
++n_nodes;
}
@@
-395,7
+403,8
@@
static void build_clique_star_cstr(ilp_env_t *ienv) {
}
}
-static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) {
+static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn)
+{
be_ifg_t *ifg = ienv->co->cenv->ifg;
int i, len;
ir_node **curr_path;
be_ifg_t *ifg = ienv->co->cenv->ifg;
int i, len;
ir_node **curr_path;
@@
-406,7
+415,7
@@
static void extend_path(ilp_env_t *ienv, pdeq *path, const ir_node *irn) {
if (pdeq_contains(path, irn))
return;
if (pdeq_contains(path, irn))
return;
- if (arch_irn_is
(irn, ignore
))
+ if (arch_irn_is
_ignore(irn
))
return;
/* insert the new irn */
return;
/* insert the new irn */
@@
-466,7
+475,8
@@
end:
* edges in between.
* Then at least one of these affinity edges must break.
*/
* edges in between.
* Then at least one of these affinity edges must break.
*/
-static void build_path_cstr(ilp_env_t *ienv) {
+static void build_path_cstr(ilp_env_t *ienv)
+{
affinity_node_t *aff_info;
/* for each node with affinity edges */
affinity_node_t *aff_info;
/* for each node with affinity edges */
@@
-479,7
+489,8
@@
static void build_path_cstr(ilp_env_t *ienv) {
}
}
}
}
-static void ilp2_build(ilp_env_t *ienv) {
+static void ilp2_build(ilp_env_t *ienv)
+{
local_env_t *lenv = ienv->env;
int lower_bound;
local_env_t *lenv = ienv->env;
int lower_bound;
@@
-495,7
+506,8
@@
static void ilp2_build(ilp_env_t *ienv) {
lpp_set_time_limit(ienv->lp, lenv->time_limit);
}
lpp_set_time_limit(ienv->lp, lenv->time_limit);
}
-static void ilp2_apply(ilp_env_t *ienv) {
+static void ilp2_apply(ilp_env_t *ienv)
+{
local_env_t *lenv = ienv->env;
int i;
local_env_t *lenv = ienv->env;
int i;
@@
-539,7
+551,18
@@
static void ilp2_apply(ilp_env_t *ienv) {
#endif
}
#endif
}
-int co_solve_ilp2(copy_opt_t *co) {
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyilp2);
+void be_init_copyilp2(void)
+{
+ static co_algo_info copyheur = {
+ co_solve_ilp2, 1
+ };
+
+ be_register_copyopt("ilp", ©heur);
+}
+
+int co_solve_ilp2(copy_opt_t *co)
+{
lpp_sol_state_t sol_state;
ilp_env_t *ienv;
local_env_t my;
lpp_sol_state_t sol_state;
ilp_env_t *ienv;
local_env_t my;
@@
-555,8
+578,8
@@
int co_solve_ilp2(copy_opt_t *co) {
my.normal_colors = bitset_alloca(arch_register_class_n_regs(co->cls));
bitset_clear_all(my.normal_colors);
my.normal_colors = bitset_alloca(arch_register_class_n_regs(co->cls));
bitset_clear_all(my.normal_colors);
-
arch_put_non_ignore_regs(
co->cls, my.normal_colors);
- my.n_colors = bitset_popcnt(my.normal_colors);
+
be_put_allocatable_regs(co->irg,
co->cls, my.normal_colors);
+ my.n_colors = bitset_popc
ou
nt(my.normal_colors);
ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my);
ienv = new_ilp_env(co, ilp2_build, ilp2_apply, &my);
@@
-570,7
+593,8
@@
int co_solve_ilp2(copy_opt_t *co) {
#else /* WITH_ILP */
#else /* WITH_ILP */
-static inline void only_that_you_can_compile_without_WITH_ILP_defined(void) {
+static inline void only_that_you_can_compile_without_WITH_ILP_defined(void)
+{
}
#endif /* WITH_ILP */
}
#endif /* WITH_ILP */