summaryrefslogtreecommitdiffhomepage
path: root/ir/be/bechordal.c
blob: 29630889d530c015c66f29dfa2e8d12a10f43c50 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief       Chordal register allocation.
 * @author      Sebastian Hack
 * @date        08.12.2004
 */
#include "bechordal_t.h"

#include "bechordal_common.h"
#include "beinsn_t.h"
#include "beirg.h"
#include "belive.h"
#include "bemodule.h"
#include "besched.h"
#include "bipartite.h"
#include "debug.h"
#include "hungarian.h"
#include "irdump.h"
#include "iredges_t.h"
#include "util.h"

#define USE_HUNGARIAN 0

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

static int get_next_free_reg(bitset_t *const available)
{
	return bitset_next_set(available, 0);
}

static unsigned const *get_decisive_partner_regs(be_operand_t const *const o1, size_t const n_regs)
{
	be_operand_t const *const o2 = o1->partner;
	if (!o2 || rbitset_contains(o1->regs, o2->regs, n_regs)) {
		return o1->regs;
	} else if (rbitset_contains(o2->regs, o1->regs, n_regs)) {
		return o2->regs;
	} else {
		return NULL;
	}
}

typedef struct pair_entry {
	be_operand_t *operand;
	int           pos;
	bool          is_def;
} pair_entry_t;

static unsigned n_regs;

static int compare_entries(const void *a, const void *b)
{
	pair_entry_t *a_entry = (pair_entry_t *)a;
	pair_entry_t *b_entry = (pair_entry_t *)b;

	be_operand_t   *a_op    = a_entry->operand;
	be_operand_t   *b_op    = b_entry->operand;
	const unsigned *a_regs  = a_op->regs;
	const unsigned *b_regs  = b_op->regs;
	int             a_count = rbitset_popcount(a_regs, n_regs);
	int             b_count = rbitset_popcount(b_regs, n_regs);
	if (a_count != b_count) {
		return a_count - b_count;
	}

	for (size_t i = 0, n = BITSET_SIZE_ELEMS(n_regs); i < n; ++i) {
		unsigned a_regs_i = a_regs[i];
		unsigned b_regs_i = b_regs[i];
		if (a_regs_i != b_regs_i) {
			return a_regs_i < b_regs_i ? -1 : 1;
		}
	}

	bool a_is_def = a_entry->is_def;
	bool b_is_def = b_entry->is_def;
	if (a_is_def != b_is_def) {
		return a_is_def - b_is_def;
	}

	return a_entry->pos - b_entry->pos;
}

static bool list_has_irn_else_add(ir_node **const list, size_t const n, ir_node *const irn)
{
	for (ir_node *const *i = list; i != list + n; ++i) {
		if (*i == irn)
			return true;
	}
	list[n] = irn;
	return false;
}

static void pair_up_operands(be_chordal_env_t *const env, be_insn_t *const insn)
{
	int           n_ops     = insn->n_ops;
	int           use_start = insn->use_start;
	pair_entry_t *entries   = OALLOCNZ(&env->obst, pair_entry_t, n_ops);

	/* Put definitions and uses into a single list. */
	for (int i = 0; i < n_ops; ++i) {
		pair_entry_t *entry = &entries[i];
		be_operand_t *op    = &insn->ops[i];
		entry->operand = op;
		entry->is_def  = i < use_start;
		if (entry->is_def) {
			ir_node *carrier = op->carrier;
			if (is_Proj(carrier)) {
				entry->pos = get_Proj_num(carrier);
			} else {
				assert(i == 0);
				entry->pos = 0;
			}
		} else {
			entry->pos = i - use_start;
		}
	}

	/**
	 * Only use most restricted node for each carrier.
	 */
	n_regs = env->cls->n_regs;
	QSORT(entries + use_start, n_ops - use_start, compare_entries);

	size_t          n_uses = 0;
	ir_node **const uses   = ALLOCAN(ir_node*, n_regs);
	for (int i = use_start; i < n_ops; ++i) {
		be_operand_t *op = entries[i].operand;
		if (list_has_irn_else_add(uses, n_uses, op->carrier)) {
			op->carrier = NULL;
		} else {
			++n_uses;
		}
	}

	/**
	 * Sort the list by register constraints (more restricted operands first).
	 * Use a stable compare function that only depends on the graph structure.
	 */
	QSORT(entries, n_ops, compare_entries);

	/* Greedily pair definitions/uses. */
	for (int i = 0; i < n_ops; ++i) {
		pair_entry_t *op_entry  = &entries[i];
		be_operand_t *op        = op_entry->operand;
		bool          op_is_def = op_entry->is_def;
		if (op->partner || !op->carrier ||
		    (!op_is_def && be_value_live_after(op->carrier, insn->irn))) {
			continue;
		}

		for (int j = i + 1; j < n_ops; ++j) {
			pair_entry_t *partner_entry  = &entries[j];
			be_operand_t *partner        = partner_entry->operand;
			bool          partner_is_def = partner_entry->is_def;
			if (!partner->partner &&
			    partner->carrier &&
			    op_is_def != partner_is_def &&
			    rbitsets_have_common(op->regs, partner->regs, n_regs) &&
			    (partner_is_def || !be_value_live_after(partner->carrier, insn->irn))) {
				op->partner      = partner;
				partner->partner = op;
				break;
			}
		}
	}
}

static void handle_constraints(be_chordal_env_t *const env, ir_node *const irn)
{
	void *const base = obstack_base(&env->obst);
	be_insn_t  *insn = be_scan_insn(env, irn);

	/* Perms inserted before the constraint handling phase are considered to be
	 * correctly precolored. These Perms arise during the ABI handling phase. */
	if (!insn || is_Phi(irn))
		goto end;

	/* Prepare the constraint handling of this node.
	 * Perms are constructed and Copies are created for constrained values
	 * interfering with the instruction. */
	ir_node *const perm = pre_process_constraints(env, &insn);

	/* find suitable in operands to the out operands of the node. */
	pair_up_operands(env, insn);

	/* Look at the in/out operands and add each operand (and its possible partner)
	 * to a bipartite graph (left: nodes with partners, right: admissible colors). */
	int                        n_alloc     = 0;
	int                  const n_regs      = env->cls->n_regs;
	ir_node            **const alloc_nodes = ALLOCAN(ir_node*, n_regs);
	pmap                *const partners    = pmap_create();
#if USE_HUNGARIAN
	hungarian_problem_t *const bp          = hungarian_new(n_regs, n_regs, HUNGARIAN_MATCH_PERFECT);
#else
	bipartite_t         *const bp          = bipartite_new(n_regs, n_regs);
#endif
	for (int i = 0, n_ops = insn->n_ops; i < n_ops; ++i) {
		/* If the operand has no partner or the partner has not been marked
		 * for allocation, determine the admissible registers and mark it
		 * for allocation by associating the node and its partner with the
		 * set of admissible registers via a bipartite graph. */
		be_operand_t *const op = &insn->ops[i];
		if (!op->carrier)
			continue;
		if (op->partner && pmap_contains(partners, op->partner->carrier))
			continue;

		ir_node *const partner = op->partner ? op->partner->carrier : NULL;
		pmap_insert(partners, op->carrier, partner);
		if (partner != NULL)
			pmap_insert(partners, partner, op->carrier);

		alloc_nodes[n_alloc] = op->carrier;

		DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, partner));

		unsigned const *const bs = get_decisive_partner_regs(op, n_regs);
		if (bs) {
#ifdef DEBUG_libfirm
			DBG((dbg, LEVEL_2, "\tallowed registers for %+F:", op->carrier, bs[0]));
			rbitset_foreach(bs, n_regs, col) {
				arch_register_t const *const reg = arch_register_for_index(env->cls, col);
				DB((dbg, LEVEL_2, " %s", reg->name));
			}
			DB((dbg, LEVEL_2, "\n"));
#endif

			rbitset_foreach(bs, n_regs, col) {
#if USE_HUNGARIAN
				hungarian_add(bp, n_alloc, col, 1);
#else
				bipartite_add(bp, n_alloc, col);
#endif
			}
		} else {
			DBG((dbg, LEVEL_2, "\tallowed registers for %+F: none\n", op->carrier));
		}

		n_alloc++;
	}

	/* Put all nodes which live through the constrained instruction also to the
	 * allocation bipartite graph. They are considered unconstrained. */
	if (perm != NULL) {
		foreach_out_edge(perm, edge) {
			ir_node *const proj = get_edge_src_irn(edge);
			assert(is_Proj(proj));

			/* Don't insert a node twice. */
			if (pmap_contains(partners, proj))
				continue;

			assert(n_alloc < n_regs);

			alloc_nodes[n_alloc] = proj;
			pmap_insert(partners, proj, NULL);

			bitset_foreach(env->allocatable_regs, col) {
#if USE_HUNGARIAN
				hungarian_add(bp, n_alloc, col, 1);
#else
				bipartite_add(bp, n_alloc, col);
#endif
			}

			n_alloc++;
		}
	}

	/* Compute a valid register allocation. */
	int *const assignment = ALLOCAN(int, n_regs);
#if USE_HUNGARIAN
	hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
	int const match_res = hungarian_solve(bp, assignment, NULL, 1);
	assert(match_res == 0 && "matching failed");
#else
	bipartite_matching(bp, assignment);
#endif

	/* Assign colors obtained from the matching. */
	for (int i = 0; i < n_alloc; ++i) {
		assert(assignment[i] >= 0 && "there must have been a register assigned (node not register pressure faithful?)");
		arch_register_t const *const reg = arch_register_for_index(env->cls, assignment[i]);

		ir_node *const irn = alloc_nodes[i];
		arch_set_irn_register(irn, reg);
		DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));

		ir_node *const partner = pmap_get(ir_node, partners, irn);
		if (partner != NULL) {
			arch_set_irn_register(partner, reg);
			DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", partner, reg->name));
		}
	}

#if USE_HUNGARIAN
	hungarian_free(bp);
#else
	bipartite_free(bp);
#endif
	pmap_destroy(partners);

end:
	obstack_free(&env->obst, base);
}

/**
 * Handle constraint nodes in each basic block.
 * handle_constraints() inserts Perm nodes which perm
 * over all values live at the constrained node right in front
 * of the constrained node. These Perms signal a constrained node.
 * For further comments, refer to handle_constraints().
 */
static void constraints(ir_node *const bl, void *const data)
{
	be_chordal_env_t *const env = (be_chordal_env_t*)data;
	sched_foreach_safe(bl, irn) {
		handle_constraints(env, irn);
	}
}

static void assign(ir_node *const block, void *const env_ptr)
{
	be_chordal_env_t *const env  = (be_chordal_env_t*)env_ptr;
	struct list_head *const head = get_block_border_head(env, block);

	DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
	DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
	foreach_border_head(head, b) {
		DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
		     b->irn, get_irn_idx(b->irn)));
	}

	bitset_t *const available = bitset_alloca(env->allocatable_regs->size);
	bitset_copy(available, env->allocatable_regs);

	/* Mind that the sequence of defs from back to front defines a perfect
	 * elimination order. So, coloring the definitions from first to last
	 * will work. */
	foreach_border_head(head, b) {
		ir_node *const irn = b->irn;

		/* Assign a color, if it is a local def. Global defs already have a
		 * color. */
		if (!b->is_def) {
			/* Make the color available upon a use. */
			arch_register_t const *const reg = arch_get_irn_register(irn);
			assert(reg && "Register must have been assigned");
			bitset_set(available, reg->index);
		} else {
			arch_register_t const *const reg = arch_get_irn_register(irn);
			/* All live-ins must have a register assigned. (The dominators were
			 * allocated before.) */
			assert(b->is_real || reg);
			unsigned col;
			if (reg) {
				DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
				col = reg->index;
				assert(bitset_is_set(available, col) && "pre-colored register must be free");
			} else {
				assert(!arch_irn_is_ignore(irn));
				col = get_next_free_reg(available);
				arch_set_irn_register_idx(irn, col);
			}
			bitset_clear(available, col);

			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", arch_get_irn_register(irn)->name, col, irn));
		}
	}
}

static void be_ra_chordal_color(be_chordal_env_t *const chordal_env)
{
	ir_graph *const irg = chordal_env->irg;
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
	be_assure_live_sets(irg);

	/* Handle register targeting constraints */
	be_timer_push(T_CONSTR);
	dom_tree_walk_irg(irg, constraints, NULL, chordal_env);
	be_timer_pop(T_CONSTR);

	be_chordal_dump(BE_CH_DUMP_CONSTR, irg, chordal_env->cls, "constr");

	/* First, determine the pressure */
	dom_tree_walk_irg(irg, create_borders, NULL, chordal_env);

	/* Assign the colors */
	dom_tree_walk_irg(irg, assign, NULL, chordal_env);
}

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal)
void be_init_chordal(void)
{
	static be_ra_chordal_coloring_t coloring = {
		be_ra_chordal_color
	};
	FIRM_DBG_REGISTER(dbg, "firm.be.chordal");

	be_register_chordal_coloring("default", &coloring);
}