bechordal.c 11.5 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Sebastian Hack's avatar
Sebastian Hack committed
6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       Chordal register allocation.
 * @author      Sebastian Hack
 * @date        08.12.2004
Sebastian Hack's avatar
Sebastian Hack committed
11
 */
Christoph Mallon's avatar
Christoph Mallon committed
12
13
#include "bechordal_common.h"
#include "bechordal_t.h"
14
#include "beinsn_t.h"
Matthias Braun's avatar
Matthias Braun committed
15
#include "belive.h"
Matthias Braun's avatar
Matthias Braun committed
16
#include "besched.h"
Christoph Mallon's avatar
Christoph Mallon committed
17
#include "beirg.h"
Christian Würdig's avatar
Christian Würdig committed
18
#include "bemodule.h"
Christoph Mallon's avatar
Christoph Mallon committed
19
20
#include "debug.h"
#include "irdump.h"
21
#include "iredges_t.h"
yb9976's avatar
yb9976 committed
22
#include "util.h"
Christoph Mallon's avatar
Christoph Mallon committed
23
24
25
26
27
28
29
30

#define USE_HUNGARIAN 0

#if USE_HUNGARIAN
#include "hungarian.h"
#else
#include "bipartite.h"
#endif
31

32
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
Daniel Grund's avatar
Daniel Grund committed
33

34
static int get_next_free_reg(bitset_t *const available)
Sebastian Hack's avatar
Sebastian Hack committed
35
{
36
	return bitset_next_set(available, 0);
Sebastian Hack's avatar
Sebastian Hack committed
37
38
}

39
static unsigned const *get_decisive_partner_regs(be_operand_t const *const o1, size_t const n_regs)
40
{
41
	be_operand_t const *const o2 = o1->partner;
42
	if (!o2 || rbitset_contains(o1->regs, o2->regs, n_regs)) {
43
		return o1->regs;
44
	} else if (rbitset_contains(o2->regs, o1->regs, n_regs)) {
45
		return o2->regs;
Christoph Mallon's avatar
Christoph Mallon committed
46
	} else {
47
		return NULL;
Christoph Mallon's avatar
Christoph Mallon committed
48
	}
49
}
Sebastian Hack's avatar
Sebastian Hack committed
50

yb9976's avatar
yb9976 committed
51
52
53
54
55
56
57
58
59
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)
Sebastian Hack's avatar
Sebastian Hack committed
60
{
yb9976's avatar
yb9976 committed
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
	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;
Sebastian Hack's avatar
Sebastian Hack committed
79
		}
yb9976's avatar
yb9976 committed
80
	}
Sebastian Hack's avatar
Sebastian Hack committed
81

yb9976's avatar
yb9976 committed
82
83
84
85
86
87
88
89
90
	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;
}

91
92
93
94
95
96
97
98
99
100
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;
}

yb9976's avatar
yb9976 committed
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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;
Matthias Braun's avatar
Matthias Braun committed
120
			}
yb9976's avatar
yb9976 committed
121
122
123
124
		} else {
			entry->pos = i - use_start;
		}
	}
Matthias Braun's avatar
Matthias Braun committed
125

yb9976's avatar
yb9976 committed
126
127
128
129
130
131
132
133
	/**
	 * Sort the list by register constraints (more restricted operands first).
	 * Use a stable compare function that only depends on the graph structure.
	 */
	n_regs = env->cls->n_regs;
	QSORT(entries, n_ops, compare_entries);

	/* Greedily pair definitions/uses. */
134
135
	size_t          n_paired     = 0;
	ir_node **const paired_nodes = ALLOCAN(ir_node*, n_regs);
yb9976's avatar
yb9976 committed
136
	for (int i = 0; i < n_ops; ++i) {
137
138
139
140
141
142
143
144
145
146
147
		pair_entry_t *op_entry = &entries[i];
		be_operand_t *op       = op_entry->operand;

		if (list_has_irn_else_add(paired_nodes, n_paired, op->carrier)) {
			if (!op->partner)
				op->carrier = NULL;
			continue;
		}
		++n_paired;

		bool op_is_def = op_entry->is_def;
yb9976's avatar
yb9976 committed
148
149
150
151
152
153
154
155
156
157
158
159
		if (op->partner ||
		    (!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 &&
			    op_is_def != partner_is_def &&
			    rbitsets_have_common(op->regs, partner->regs, n_regs) &&
160
161
162
			    (partner_is_def || !be_value_live_after(partner->carrier, insn->irn)) &&
			    !list_has_irn_else_add(paired_nodes, n_paired, partner->carrier)) {
				++n_paired;
yb9976's avatar
yb9976 committed
163
164
165
166
				op->partner      = partner;
				partner->partner = op;
				break;
			}
Sebastian Hack's avatar
Sebastian Hack committed
167
168
169
170
		}
	}
}

171
static void handle_constraints(be_chordal_env_t *const env, ir_node *const irn)
172
{
173
	void *const base = obstack_base(&env->obst);
174
	be_insn_t  *insn = be_scan_insn(env, irn);
Christoph Mallon's avatar
Christoph Mallon committed
175
176
177

	/* Perms inserted before the constraint handling phase are considered to be
	 * correctly precolored. These Perms arise during the ABI handling phase. */
178
	if (!insn || is_Phi(irn))
Matthias Braun's avatar
Matthias Braun committed
179
		goto end;
180

Christoph Mallon's avatar
Christoph Mallon committed
181
	/* Prepare the constraint handling of this node.
Christoph Mallon's avatar
Christoph Mallon committed
182
	 * Perms are constructed and Copies are created for constrained values
Christoph Mallon's avatar
Christoph Mallon committed
183
184
	 * interfering with the instruction. */
	ir_node *const perm = pre_process_constraints(env, &insn);
185

Matthias Braun's avatar
Matthias Braun committed
186
	/* find suitable in operands to the out operands of the node. */
Christoph Mallon's avatar
Christoph Mallon committed
187
188
189
190
191
192
193
194
195
196
197
198
199
	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
Matthias Braun's avatar
Matthias Braun committed
200
	for (int i = 0, n_ops = insn->n_ops; i < n_ops; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
201
		/* If the operand has no partner or the partner has not been marked
Christoph Mallon's avatar
Christoph Mallon committed
202
203
		 * for allocation, determine the admissible registers and mark it
		 * for allocation by associating the node and its partner with the
Christoph Mallon's avatar
Christoph Mallon committed
204
205
		 * set of admissible registers via a bipartite graph. */
		be_operand_t *const op = &insn->ops[i];
206
207
		if (!op->carrier)
			continue;
Christoph Mallon's avatar
Christoph Mallon committed
208
209
		if (op->partner && pmap_contains(partners, op->partner->carrier))
			continue;
210

Christoph Mallon's avatar
Christoph Mallon committed
211
212
213
214
		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);
215

Christoph Mallon's avatar
Christoph Mallon committed
216
		alloc_nodes[n_alloc] = op->carrier;
217

Christoph Mallon's avatar
Christoph Mallon committed
218
		DBG((dbg, LEVEL_2, "\tassociating %+F and %+F\n", op->carrier, partner));
Matthias Braun's avatar
Matthias Braun committed
219

220
		unsigned const *const bs = get_decisive_partner_regs(op, n_regs);
Christoph Mallon's avatar
Christoph Mallon committed
221
222
223
		if (bs) {
			DBG((dbg, LEVEL_2, "\tallowed registers for %+F: %B\n", op->carrier, bs));

224
			rbitset_foreach(bs, n_regs, col) {
Christoph Mallon's avatar
Christoph Mallon committed
225
226
227
228
229
230
231
232
#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));
233
		}
Christoph Mallon's avatar
Christoph Mallon committed
234
235

		n_alloc++;
Matthias Braun's avatar
Matthias Braun committed
236
	}
237

Christoph Mallon's avatar
Christoph Mallon committed
238
239
	/* Put all nodes which live through the constrained instruction also to the
	 * allocation bipartite graph. They are considered unconstrained. */
Christoph Mallon's avatar
Christoph Mallon committed
240
	if (perm != NULL) {
Matthias Braun's avatar
Matthias Braun committed
241
		foreach_out_edge(perm, edge) {
Christoph Mallon's avatar
Christoph Mallon committed
242
			ir_node *const proj = get_edge_src_irn(edge);
Matthias Braun's avatar
Matthias Braun committed
243
			assert(is_Proj(proj));
244

Christoph Mallon's avatar
Christoph Mallon committed
245
			/* Don't insert a node twice. */
yb9976's avatar
yb9976 committed
246
			if (pmap_contains(partners, proj))
247
248
				continue;

Matthias Braun's avatar
Matthias Braun committed
249
			assert(n_alloc < n_regs);
250

Matthias Braun's avatar
Matthias Braun committed
251
252
			alloc_nodes[n_alloc] = proj;
			pmap_insert(partners, proj, NULL);
253

254
			bitset_foreach(env->allocatable_regs, col) {
Christoph Mallon's avatar
Christoph Mallon committed
255
256
257
#if USE_HUNGARIAN
				hungarian_add(bp, n_alloc, col, 1);
#else
258
				bipartite_add(bp, n_alloc, col);
Christoph Mallon's avatar
Christoph Mallon committed
259
#endif
260
			}
Matthias Braun's avatar
Matthias Braun committed
261
262

			n_alloc++;
Sebastian Hack's avatar
Sebastian Hack committed
263
		}
Matthias Braun's avatar
Matthias Braun committed
264
	}
265

Matthias Braun's avatar
Matthias Braun committed
266
	/* Compute a valid register allocation. */
Christoph Mallon's avatar
Christoph Mallon committed
267
268
	int *const assignment = ALLOCAN(int, n_regs);
#if USE_HUNGARIAN
Matthias Braun's avatar
Matthias Braun committed
269
	hungarian_prepare_cost_matrix(bp, HUNGARIAN_MODE_MAXIMIZE_UTIL);
Christoph Mallon's avatar
Christoph Mallon committed
270
	int const match_res = hungarian_solve(bp, assignment, NULL, 1);
Matthias Braun's avatar
Matthias Braun committed
271
	assert(match_res == 0 && "matching failed");
272
273
274
#else
	bipartite_matching(bp, assignment);
#endif
275

Matthias Braun's avatar
Matthias Braun committed
276
	/* Assign colors obtained from the matching. */
Christoph Mallon's avatar
Christoph Mallon committed
277
	for (int i = 0; i < n_alloc; ++i) {
Christoph Mallon's avatar
Christoph Mallon committed
278
		assert(assignment[i] >= 0 && "there must have been a register assigned (node not register pressure faithful?)");
Christoph Mallon's avatar
Christoph Mallon committed
279
		arch_register_t const *const reg = arch_register_for_index(env->cls, assignment[i]);
280

Christoph Mallon's avatar
Christoph Mallon committed
281
		ir_node *const irn = alloc_nodes[i];
yb9976's avatar
yb9976 committed
282
283
		arch_set_irn_register(irn, reg);
		DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", irn, reg->name));
284

yb9976's avatar
yb9976 committed
285
		ir_node *const partner = pmap_get(ir_node, partners, irn);
Christoph Mallon's avatar
Christoph Mallon committed
286
287
288
		if (partner != NULL) {
			arch_set_irn_register(partner, reg);
			DBG((dbg, LEVEL_2, "\tsetting %+F to register %s\n", partner, reg->name));
289
		}
Matthias Braun's avatar
Matthias Braun committed
290
	}
291

Christoph Mallon's avatar
Christoph Mallon committed
292
293
294
#if USE_HUNGARIAN
	hungarian_free(bp);
#else
295
	bipartite_free(bp);
Christoph Mallon's avatar
Christoph Mallon committed
296
#endif
Matthias Braun's avatar
Matthias Braun committed
297
298
	pmap_destroy(partners);

299
end:
300
	obstack_free(&env->obst, base);
301
302
303
304
}

/**
 * Handle constraint nodes in each basic block.
305
 * handle_constraints() inserts Perm nodes which perm
306
307
 * over all values live at the constrained node right in front
 * of the constrained node. These Perms signal a constrained node.
308
 * For further comments, refer to handle_constraints().
309
 */
Christoph Mallon's avatar
Christoph Mallon committed
310
static void constraints(ir_node *const bl, void *const data)
311
{
312
	be_chordal_env_t *const env = (be_chordal_env_t*)data;
313
	sched_foreach_safe(bl, irn) {
314
		handle_constraints(env, irn);
315
	}
316
317
}

Christoph Mallon's avatar
Christoph Mallon committed
318
static void assign(ir_node *const block, void *const env_ptr)
319
{
320
321
	be_chordal_env_t *const env  = (be_chordal_env_t*)env_ptr;
	struct list_head *const head = get_block_border_head(env, block);
322

323
	DBG((dbg, LEVEL_4, "Assigning colors for block %+F\n", block));
324
	DBG((dbg, LEVEL_4, "\tusedef chain for block\n"));
325
	foreach_border_head(head, b) {
326
		DBG((dbg, LEVEL_4, "\t%s %+F/%d\n", b->is_def ? "def" : "use",
Sebastian Hack's avatar
Sebastian Hack committed
327
					b->irn, get_irn_idx(b->irn)));
328
329
	}

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

Christoph Mallon's avatar
Christoph Mallon committed
333
	/* Mind that the sequence of defs from back to front defines a perfect
334
	 * elimination order. So, coloring the definitions from first to last
Christoph Mallon's avatar
Christoph Mallon committed
335
	 * will work. */
336
	foreach_border_head(head, b) {
Christoph Mallon's avatar
Christoph Mallon committed
337
338
339
340
341
		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) {
342
			/* Make the color available upon a use. */
Christoph Mallon's avatar
Christoph Mallon committed
343
344
			arch_register_t const *const reg = arch_get_irn_register(irn);
			assert(reg && "Register must have been assigned");
345
			bitset_set(available, reg->index);
346
		} else {
347
			arch_register_t const *reg = arch_get_irn_register(irn);
348
349
350
			/* All live-ins must have a register assigned. (The dominators were
			 * allocated before.) */
			assert(b->is_real || reg);
Matthias Braun's avatar
Matthias Braun committed
351
			unsigned col;
352
			if (reg) {
353
				DBG((dbg, LEVEL_4, "%+F has reg %s\n", irn, reg->name));
354
				col = reg->index;
355
				assert(bitset_is_set(available, col) && "pre-colored register must be free");
Matthias Braun's avatar
Matthias Braun committed
356
			} else {
357
				assert(!arch_irn_is_ignore(irn));
358
				col = get_next_free_reg(available);
359
				reg = arch_register_for_index(env->cls, col);
360
				arch_set_irn_register(irn, reg);
361
			}
362
			bitset_clear(available, col);
363

364
			DBG((dbg, LEVEL_1, "\tassigning register %s(%d) to %+F\n", reg->name, col, irn));
365
366
		}
	}
367
368
}

369
static void be_ra_chordal_color(be_chordal_env_t *const chordal_env)
370
{
Christoph Mallon's avatar
Christoph Mallon committed
371
	ir_graph *const irg = chordal_env->irg;
372
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
373
	be_assure_live_sets(irg);
Sebastian Hack's avatar
Sebastian Hack committed
374

375
	/* Handle register targeting constraints */
376
	be_timer_push(T_CONSTR);
377
	dom_tree_walk_irg(irg, constraints, NULL, chordal_env);
378
	be_timer_pop(T_CONSTR);
379

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

382
	/* First, determine the pressure */
Christoph Mallon's avatar
Christoph Mallon committed
383
	dom_tree_walk_irg(irg, create_borders, NULL, chordal_env);
384
385

	/* Assign the colors */
386
	dom_tree_walk_irg(irg, assign, NULL, chordal_env);
Sebastian Hack's avatar
Sebastian Hack committed
387
}
388

Matthias Braun's avatar
Matthias Braun committed
389
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_chordal)
390
391
void be_init_chordal(void)
{
392
393
394
	static be_ra_chordal_coloring_t coloring = {
		be_ra_chordal_color
	};
Michael Beck's avatar
Michael Beck committed
395
	FIRM_DBG_REGISTER(dbg, "firm.be.chordal");
396
397

	be_register_chordal_coloring("default", &coloring);
398
}