projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
fixed some bugs
[libfirm]
/
ir
/
be
/
becopyilp2.c
diff --git
a/ir/be/becopyilp2.c
b/ir/be/becopyilp2.c
index
5cf5556
..
93cb741
100644
(file)
--- a/
ir/be/becopyilp2.c
+++ b/
ir/be/becopyilp2.c
@@
-4,25
+4,26
@@
* Copyright: (c) Universitaet Karlsruhe
* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*
* Copyright: (c) Universitaet Karlsruhe
* Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*
+ *
* ILP formalization using G=(V, E, Q):
* ILP formalization using G=(V, E, Q):
- * -
1 class of variables: equal color vars
+ * -
2 class of variables: coloring vars x_ic and equal color vars y_ij
* - Path constraints
* - Path constraints
- * - Clique
path
constraints
+ * - Clique
-star
constraints
*
*
* \min \sum_{ (i,j) \in Q } w_ij y_ij
*
*
*
* \min \sum_{ (i,j) \in Q } w_ij y_ij
*
- *
y_ij = 1 (i,j) \in E
+ *
\sum_c x_nc = 1 n \in N, c \in C
*
*
- *
\sum_c y_nc = |C| - 1 n \in N, c \in C
+ *
x_nc = 0 n \in N, c \not\in C(n)
*
*
- *
y_nc = 1 n \in N, c \not\in C(n)
+ *
\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 c
p} y_e >= |cp| - 1 cp \in CP clique-path
constraints
+ * \sum_{e \in c
s} y_e >= |cs| - 1 cs \in CP clique-star
constraints
*
*
- * y_ij \in N, w_ij \in R^+
+ *
x_nc,
y_ij \in N, w_ij \in R^+
*/
#ifdef HAVE_CONFIG_H
*/
#ifdef HAVE_CONFIG_H
@@
-31,9
+32,11
@@
#ifdef WITH_ILP
#ifdef WITH_ILP
+#include "irtools.h"
+#include "irgwalk.h"
#include "becopyilp_t.h"
#include "beifg_t.h"
#include "becopyilp_t.h"
#include "beifg_t.h"
-#include "
irtools
.h"
+#include "
besched_t
.h"
#define DEBUG_LVL 1
#define DEBUG_LVL 1
@@
-103,13
+106,13
@@
static void build_interference_cstr(ilp_env_t *ienv) {
int i, col;
void *iter = be_ifg_cliques_iter_alloca(ifg);
int i, col;
void *iter = be_ifg_cliques_iter_alloca(ifg);
- ir_node *clique = alloca(sizeof(*clique) * n_colors);
+ ir_node *
*
clique = alloca(sizeof(*clique) * n_colors);
int size;
char buf[16];
/* for each maximal clique */
int size;
char buf[16];
/* for each maximal clique */
- be_ifg_foreach_clique(ifg, iter,
&
clique, &size) {
+ be_ifg_foreach_clique(ifg, iter, clique, &size) {
if (size < 2)
continue;
if (size < 2)
continue;
@@
-119,7
+122,7
@@
static void build_interference_cstr(ilp_env_t *ienv) {
int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
/* for each member of this clique */
int cst_idx = lpp_add_cst(lpp, NULL, lpp_less, 1.0);
/* for each member of this clique */
- for (i=0; i<size
,
++i) {
+ for (i=0; i<size
;
++i) {
ir_node *irn = clique[i];
if (!sr_is_removed(ienv->sr, irn)) {
ir_node *irn = clique[i];
if (!sr_is_removed(ienv->sr, irn)) {
@@
-169,11
+172,17
@@
static void build_affinity_cstr(ilp_env_t *ienv) {
}
}
}
}
-static void build_path_cstr(ilp_env_t *ienv) {
+/**
+ *
+ */
+static void build_clique_star_cstr(ilp_env_t *ienv) {
}
}
-static void build_clique_path_cstr(ilp_env_t *ienv) {
+/**
+ *
+ */
+static void build_path_cstr(ilp_env_t *ienv) {
}
}
@@
-185,8
+194,8
@@
static void ilp2_build(ilp_env_t *ienv) {
build_coloring_cstr(ienv);
build_interference_cstr(ienv);
build_affinity_cstr(ienv);
build_coloring_cstr(ienv);
build_interference_cstr(ienv);
build_affinity_cstr(ienv);
+ build_clique_star_cstr(ienv);
build_path_cstr(ienv);
build_path_cstr(ienv);
- build_clique_path_cstr(ienv);
lower_bound = co_get_lower_bound(ienv->co) - co_get_inevit_copy_costs(ienv->co);
lpp_set_bound(ienv->lp, lower_bound);
lower_bound = co_get_lower_bound(ienv->co) - co_get_inevit_copy_costs(ienv->co);
lpp_set_bound(ienv->lp, lower_bound);
@@
-195,9
+204,9
@@
static void ilp2_build(ilp_env_t *ienv) {
static void ilp2_apply(ilp_env_t *ienv) {
local_env_t *lenv = ienv->env;
static void ilp2_apply(ilp_env_t *ienv) {
local_env_t *lenv = ienv->env;
- double
sol[]
;
+ double
*sol
;
lpp_sol_state_t state;
lpp_sol_state_t state;
- int count;
+ int
i,
count;
count = lenv->last_x_var - lenv->first_x_var + 1;
sol = xmalloc(count * sizeof(sol[0]));
count = lenv->last_x_var - lenv->first_x_var + 1;
sol = xmalloc(count * sizeof(sol[0]));
@@
-208,7
+217,6
@@
static void ilp2_apply(ilp_env_t *ienv) {
}
for (i=0; i<count; ++i) {
}
for (i=0; i<count; ++i) {
- char c;
int nodenr, color;
char var_name[16];
int nodenr, color;
char var_name[16];