bepbqpcoloring.c 25.3 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
3
 *
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 * 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.
 */

/**
 * @file
 * @brief       PBQP based register allocation.
 * @author      Thomas Bersch
 * @date        27.11.2009
 * @version     $Id: bechordal.c 26750 2009-11-27 09:37:43Z bersch $
26
27
 */

28
/* miscellaneous includes */
29
#include "config.h"
30
31
32

#ifdef FIRM_KAPS

33
34
35
36
#include "debug.h"
#include "error.h"

#include "irdom.h"
yb9976's avatar
yb9976 committed
37
#include "irdump.h"
38
39
40
41
42
#include "iredges_t.h"
#include "irprintf.h"
#include "irgwalk.h"
#include "time.h"

43
44
45
/* libfirm/ir/adt includes */
#include "bipartite.h"

46
47
48
49
50
/* libfirm/ir/be includes */
#include "bearch.h"
#include "beirg.h"
#include "besched.h"
#include "bemodule.h"
51
#include "bechordal_common.h"
52
53
54
55
56
57
58
59
60
#include "bechordal.h"
#include "bechordal_t.h"
#include "beinsn_t.h"
#include "benode.h"
#include "belive.h"
#include "belive_t.h"
#include "beutil.h"
#include "plist.h"
#include "pqueue.h"
Thomas Bersch's avatar
Thomas Bersch committed
61
#include "becopyopt.h"
62
63
64
65
66
67

/* pbqp includes */
#include "kaps.h"
#include "matrix.h"
#include "vector.h"
#include "vector_t.h"
yb9976's avatar
yb9976 committed
68
#include "heuristical_co.h"
69
#include "heuristical_co_ld.h"
70
71
72
73
#include "pbqp_t.h"
#include "html_dumper.h"
#include "pbqp_node_t.h"
#include "pbqp_node.h"
74
#include "pbqp_edge_t.h"
75

yb9976's avatar
yb9976 committed
76
77
78
79
#define TIMER                 0
#define PRINT_RPEO            0
#define USE_BIPARTIT_MATCHING 0
#define DO_USEFUL_OPT         1
Thomas Bersch's avatar
Thomas Bersch committed
80
81


yb9976's avatar
yb9976 committed
82
83
static int use_exec_freq     = true;
static int use_late_decision = false;
84

85
typedef struct be_pbqp_alloc_env_t {
86
	pbqp_t                      *pbqp_inst;         /**< PBQP instance for register allocation */
87
	ir_graph                    *irg;               /**< The graph under examination. */
88
	const arch_register_class_t *cls;               /**< Current processed register class */
89
	be_lv_t                     *lv;
90
	bitset_t                    *allocatable_regs;
91
92
	pbqp_matrix_t               *ife_matrix_template;
	pbqp_matrix_t               *aff_matrix_template;
yb9976's avatar
yb9976 committed
93
94
95
96
	plist_t                     *rpeo;
	unsigned                    *restr_nodes;
	unsigned                    *ife_edge_num;
	be_chordal_env_t            *env;
97
98
99
} be_pbqp_alloc_env_t;


yb9976's avatar
yb9976 committed
100
101
102
103
104
#define is_Reg_Phi(irn)                                        (is_Phi(irn) && mode_is_data(get_irn_mode(irn)))
#define get_Perm_src(irn)                                      (get_irn_n(get_Proj_pred(irn), get_Proj_proj(irn)))
#define is_Perm_Proj(irn)                                      (is_Proj(irn) && be_is_Perm(get_Proj_pred(irn)))
#define insert_edge(pbqp, src_node, trg_node, template_matrix) (add_edge_costs(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node), pbqp_matrix_copy(pbqp, template_matrix)))
#define get_free_regs(restr_nodes, cls, irn)                   (arch_register_class_n_regs(cls) - restr_nodes[get_irn_idx(irn)])
105
106
107
108
109
110

static inline int is_2addr_code(const arch_register_req_t *req)
{
	return (req->type & arch_register_req_type_should_be_same) != 0;
}

Thomas Bersch's avatar
Thomas Bersch committed
111
static const lc_opt_table_entry_t options[] = {
yb9976's avatar
yb9976 committed
112
113
	LC_OPT_ENT_BOOL("exec_freq", "use exec_freq",  &use_exec_freq),
	LC_OPT_ENT_BOOL("late_decision", "use late decision for register allocation",  &use_late_decision),
Thomas Bersch's avatar
Thomas Bersch committed
114
115
	LC_OPT_LAST
};
116
117
118
119

#if KAPS_DUMP
static FILE *my_open(const be_chordal_env_t *env, const char *prefix, const char *suffix)
{
yb9976's avatar
yb9976 committed
120
121
122
123
124
	FILE       *result;
	char        buf[1024];
	size_t      i;
	size_t      n;
	char       *tu_name;
125
	const char *cup_name = be_get_irg_main_env(env->irg)->cup_name;
126

127
	n = strlen(cup_name);
128
	tu_name = XMALLOCN(char, n + 1);
129
	strcpy(tu_name, cup_name);
130
131
132
133
134
135
136
	for (i = 0; i < n; ++i)
		if (tu_name[i] == '.')
			tu_name[i] = '_';

	ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg, env->cls->name, suffix);
	xfree(tu_name);
	result = fopen(buf, "wt");
137
	if (result == NULL) {
138
139
140
141
142
143
144
145
		panic("Couldn't open '%s' for writing.", buf);
	}

	return result;
}
#endif


146
147
static void create_pbqp_node(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *irn)
{
148
	const arch_register_class_t *cls = pbqp_alloc_env->cls;
149
	pbqp_t   *pbqp_inst              = pbqp_alloc_env->pbqp_inst;
150
	bitset_t *allocatable_regs       = pbqp_alloc_env->allocatable_regs;
151
152
153
154
	unsigned  colors_n               = arch_register_class_n_regs(cls);
	unsigned  cntConstrains          = 0;

	/* create costs vector depending on register constrains */
155
	vector_t *costs_vector = vector_alloc(pbqp_inst, colors_n);
156
157
158

	/* set costs depending on register constrains */
	unsigned idx;
159
	for (idx = 0; idx < colors_n; idx++) {
160
		if (!bitset_is_set(allocatable_regs, idx) || !arch_reg_out_is_allocatable(irn, arch_register_for_index(cls, idx))) {
161
			/* constrained */
162
163
164
165
166
167
168
			vector_set(costs_vector, idx, INF_COSTS);
			cntConstrains++;
		}
	}

	/* add vector to pbqp node */
	add_node_costs(pbqp_inst, get_irn_idx(irn), costs_vector);
Thomas Bersch's avatar
Thomas Bersch committed
169
170
171
	pbqp_alloc_env->restr_nodes[get_irn_idx(irn)] = cntConstrains;
}

Matthias Braun's avatar
Matthias Braun committed
172
173
static void insert_ife_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node)
{
174
	pbqp_t                      *pbqp                = pbqp_alloc_env->pbqp_inst;
Thomas Bersch's avatar
Thomas Bersch committed
175
	const arch_register_class_t *cls                 = pbqp_alloc_env->cls;
176
	pbqp_matrix_t               *ife_matrix_template = pbqp_alloc_env->ife_matrix_template;
yb9976's avatar
yb9976 committed
177
	unsigned                    *restr_nodes         = pbqp_alloc_env->restr_nodes;
178

179
	if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
Thomas Bersch's avatar
Thomas Bersch committed
180

yb9976's avatar
yb9976 committed
181
		/* increase ife edge counter */
182
183
184
		pbqp_alloc_env->ife_edge_num[get_irn_idx(src_node)]++;
		pbqp_alloc_env->ife_edge_num[get_irn_idx(trg_node)]++;

185
#if DO_USEFUL_OPT || USE_BIPARTIT_MATCHING
Thomas Bersch's avatar
Thomas Bersch committed
186
		/* do useful optimization to speed up pbqp solving (we can do this because we know our matrix) */
187
		if (get_free_regs(restr_nodes, cls, src_node) == 1 && get_free_regs(restr_nodes, cls, trg_node) == 1) {
yb9976's avatar
yb9976 committed
188
189
190
			assert(vector_get_min_index(get_node(pbqp, get_irn_idx(src_node))->costs) !=
			       vector_get_min_index(get_node(pbqp, get_irn_idx(trg_node))->costs) &&
			       "Interfering nodes must not have the same register!");
Thomas Bersch's avatar
Thomas Bersch committed
191
192
			return;
		}
193
194
		if (get_free_regs(restr_nodes, cls, src_node) == 1 || get_free_regs(restr_nodes, cls, trg_node) == 1) {
			if (get_free_regs(restr_nodes, cls, src_node) == 1) {
Thomas Bersch's avatar
Thomas Bersch committed
195
196
197
198
199
200
201
202
203
				unsigned idx = vector_get_min_index(get_node(pbqp, get_irn_idx(src_node))->costs);
				vector_set(get_node(pbqp, get_irn_idx(trg_node))->costs, idx, INF_COSTS);
			}
			else {
				unsigned idx = vector_get_min_index(get_node(pbqp, get_irn_idx(trg_node))->costs);
				vector_set(get_node(pbqp, get_irn_idx(src_node))->costs, idx, INF_COSTS);
			}
			return;
		}
204
#endif
Thomas Bersch's avatar
Thomas Bersch committed
205
206
207
		/* insert interference edge */
		insert_edge(pbqp, src_node, trg_node, ife_matrix_template);
	}
208
209
}

yb9976's avatar
yb9976 committed
210
static void insert_afe_edge(be_pbqp_alloc_env_t *pbqp_alloc_env, ir_node *src_node, ir_node *trg_node, int pos)
Matthias Braun's avatar
Matthias Braun committed
211
{
212
	pbqp_t                      *pbqp        = pbqp_alloc_env->pbqp_inst;
yb9976's avatar
yb9976 committed
213
214
	const arch_register_class_t *cls         = pbqp_alloc_env->cls;
	unsigned                    *restr_nodes = pbqp_alloc_env->restr_nodes;
215
	pbqp_matrix_t               *afe_matrix  = pbqp_matrix_alloc(pbqp, arch_register_class_n_regs(cls), arch_register_class_n_regs(cls));
yb9976's avatar
yb9976 committed
216
	unsigned                     colors_n    = arch_register_class_n_regs(cls);
Thomas Bersch's avatar
Thomas Bersch committed
217

218
219
	if (get_edge(pbqp, get_irn_idx(src_node), get_irn_idx(trg_node)) == NULL) {
		if (use_exec_freq) {
Thomas Bersch's avatar
Thomas Bersch committed
220
			/* get exec_freq for copy_block */
yb9976's avatar
yb9976 committed
221
222
223
224
			ir_node       *root_bl   = get_nodes_block(src_node);
			ir_node       *copy_bl   = is_Phi(src_node) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
			ir_exec_freq  *exec_freq = be_get_irg_exec_freq(pbqp_alloc_env->irg);
			unsigned long  res       = get_block_execfreq_ulong(exec_freq, copy_bl);
Thomas Bersch's avatar
Thomas Bersch committed
225
226
227

			/* create afe-matrix */
			unsigned row, col;
228
229
230
			for (row = 0; row < colors_n; row++) {
				for (col = 0; col < colors_n; col++) {
					if (row != col)
Thomas Bersch's avatar
Thomas Bersch committed
231
232
233
234
235
236
237
						pbqp_matrix_set(afe_matrix, row, col, (num)res);
				}
			}
		}
		else {
			afe_matrix = pbqp_alloc_env->aff_matrix_template;
		}
238
#if DO_USEFUL_OPT || USE_BIPARTIT_MATCHING
Thomas Bersch's avatar
Thomas Bersch committed
239
		/* do useful optimization to speed up pbqp solving */
240
		if (get_free_regs(restr_nodes, cls, src_node) == 1 && get_free_regs(restr_nodes, cls, trg_node) == 1) {
Thomas Bersch's avatar
Thomas Bersch committed
241
242
			return;
		}
243
244
		if (get_free_regs(restr_nodes, cls, src_node) == 1 || get_free_regs(restr_nodes, cls, trg_node) == 1) {
			if (get_free_regs(restr_nodes, cls, src_node) == 1) {
Thomas Bersch's avatar
Thomas Bersch committed
245
246
247
248
249
250
251
252
253
				unsigned regIdx = vector_get_min_index(get_node(pbqp, get_irn_idx(src_node))->costs);
				vector_add_matrix_col(get_node(pbqp, get_irn_idx(trg_node))->costs, afe_matrix, regIdx);
			}
			else {
				unsigned regIdx = vector_get_min_index(get_node(pbqp, get_irn_idx(trg_node))->costs);
				vector_add_matrix_col(get_node(pbqp, get_irn_idx(src_node))->costs, afe_matrix, regIdx);
			}
			return;
		}
254
#endif
Thomas Bersch's avatar
Thomas Bersch committed
255
256
257
258
259
		/* insert interference edge */
		insert_edge(pbqp, src_node, trg_node, afe_matrix);
	}
}

Matthias Braun's avatar
Matthias Braun committed
260
261
static void create_affinity_edges(ir_node *irn, void *env)
{
262
	be_pbqp_alloc_env_t         *pbqp_alloc_env = (be_pbqp_alloc_env_t*)env;
yb9976's avatar
yb9976 committed
263
264
265
266
	const arch_register_class_t *cls            = pbqp_alloc_env->cls;
	const arch_register_req_t   *req            = arch_get_register_req_out(irn);
	unsigned                     pos;
	unsigned                     max;
267
268

	if (is_Reg_Phi(irn)) { /* Phis */
yb9976's avatar
yb9976 committed
269
		for (pos = 0, max = get_irn_arity(irn); pos < max; ++pos) {
270
271
272
273
274
275
			ir_node *arg = get_irn_n(irn, pos);

			if (!arch_irn_consider_in_reg_alloc(cls, arg))
				continue;

			/* no edges to itself */
276
			if (irn == arg) {
277
278
279
				continue;
			}

yb9976's avatar
yb9976 committed
280
			insert_afe_edge(pbqp_alloc_env, irn, arg, pos);
281
282
283
284
285
286
287
		}
	}
	else if (is_Perm_Proj(irn)) { /* Perms */
		ir_node *arg = get_Perm_src(irn);
		if (!arch_irn_consider_in_reg_alloc(cls, arg))
			return;

yb9976's avatar
yb9976 committed
288
		insert_afe_edge(pbqp_alloc_env, irn, arg, -1);
289
290
291
292
	}
	else { /* 2-address code */
		if (is_2addr_code(req)) {
			const unsigned other = req->other_same;
yb9976's avatar
yb9976 committed
293
			int            i;
294
295
296
297

			for (i = 0; 1U << i <= other; ++i) {
				if (other & (1U << i)) {
					ir_node *other = get_irn_n(skip_Proj(irn), i);
Thomas Bersch's avatar
Thomas Bersch committed
298
299
300
301
					if (!arch_irn_consider_in_reg_alloc(cls, other))
						continue;

					/* no edges to itself */
302
					if (irn == other) {
Thomas Bersch's avatar
Thomas Bersch committed
303
304
305
						continue;
					}

yb9976's avatar
yb9976 committed
306
					insert_afe_edge(pbqp_alloc_env, irn, other, i);
307
308
309
310
311
312
				}
			}
		}
	}
}

Matthias Braun's avatar
Matthias Braun committed
313
314
static void create_pbqp_coloring_instance(ir_node *block, void *data)
{
315
	be_pbqp_alloc_env_t         *pbqp_alloc_env     = (be_pbqp_alloc_env_t*)data;
316
317
	be_lv_t                     *lv                 = pbqp_alloc_env->lv;
	const arch_register_class_t *cls                = pbqp_alloc_env->cls;
yb9976's avatar
yb9976 committed
318
	plist_t                     *rpeo               = pbqp_alloc_env->rpeo;
319
	pbqp_t                      *pbqp_inst          = pbqp_alloc_env->pbqp_inst;
yb9976's avatar
yb9976 committed
320
321
	plist_t                     *temp_list          = plist_new();
	plist_element_t             *el;
322
323
	ir_node                     *irn;
	ir_nodeset_t                 live_nodes;
324
#if USE_BIPARTIT_MATCHING
yb9976's avatar
yb9976 committed
325
	int                         *assignment         = ALLOCAN(int, cls->n_regs);
326
#else
yb9976's avatar
yb9976 committed
327
	unsigned                    *restr_nodes        = pbqp_alloc_env->restr_nodes;
328
329
330
	pqueue_t                    *restr_nodes_queue  = new_pqueue();
	pqueue_t                    *queue              = new_pqueue();
	plist_t                     *sorted_list        = plist_new();
yb9976's avatar
yb9976 committed
331
	ir_node                     *last_element       = NULL;
332
#endif
333
334
335

	/* first, determine the pressure */
	/* (this is only for compatibility with copymin optimization, it's not needed for pbqp coloring) */
336
	create_borders(block, pbqp_alloc_env->env);
337
338
339
340
341
342
343

	/* calculate living nodes for the first step */
	ir_nodeset_init(&live_nodes);
	be_liveness_end_of_block(lv, cls, block, &live_nodes);

	/* create pbqp nodes, interference edges and reverse perfect elimination order */
	sched_foreach_reverse(block, irn) {
yb9976's avatar
yb9976 committed
344
345
		ir_node               *live;
		ir_nodeset_iterator_t  iter;
346

Thomas Bersch's avatar
Thomas Bersch committed
347
348
349
350
351
352
353
354
		if (get_irn_mode(irn) == mode_T) {
			const ir_edge_t *edge;
			foreach_out_edge(irn, edge) {
				ir_node *proj = get_edge_src_irn(edge);
				if (!arch_irn_consider_in_reg_alloc(cls, proj))
					continue;

				/* create pbqp source node if it dosn't exist */
355
				if (get_node(pbqp_inst, get_irn_idx(proj)) == NULL) {
Thomas Bersch's avatar
Thomas Bersch committed
356
					create_pbqp_node(pbqp_alloc_env, proj);
357
				}
Thomas Bersch's avatar
Thomas Bersch committed
358
359
360
361

				/* create nodes and interference edges */
				foreach_ir_nodeset(&live_nodes, live, iter) {
					/* create pbqp source node if it dosn't exist */
362
					if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
Thomas Bersch's avatar
Thomas Bersch committed
363
364
365
						create_pbqp_node(pbqp_alloc_env, live);
					}

366
					/* no edges to itself */
367
					if (proj == live) {
368
						continue;
Thomas Bersch's avatar
Thomas Bersch committed
369
					}
370

Thomas Bersch's avatar
Thomas Bersch committed
371
					insert_ife_edge(pbqp_alloc_env, proj, live);
372
				}
Thomas Bersch's avatar
Thomas Bersch committed
373
374
375
376
377
			}
		}
		else {
			if (arch_irn_consider_in_reg_alloc(cls, irn)) {
				/* create pbqp source node if it dosn't exist */
378
				if (get_node(pbqp_inst, get_irn_idx(irn)) == NULL) {
Thomas Bersch's avatar
Thomas Bersch committed
379
380
381
382
383
384
					create_pbqp_node(pbqp_alloc_env, irn);
				}

				/* create nodes and interference edges */
				foreach_ir_nodeset(&live_nodes, live, iter) {
					/* create pbqp source node if it dosn't exist */
385
					if (get_node(pbqp_inst, get_irn_idx(live)) == NULL) {
Thomas Bersch's avatar
Thomas Bersch committed
386
						create_pbqp_node(pbqp_alloc_env, live);
387
					}
Thomas Bersch's avatar
Thomas Bersch committed
388
389

					/* no edges to itself */
390
					if (irn == live) {
Thomas Bersch's avatar
Thomas Bersch committed
391
						continue;
392
393
					}

Thomas Bersch's avatar
Thomas Bersch committed
394
395
396
					/* insert interference edge */
					insert_ife_edge(pbqp_alloc_env, irn, live);
				}
397
398
399
			}
		}

Thomas Bersch's avatar
Thomas Bersch committed
400
401
402
403
404
		/* get living nodes for next step */
		if (!is_Phi(irn)) {
			be_liveness_transfer(cls, irn, &live_nodes);
		}

405
406
#if USE_BIPARTIT_MATCHING
		if (get_irn_mode(irn) == mode_T) {
yb9976's avatar
yb9976 committed
407
408
409
410
			unsigned     clique_size         = 0;
			unsigned     n_alloc             = 0;
			pbqp_node   *clique[cls->n_regs];
			bipartite_t *bp                  = bipartite_new(cls->n_regs, cls->n_regs);
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426

			/* add all proj after a perm to clique */
			const ir_edge_t *edge;
			foreach_out_edge(irn, edge) {
				ir_node *proj = get_edge_src_irn(edge);

				/* ignore node if it is not necessary for register allocation */
				if (!arch_irn_consider_in_reg_alloc(cls, proj))
					continue;

				/* insert pbqp node into temp rpeo list of this block */
				plist_insert_front(temp_list, get_node(pbqp_inst, get_irn_idx(proj)));

				if(is_Perm_Proj(proj)) {
					/* add proj to clique */
					pbqp_node *clique_member = get_node(pbqp_inst,proj->node_idx);
yb9976's avatar
yb9976 committed
427
428
429
					vector    *costs         = clique_member->costs;
					unsigned   idx           = 0;

430
					clique[clique_size] = clique_member;
yb9976's avatar
yb9976 committed
431

432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
					for(idx = 0; idx < costs->len; idx++) {
						if(costs->entries[idx].data != INF_COSTS) {
							bipartite_add(bp, clique_size, idx);
						}
					}

					/* increase node counter */
					clique_size++;
					n_alloc++;
				}
			}

			if(clique_size > 0) {
				plist_element_t *listElement;
				foreach_plist(temp_list, listElement) {
yb9976's avatar
yb9976 committed
447
448
449
					pbqp_node *clique_candidate  = listElement->data;
					unsigned   idx               = 0;
					bool       isMember          = true;
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483

					/* clique size not bigger then register class size */
					if(clique_size >= cls->n_regs) break;

					for(idx = 0; idx < clique_size; idx++) {
						pbqp_node *member = clique[idx];

						if(member == clique_candidate) {
							isMember = false;
							break;
						}

						if(get_edge(pbqp_inst, member->index, clique_candidate->index) == NULL && get_edge(pbqp_inst, clique_candidate->index, member->index) == NULL) {
							isMember = false;
							break;
						}
					}

					/* goto next list element if current node is not a member of the clique */
					if(!isMember) { continue; }

					/* add candidate to clique */
					clique[clique_size] = clique_candidate;

					vector *costs = clique_candidate->costs;
					for(idx = 0; idx < costs->len; idx++) {
						if(costs->entries[idx].data != INF_COSTS) {
							bipartite_add(bp, clique_size, idx);
						}
					}

					/* increase node counter */
					clique_size++;
				}
yb9976's avatar
yb9976 committed
484
			}
485
486
487
488
489
490
491
492

			/* solve bipartite matching */
			bipartite_matching(bp, assignment);

			/* assign colors */
			unsigned nodeIdx = 0;
			for(nodeIdx = 0; nodeIdx < clique_size; nodeIdx++) {
				vector *costs = clique[nodeIdx]->costs;
yb9976's avatar
yb9976 committed
493
				int     idx;
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
				for(idx = 0; idx < (int)costs->len; idx++) {
					if(assignment[nodeIdx] != idx) {
						costs->entries[idx].data = INF_COSTS;
					}
				}
				assert(assignment[nodeIdx] >= 0 && "there must have been a register assigned (node not register pressure faithful?)");
			}

			/* free memory */
			bipartite_free(bp);
		}
		else {
			if (arch_irn_consider_in_reg_alloc(cls, irn)) {
				plist_insert_front(temp_list, get_node(pbqp_inst, get_irn_idx(irn)));
			}
		}
#else
511
512
		/* order nodes for perfect elimination order */
		if (get_irn_mode(irn) == mode_T) {
yb9976's avatar
yb9976 committed
513
			bool             allHaveIFEdges = true;
514
			const ir_edge_t *edge;
yb9976's avatar
yb9976 committed
515

516
517
518
519
520
			foreach_out_edge(irn, edge) {
				ir_node *proj = get_edge_src_irn(edge);
				if (!arch_irn_consider_in_reg_alloc(cls, proj))
					continue;

521
522
				/* insert proj node into priority queue (descending by the number of interference edges) */
				if (get_free_regs(restr_nodes, cls, proj) <= 4) {
523
					pqueue_put(restr_nodes_queue, proj, pbqp_alloc_env->ife_edge_num[get_irn_idx(proj)]);
524
525
				}
				else {
526
527
528
529
530
531
532
533
534
535
					pqueue_put(queue, proj, pbqp_alloc_env->ife_edge_num[get_irn_idx(proj)]);
				}

				/* skip last step if there is no last_element */
				if(last_element == NULL)
					continue;

				/* check if proj has an if edge to last_element (at this time pbqp contains only if edges) */
				if(get_edge(pbqp_inst, proj->node_idx, last_element->node_idx) == NULL && get_edge(pbqp_inst, last_element->node_idx, proj->node_idx) == NULL) {
					allHaveIFEdges = false; /* there is no if edge between proj and last_element */
536
537
538
				}
			}

539
540
541
			if(last_element != NULL && allHaveIFEdges) {
				if (get_free_regs(restr_nodes, cls, last_element) <= 4) {
					pqueue_put(restr_nodes_queue, last_element, pbqp_alloc_env->ife_edge_num[get_irn_idx(last_element)]);
542
543
				}
				else {
544
					pqueue_put(queue, last_element, pbqp_alloc_env->ife_edge_num[get_irn_idx(last_element)]);
545
546
547
548
549
				}
				plist_erase(temp_list, plist_find_value(temp_list, get_node(pbqp_inst, last_element->node_idx)));
				last_element = NULL;
			}

550
			/* first insert all restricted proj nodes */
551
			while (!pqueue_empty(restr_nodes_queue)) {
552
553
				ir_node *node = (ir_node*)pqueue_pop_front(restr_nodes_queue);
				plist_insert_front(sorted_list, get_node(pbqp_inst, get_irn_idx(node)));
554
555
556
			}

			/* insert proj nodes descending by their number of interference edges */
557
			while (!pqueue_empty(queue)) {
558
559
				ir_node *node = (ir_node*)pqueue_pop_front(queue);
				plist_insert_front(sorted_list, get_node(pbqp_inst, get_irn_idx(node)));
560
561
562
563
564
			}

			/* invert sorted list */
			foreach_plist(sorted_list, el) {
				plist_insert_front(temp_list, el->data);
565
			}
566
567
568

			plist_clear(sorted_list);

569
570
571
		}
		else {
			if (arch_irn_consider_in_reg_alloc(cls, irn)) {
572
				// remember last colorable node
573
				last_element = irn;
574
575
				plist_insert_front(temp_list, get_node(pbqp_inst, get_irn_idx(irn)));
			}
576
577
578
579
			else {
				// node not colorable, so ignore it
				last_element = NULL;
			}
580
		}
581
#endif
582
583
	}

584
	/* add the temp rpeo list of this block to the global reverse perfect elimination order list*/
585
586
587
588
589
590
591
	foreach_plist(temp_list, el) {
		plist_insert_back(rpeo, el->data);
	}

	/* free reserved memory */
	ir_nodeset_destroy(&live_nodes);
	plist_free(temp_list);
592
593
#if USE_BIPARTIT_MATCHING
#else
594
	plist_free(sorted_list);
595
596
	del_pqueue(queue);
	del_pqueue(restr_nodes_queue);
597
#endif
598
599
}

Matthias Braun's avatar
Matthias Braun committed
600
601
static void insert_perms(ir_node *block, void *data)
{
602
603
	be_chordal_env_t *env    = (be_chordal_env_t*)data;
	ir_node          *irn;
604
605
606
607
608
609

	/*
	 * If the block is the start block search the barrier and
	 * start handling constraints from there.
	 */
	for (irn = sched_first(block); !sched_is_end(irn);) {
yb9976's avatar
yb9976 committed
610
611
		be_insn_t *insn = chordal_scan_insn(env, irn);
		irn             = insn->next_insn;
612
613
614
615
616
617
618
619

		if (!insn->has_constraints)
			continue;

		pre_process_constraints(env, &insn);
	}
}

620
static void be_pbqp_coloring(be_chordal_env_t *env)
Matthias Braun's avatar
Matthias Braun committed
621
{
yb9976's avatar
yb9976 committed
622
623
624
625
626
627
628
629
	ir_graph                    *irg            = env->irg;
	const arch_register_class_t *cls            = env->cls;
	be_lv_t                     *lv             = NULL;
	plist_element_t             *element        = NULL;
	unsigned                     colors_n       = arch_register_class_n_regs(cls);
	be_pbqp_alloc_env_t          pbqp_alloc_env;
	unsigned                     col;
	unsigned                     row;
630

Thomas Bersch's avatar
Thomas Bersch committed
631
#if TIMER
Matthias Braun's avatar
Matthias Braun committed
632
633
634
	ir_timer_t *t_ra_pbqp_alloc_create     = ir_timer_new();
	ir_timer_t *t_ra_pbqp_alloc_solve      = ir_timer_new();
	ir_timer_t *t_ra_pbqp_alloc_create_aff = ir_timer_new();
Thomas Bersch's avatar
Thomas Bersch committed
635
636
637

	printf("#### ----- === Allocating registers of %s (%s) ===\n", cls->name, get_entity_name(get_irg_entity(irg)));
#endif
638
	lv = be_assure_liveness(irg);
639
640
641
642
643
644
645
646
647
648
649
	be_liveness_assure_sets(lv);
	be_liveness_assure_chk(lv);

	/* insert perms */
	assure_doms(irg);
	dom_tree_walk_irg(irg, insert_perms, NULL, env);

	/* dump graph after inserting perms */
	if (env->opts->dump_flags & BE_CH_DUMP_CONSTR) {
		char buf[256];
		snprintf(buf, sizeof(buf), "-%s-constr", cls->name);
yb9976's avatar
yb9976 committed
650
		dump_ir_graph(irg, buf);
651
652
	}

Thomas Bersch's avatar
Thomas Bersch committed
653

654
	/* initialize pbqp allocation data structure */
655
656
657
658
659
660
661
662
663
664
	pbqp_alloc_env.pbqp_inst        = alloc_pbqp(get_irg_last_idx(irg));  /* initialize pbqp instance */
	pbqp_alloc_env.cls              = cls;
	pbqp_alloc_env.irg              = irg;
	pbqp_alloc_env.lv               = lv;
	pbqp_alloc_env.allocatable_regs = bitset_malloc(colors_n);
	pbqp_alloc_env.rpeo             = plist_new();
	pbqp_alloc_env.restr_nodes      = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
	pbqp_alloc_env.ife_edge_num     = XMALLOCNZ(unsigned, get_irg_last_idx(irg));
	pbqp_alloc_env.env              = env;
	be_put_allocatable_regs(irg, cls, pbqp_alloc_env.allocatable_regs);
665

Thomas Bersch's avatar
Thomas Bersch committed
666
667

	/* create costs matrix template for interference edges */
668
	pbqp_matrix_t *ife_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
669
	/* set costs */
yb9976's avatar
yb9976 committed
670
	for (row = 0, col = 0; row < colors_n; row++, col++)
671
672
		pbqp_matrix_set(ife_matrix, row, col, INF_COSTS);

Thomas Bersch's avatar
Thomas Bersch committed
673
	pbqp_alloc_env.ife_matrix_template = ife_matrix;
674

Thomas Bersch's avatar
Thomas Bersch committed
675

676
	if (!use_exec_freq) {
Thomas Bersch's avatar
Thomas Bersch committed
677
		/* create costs matrix template for affinity edges */
678
		pbqp_matrix_t *afe_matrix = pbqp_matrix_alloc(pbqp_alloc_env.pbqp_inst, colors_n, colors_n);
Thomas Bersch's avatar
Thomas Bersch committed
679
		/* set costs */
680
681
682
		for (row = 0; row < colors_n; row++) {
			for (col = 0; col < colors_n; col++) {
				if (row != col)
Thomas Bersch's avatar
Thomas Bersch committed
683
684
					pbqp_matrix_set(afe_matrix, row, col, 2);
			}
685
		}
Thomas Bersch's avatar
Thomas Bersch committed
686
		pbqp_alloc_env.aff_matrix_template = afe_matrix;
687
688
689
690
	}


	/* create pbqp instance */
Thomas Bersch's avatar
Thomas Bersch committed
691
692
693
#if TIMER
	ir_timer_reset_and_start(t_ra_pbqp_alloc_create);
#endif
694
	assure_doms(irg);
Thomas Bersch's avatar
Thomas Bersch committed
695
696
697
698
699
	dom_tree_walk_irg(irg, create_pbqp_coloring_instance , NULL, &pbqp_alloc_env);
#if TIMER
	ir_timer_stop(t_ra_pbqp_alloc_create);
#endif

700
701

	/* set up affinity edges */
Thomas Bersch's avatar
Thomas Bersch committed
702
703
704
#if TIMER
	ir_timer_reset_and_start(t_ra_pbqp_alloc_create_aff);
#endif
705
	foreach_plist(pbqp_alloc_env.rpeo, element) {
706
707
		pbqp_node_t *node = (pbqp_node_t*)element->data;
		ir_node     *irn  = get_idx_irn(irg, node->index);
708

Thomas Bersch's avatar
Thomas Bersch committed
709
710
711
712
713
714
		create_affinity_edges(irn, &pbqp_alloc_env);
	}
#if TIMER
	ir_timer_stop(t_ra_pbqp_alloc_create_aff);
#endif

715
716
717
718
719
720
721

#if KAPS_DUMP
	// dump graph before solving pbqp
	FILE *file_before = my_open(env, "", "-pbqp_coloring.html");
	set_dumpfile(pbqp_alloc_env.pbqp_inst, file_before);
#endif

722
723
724
725
	/* print out reverse perfect eleminiation order */
#if PRINT_RPEO
	plist_element_t *elements;
	foreach_plist(pbqp_alloc_env.rpeo, elements) {
726
		pbqp_node *node = elements->data;
727
728
729
730
731
		printf(" %d(%lu);", node->index, get_idx_irn(irg, node->index)->node_nr);
	}
	printf("\n");
#endif

732
	/* solve pbqp instance */
Thomas Bersch's avatar
Thomas Bersch committed
733
734
735
#if TIMER
	ir_timer_reset_and_start(t_ra_pbqp_alloc_solve);
#endif
736
737
738
739
740
741
	if(use_late_decision) {
		solve_pbqp_heuristical_co_ld(pbqp_alloc_env.pbqp_inst,pbqp_alloc_env.rpeo);
	}
	else {
		solve_pbqp_heuristical_co(pbqp_alloc_env.pbqp_inst,pbqp_alloc_env.rpeo);
	}
Thomas Bersch's avatar
Thomas Bersch committed
742
743
744
#if TIMER
	ir_timer_stop(t_ra_pbqp_alloc_solve);
#endif
745
746


747
	num solution = get_solution(pbqp_alloc_env.pbqp_inst);
yb9976's avatar
yb9976 committed
748
749
	if (solution == INF_COSTS)
		panic("No PBQP solution found");
750

Thomas Bersch's avatar
Thomas Bersch committed
751
752

	/* assign colors */
753
	foreach_plist(pbqp_alloc_env.rpeo, element) {
754
		pbqp_node_t           *node  = (pbqp_node_t*)element->data;
yb9976's avatar
yb9976 committed
755
756
757
		ir_node               *irn   = get_idx_irn(irg, node->index);
		num                    color = get_node_solution(pbqp_alloc_env.pbqp_inst, node->index);
		const arch_register_t *reg   = arch_register_for_index(cls, color);
758
759
760
761

		arch_set_irn_register(irn, reg);
	}

Thomas Bersch's avatar
Thomas Bersch committed
762
763

#if TIMER
yb9976's avatar
yb9976 committed
764
	printf("PBQP alloc create:     %10.3lf msec\n",
Matthias Braun's avatar
Matthias Braun committed
765
	       (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create) / 1000.0);
yb9976's avatar
yb9976 committed
766
	printf("PBQP alloc solve:      %10.3lf msec\n",
Matthias Braun's avatar
Matthias Braun committed
767
	       (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_solve) / 1000.0);
yb9976's avatar
yb9976 committed
768
	printf("PBQP alloc create aff: %10.3lf msec\n",
Matthias Braun's avatar
Matthias Braun committed
769
	       (double)ir_timer_elapsed_usec(t_ra_pbqp_alloc_create_aff) / 1000.0);
Thomas Bersch's avatar
Thomas Bersch committed
770
#endif
771
772
773
774
775
776


	/* free reserved memory */
#if KAPS_DUMP
	fclose(file_before);
#endif
777
	bitset_free(pbqp_alloc_env.allocatable_regs);
778
779
780
	free_pbqp(pbqp_alloc_env.pbqp_inst);
	plist_free(pbqp_alloc_env.rpeo);
	xfree(pbqp_alloc_env.restr_nodes);
781
	xfree(pbqp_alloc_env.ife_edge_num);
782
783
784
785
786
787
}


/**
 * Initializes this module.
 */
788
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_pbqp_coloring);
Matthias Braun's avatar
Matthias Braun committed
789
790
void be_init_pbqp_coloring(void)
{
yb9976's avatar
yb9976 committed
791
792
793
	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");
Thomas Bersch's avatar
Thomas Bersch committed
794
	lc_opt_entry_t *coloring_grp = lc_opt_get_grp(chordal_grp, "coloring");
yb9976's avatar
yb9976 committed
795
	lc_opt_entry_t *pbqp_grp     = lc_opt_get_grp(coloring_grp, "pbqp");
796
797
798
799
800

	static be_ra_chordal_coloring_t coloring = {
		be_pbqp_coloring
	};

Thomas Bersch's avatar
Thomas Bersch committed
801
	lc_opt_add_table(pbqp_grp, options);
802
803
804
	be_register_chordal_coloring("pbqp", &coloring);
}

805
#endif