becopyilp.c 7.46 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
 * @file
 * @brief       Common stuff used by all ILP formulations.
 * @author      Daniel Grund
 * @date        28.02.2006
 * @version     $Id$
26
 */
Christian Würdig's avatar
Christian Würdig committed
27
28
29
30
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif /* HAVE_CONFIG_H */

Christian Würdig's avatar
Christian Würdig committed
31
#include "irtools.h"
32
#include "irprintf.h"
Christian Würdig's avatar
Christian Würdig committed
33

34
35
#include "bestatevent.h"
#include "beirg_t.h"
Matthias Braun's avatar
fix    
Matthias Braun committed
36
#include "bemodule.h"
37
#include "error.h"
38

Matthias Braun's avatar
Matthias Braun committed
39
40
#include "lc_opts.h"
#include "lc_opts_enum.h"
41

Christian Würdig's avatar
Christian Würdig committed
42
43
#ifdef WITH_ILP

Sebastian Hack's avatar
Sebastian Hack committed
44
45
46
47
48
#define DUMP_ILP 1
#define DUMP_SOL 2

static int time_limit = 60;
static int solve_net  = 1;
Sebastian Hack's avatar
Sebastian Hack committed
49
static int solve_log  = 0;
Matthias Braun's avatar
Matthias Braun committed
50
static unsigned dump_flags = 0;
Sebastian Hack's avatar
Sebastian Hack committed
51
52
53
54
55
56
57
58
59
60
61
62

static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "ilp",   DUMP_ILP },
	{ "sol",   DUMP_SOL },
	{ NULL,    0 }
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static const lc_opt_table_entry_t options[] = {
63
64
	LC_OPT_ENT_INT      ("limit", "time limit for solving in seconds (0 for unlimited)", &time_limit),
	LC_OPT_ENT_BOOL     ("net",   "solve over the net", &solve_net),
Sebastian Hack's avatar
Sebastian Hack committed
65
	LC_OPT_ENT_BOOL     ("log",   "show ilp solving log",              &solve_log),
66
	LC_OPT_ENT_ENUM_MASK("dump",  "dump flags",             &dump_var),
67
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
68
69
};

70
void be_init_copyilp(void)
Sebastian Hack's avatar
Sebastian Hack committed
71
{
72
73
74
75
76
77
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
	lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
	lc_opt_entry_t *ilp_grp = lc_opt_get_grp(co_grp, "ilp");

Sebastian Hack's avatar
Sebastian Hack committed
78
79
	lc_opt_add_table(ilp_grp, options);
}
80
81

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyilp);
Sebastian Hack's avatar
Sebastian Hack committed
82

Daniel Grund's avatar
Daniel Grund committed
83
84
85
86
87
88
89
90
91
92
93
94
95
#include "becopyilp_t.h"
#include "beifg_t.h"

/******************************************************************************
    _____ _                        _            _   _
   / ____(_)                      | |          | | (_)
  | (___  _ _______   _ __ ___  __| |_   _  ___| |_ _  ___  _ __
   \___ \| |_  / _ \ | '__/ _ \/ _` | | | |/ __| __| |/ _ \| '_ \
   ____) | |/ /  __/ | | |  __/ (_| | |_| | (__| |_| | (_) | | | |
  |_____/|_/___\___| |_|  \___|\__,_|\__,_|\___|\__|_|\___/|_| |_|

 *****************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
96
97

size_red_t *new_size_red(copy_opt_t *co) {
98
	size_red_t *res = XMALLOC(size_red_t);
Daniel Grund's avatar
Daniel Grund committed
99
100
101
102
103
104
105
106
107

	res->co = co;
	res->all_removed = pset_new_ptr_default();
	res->col_suff = NULL;
	obstack_init(&res->ob);

	return res;
}

Daniel Grund's avatar
Daniel Grund committed
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/**
 * Checks if a node is simplicial in the graph heeding the already removed nodes.
 */
static INLINE int sr_is_simplicial(size_red_t *sr, const ir_node *ifn) {
	int i, o, size = 0;
	ir_node **all, *curr;
	be_ifg_t *ifg = sr->co->cenv->ifg;
	void *iter = be_ifg_neighbours_iter_alloca(ifg);

	all = alloca(be_ifg_degree(ifg, ifn) * sizeof(*all));

	/* get all non-removed neighbors */
	be_ifg_foreach_neighbour(ifg, iter, ifn, curr)
		if (!sr_is_removed(sr, curr))
			all[size++] = curr;

	/* check if these form a clique */
	for (i=0; i<size; ++i)
		for (o=i+1; o<size; ++o)
			if (!be_ifg_connected(ifg, all[i], all[o]))
				return 0;

	/* all edges exist so this is a clique */
	return 1;
}

void sr_remove(size_red_t *sr) {
	ir_node *irn;
	int redo = 1;
	const be_ifg_t *ifg = sr->co->cenv->ifg;
Sebastian Hack's avatar
Sebastian Hack committed
138
	void *iter = be_ifg_nodes_iter_alloca(ifg);
Daniel Grund's avatar
Daniel Grund committed
139
140
141
142

	while (redo) {
		redo = 0;
		be_ifg_foreach_node(ifg, iter, irn) {
143
			const arch_register_req_t *req = arch_get_register_req(irn, -1);
144

Matthias Braun's avatar
Matthias Braun committed
145
			if (!arch_register_req_is(req, limited) && !sr_is_removed(sr, irn) && !co_gs_is_optimizable(sr->co, irn)) {
146
				if (sr_is_simplicial(sr, irn)) {
Daniel Grund's avatar
Daniel Grund committed
147
148
149
150
151
152
153
154
155
					coloring_suffix_t *cs = obstack_alloc(&sr->ob, sizeof(*cs));

					cs->irn = irn;
					cs->next = sr->col_suff;
					sr->col_suff = cs;

					pset_insert_ptr(sr->all_removed, irn);

					redo = 1;
156
				}
Daniel Grund's avatar
Daniel Grund committed
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
			}
		}
	}
}

void sr_reinsert(size_red_t *sr) {
	coloring_suffix_t *cs;
	be_ifg_t *ifg        = sr->co->cenv->ifg;
	bitset_t *used_cols  = bitset_alloca(arch_register_class_n_regs(sr->co->cls));
	void *iter           = be_ifg_neighbours_iter_alloca(ifg);

	/* color the removed nodes in right order */
	for (cs = sr->col_suff; cs; cs = cs->next) {
		int free_col;
		ir_node *other, *irn;

		/* get free color by inspecting all neighbors */
		irn = cs->irn;
		bitset_clear_all(used_cols);

		be_ifg_foreach_neighbour(ifg, iter, irn, other) {
			if (!sr_is_removed(sr, other)) /* only inspect nodes which are in graph right now */
				bitset_set(used_cols, get_irn_col(sr->co, other));
		}

		/* now all bits not set are possible colors */
		free_col = bitset_next_clear(used_cols, 0);
		assert(free_col != -1 && "No free color found. This can not be.");
		set_irn_col(sr->co, irn, free_col);
		pset_remove_ptr(sr->all_removed, irn); /* irn is back in graph again */
	}
}

void free_size_red(size_red_t *sr) {
Daniel Grund's avatar
Daniel Grund committed
191
	del_pset(sr->all_removed);
Daniel Grund's avatar
Daniel Grund committed
192
193
194
195
196
197
198
199
200
201
202
203
204
205
	obstack_free(&sr->ob, NULL);
	free(sr);
}

/******************************************************************************
    _____                      _        _____ _      _____
   / ____|                    (_)      |_   _| |    |  __ \
  | |  __  ___ _ __   ___ _ __ _  ___    | | | |    | |__) |
  | | |_ |/ _ \ '_ \ / _ \ '__| |/ __|   | | | |    |  ___/
  | |__| |  __/ | | |  __/ |  | | (__   _| |_| |____| |
   \_____|\___|_| |_|\___|_|  |_|\___| |_____|______|_|

 *****************************************************************************/

206
207
#include <stdio.h>

Daniel Grund's avatar
Daniel Grund committed
208
ilp_env_t *new_ilp_env(copy_opt_t *co, ilp_callback build, ilp_callback apply, void *env) {
209
	ilp_env_t *res = XMALLOC(ilp_env_t);
Daniel Grund's avatar
Daniel Grund committed
210

Sebastian Hack's avatar
Sebastian Hack committed
211
212
213
214
215
	res->co         = co;
	res->build      = build;
	res->apply      = apply;
	res->env        = env;
	res->sr         = new_size_red(co);
Daniel Grund's avatar
Daniel Grund committed
216
217
218
219

	return res;
}

Daniel Grund's avatar
Daniel Grund committed
220
lpp_sol_state_t ilp_go(ilp_env_t *ienv) {
221
	be_main_env_t *main_env = ienv->co->cenv->birg->main_env;
222

Daniel Grund's avatar
Daniel Grund committed
223
224
225
	sr_remove(ienv->sr);

	ienv->build(ienv);
Sebastian Hack's avatar
Sebastian Hack committed
226
	lpp_set_time_limit(ienv->lp, time_limit);
Daniel Grund's avatar
Daniel Grund committed
227

Sebastian Hack's avatar
Sebastian Hack committed
228
229
230
	if(solve_log)
		lpp_set_log(ienv->lp, stdout);

Sebastian Hack's avatar
Sebastian Hack committed
231
232
233
	if(solve_net)
		lpp_solve_net(ienv->lp, main_env->options->ilp_server, main_env->options->ilp_solver);
	else {
Daniel Grund's avatar
Daniel Grund committed
234
#ifdef LPP_SOLVE_NET
Sebastian Hack's avatar
Sebastian Hack committed
235
		fprintf(stderr, "can only solve ilp over the net\n");
Daniel Grund's avatar
Daniel Grund committed
236
#else
Sebastian Hack's avatar
Sebastian Hack committed
237
		lpp_solve_cplex(ienv->lp);
Daniel Grund's avatar
Daniel Grund committed
238
#endif
Sebastian Hack's avatar
Sebastian Hack committed
239
	}
Daniel Grund's avatar
Daniel Grund committed
240

Sebastian Hack's avatar
Sebastian Hack committed
241
242
243
244
245
	be_stat_ev_dbl("co_ilp_objval",     ienv->lp->objval);
	be_stat_ev_dbl("co_ilp_best_bound", ienv->lp->best_bound);
	be_stat_ev    ("co_ilp_iter",       ienv->lp->iterations);
	be_stat_ev_dbl("co_ilp_sol_time",   ienv->lp->sol_time);

Sebastian Hack's avatar
Sebastian Hack committed
246
	if(dump_flags & DUMP_ILP) {
247
248
249
250
251
252
253
254
255
		char buf[128];
		FILE *f;

		ir_snprintf(buf, sizeof(buf), "%F_%s-co.ilp", ienv->co->cenv->irg,
		            ienv->co->cenv->cls->name);
		f = fopen(buf, "wt");
		if(f == NULL) {
			panic("Couldn't open '%s' for writing", buf);
		}
Sebastian Hack's avatar
Sebastian Hack committed
256
257
258
		lpp_dump_plain(ienv->lp, f);
		fclose(f);
	}
259

Daniel Grund's avatar
Daniel Grund committed
260
261
262
263
264
265
266
267
268
269
270
271
	ienv->apply(ienv);

	sr_reinsert(ienv->sr);

	return lpp_get_sol_state(ienv->lp);
}

void free_ilp_env(ilp_env_t *ienv) {
	free_size_red(ienv->sr);
	free_lpp(ienv->lp);
	free(ienv);
}
Christian Würdig's avatar
Christian Würdig committed
272
273
274

#else /* WITH_ILP */

275
static INLINE void only_that_you_can_compile_without_WITH_ILP_defined(void) {
Christian Würdig's avatar
Christian Würdig committed
276
277
278
}

#endif /* WITH_ILP */