becopyopt.c 23.4 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
 */

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
11
12
13
14
15
 * @file
 * @brief       Copy minimization driver.
 * @author      Daniel Grund
 * @date        12.04.2005
 *
 * Main file for the optimization reducing the copies needed for:
 * - Phi coalescing
 * - Register-constrained nodes
 * - Two-address code instructions
16
 */
17
#include "debug.h"
Matthias Braun's avatar
Matthias Braun committed
18
#include "panic.h"
19
#include "execfreq_t.h"
Matthias Braun's avatar
Matthias Braun committed
20
21
#include "irdump_t.h"
#include "iredges_t.h"
22
#include "irgwalk.h"
Daniel Grund's avatar
Daniel Grund committed
23
#include "irloop_t.h"
24
#include "irnode_t.h"
25
#include "irprintf.h"
Matthias Braun's avatar
Matthias Braun committed
26
#include "irprog.h"
27
#include "irtools.h"
Matthias Braun's avatar
Matthias Braun committed
28
29
#include "pmap.h"
#include "raw_bitset.h"
30
#include "util.h"
Matthias Braun's avatar
Matthias Braun committed
31
#include "xmalloc.h"
Sebastian Hack's avatar
Sebastian Hack committed
32

33
#include "bearch.h"
34
#include "becopyopt_t.h"
Matthias Braun's avatar
Matthias Braun committed
35
36
#include "bedump.h"
#include "beifg.h"
Sebastian Hack's avatar
Sebastian Hack committed
37
#include "beinsn_t.h"
Matthias Braun's avatar
Matthias Braun committed
38
#include "beirg.h"
Matthias Braun's avatar
Matthias Braun committed
39
#include "belive.h"
Matthias Braun's avatar
Matthias Braun committed
40
41
#include "bemodule.h"
#include "benode.h"
Matthias Braun's avatar
Matthias Braun committed
42
#include "statev_t.h"
Daniel Grund's avatar
Daniel Grund committed
43

Matthias Braun's avatar
Matthias Braun committed
44
45
#include "lc_opts.h"
#include "lc_opts_enum.h"
46

Matthias Braun's avatar
Matthias Braun committed
47
48
#define MIS_HEUR_TRIGGER 8

Sebastian Hack's avatar
Sebastian Hack committed
49
50
51
52
53
#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_APPEL  4
#define DUMP_ALL    2 * DUMP_APPEL - 1

Matthias Braun's avatar
Matthias Braun committed
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#define list_entry_units(lh) list_entry(lh, unit_t, units)

/**
 * Statistics over a copy optimization module.
 */
typedef struct {
	unsigned long long aff_edges;            /**< number of affinity edges. */
	unsigned long long aff_nodes;            /**< number of nodes with incident affinity edges. */
	unsigned long long aff_int;              /**< number of affinity edges whose nodes also interfere. */
	unsigned long long inevit_costs;         /**< costs which cannot be evited (due to interfering affinities). */
	unsigned long long max_costs;            /**< all costs of the affinities. */
	unsigned long long costs;                /**< The costs of the current coloring. */
	unsigned long long unsatisfied_edges;    /**< The number of unequally colored affinity edges. */
} co_complete_stats_t;
Sebastian Hack's avatar
Sebastian Hack committed
68

Matthias Braun's avatar
Matthias Braun committed
69
70
71
72
73
74
75
76
77
78
/**
 * Flags for dumping the IFG.
 */
enum {
	CO_IFG_DUMP_COLORS = 1 << 0, /**< Dump the graph colored. */
	CO_IFG_DUMP_LABELS = 1 << 1, /**< Dump node/edge labels. */
	CO_IFG_DUMP_SHAPE  = 1 << 2, /**< Give constrained nodes special shapes. */
	CO_IFG_DUMP_CONSTR = 1 << 3, /**< Dump the node constraints in the label. */
};

Matthias Braun's avatar
Matthias Braun committed
79
80
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

Matthias Braun's avatar
Matthias Braun committed
81
82
83
84
static int co_get_costs_loop_depth(const ir_node *root, int pos);
static int co_get_costs_exec_freq(const ir_node *root, int pos);
static int co_get_costs_all_one(const ir_node *root, int pos);

Christian Würdig's avatar
Christian Würdig committed
85
static unsigned   dump_flags  = 0;
Matthias Braun's avatar
Matthias Braun committed
86
static unsigned   style_flags = CO_IFG_DUMP_COLORS;
87
static bool       do_stats    = false;
Sebastian Hack's avatar
Sebastian Hack committed
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
static cost_fct_t cost_func   = co_get_costs_exec_freq;

static const lc_opt_enum_mask_items_t dump_items[] = {
	{ "before",  DUMP_BEFORE },
	{ "after",   DUMP_AFTER  },
	{ "appel",   DUMP_APPEL  },
	{ "all",     DUMP_ALL    },
	{ NULL,      0 }
};

static const lc_opt_enum_mask_items_t style_items[] = {
	{ "color",   CO_IFG_DUMP_COLORS },
	{ "labels",  CO_IFG_DUMP_LABELS },
	{ "constr",  CO_IFG_DUMP_CONSTR },
	{ "shape",   CO_IFG_DUMP_SHAPE  },
	{ "full",    2 * CO_IFG_DUMP_SHAPE - 1 },
	{ NULL,      0 }
};

Matthias Braun's avatar
Matthias Braun committed
107
typedef int (*opt_funcptr)(void);
Sebastian Hack's avatar
Sebastian Hack committed
108
static const lc_opt_enum_func_ptr_items_t cost_func_items[] = {
Matthias Braun's avatar
Matthias Braun committed
109
110
111
112
	{ "freq",   (opt_funcptr) co_get_costs_exec_freq },
	{ "loop",   (opt_funcptr) co_get_costs_loop_depth },
	{ "one",    (opt_funcptr) co_get_costs_all_one },
	{ NULL,     NULL }
Sebastian Hack's avatar
Sebastian Hack committed
113
114
115
116
117
118
119
120
121
122
123
};

static lc_opt_enum_mask_var_t dump_var = {
	&dump_flags, dump_items
};

static lc_opt_enum_mask_var_t style_var = {
	&style_flags, style_items
};

static lc_opt_enum_func_ptr_var_t cost_func_var = {
Matthias Braun's avatar
Matthias Braun committed
124
	(opt_funcptr*) &cost_func, cost_func_items
Sebastian Hack's avatar
Sebastian Hack committed
125
126
127
};

static const lc_opt_table_entry_t options[] = {
128
129
130
131
	LC_OPT_ENT_ENUM_FUNC_PTR ("cost",  "select a cost function",                     &cost_func_var),
	LC_OPT_ENT_ENUM_MASK     ("dump",  "dump ifg before or after copy optimization", &dump_var),
	LC_OPT_ENT_ENUM_MASK     ("style", "dump style for ifg dumping",                 &style_var),
	LC_OPT_ENT_BOOL          ("stats", "dump statistics after each optimization",    &do_stats),
132
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
133
};
Sebastian Hack's avatar
Sebastian Hack committed
134

135
136
137
138
139
140
141
142
143
144
static be_module_list_entry_t *copyopts = NULL;
static const co_algo_info *selected_copyopt = NULL;

void be_register_copyopt(const char *name, co_algo_info *copyopt)
{
	if (selected_copyopt == NULL)
		selected_copyopt = copyopt;
	be_add_module_to_list(&copyopts, name, copyopt);
}

Matthias Braun's avatar
Matthias Braun committed
145
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyopt)
yb9976's avatar
yb9976 committed
146
void be_init_copyopt(void)
Sebastian Hack's avatar
Sebastian Hack committed
147
{
Matthias Braun's avatar
Matthias Braun committed
148
149
	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");
150
	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
Matthias Braun's avatar
Matthias Braun committed
151
	lc_opt_entry_t *co_grp      = lc_opt_get_grp(chordal_grp, "co");
Sebastian Hack's avatar
Sebastian Hack committed
152

153
	lc_opt_add_table(co_grp, options);
154
	be_add_module_list_opt(co_grp, "algo", "select copy optimization algo",
Matthias Braun's avatar
Matthias Braun committed
155
	                       &copyopts, (void**) &selected_copyopt);
156
157
158
159
}

static int void_algo(copy_opt_t *co)
{
Matthias Braun's avatar
Matthias Braun committed
160
	(void)co;
161
162
163
	return 0;
}

Matthias Braun's avatar
Matthias Braun committed
164
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copynone)
165
166
167
void be_init_copynone(void)
{
	static co_algo_info copyheur = {
168
		void_algo
169
170
171
	};

	be_register_copyopt("none", &copyheur);
Sebastian Hack's avatar
Sebastian Hack committed
172
}
173

Matthias Braun's avatar
Matthias Braun committed
174
static copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
Sebastian Hack's avatar
Sebastian Hack committed
175
{
176
	FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
Daniel Grund's avatar
Daniel Grund committed
177

178
	copy_opt_t *const co = XMALLOCZ(copy_opt_t);
Daniel Grund's avatar
Daniel Grund committed
179
180
181
182
183
184
185
	co->cenv      = chordal_env;
	co->irg       = chordal_env->irg;
	co->cls       = chordal_env->cls;
	co->get_costs = get_costs;
	return co;
}

Matthias Braun's avatar
Matthias Braun committed
186
static void free_copy_opt(copy_opt_t *co)
187
{
Daniel Grund's avatar
Daniel Grund committed
188
	free(co);
Daniel Grund's avatar
Daniel Grund committed
189
190
}

191
192
193
194
/**
 * Checks if a node is optimizable, viz. has something to do with coalescing
 * @param irn  The irn to check
 */
Matthias Braun's avatar
Matthias Braun committed
195
static bool co_is_optimizable_root(const ir_node *irn)
196
{
197
	arch_register_req_t const *const req = arch_get_irn_register_req(irn);
198
	if (req->ignore)
Matthias Braun's avatar
Matthias Braun committed
199
		return false;
Daniel Grund's avatar
Daniel Grund committed
200

201
	if (is_Phi(irn) || is_Perm_Proj(irn))
Matthias Braun's avatar
Matthias Braun committed
202
		return true;
203

204
	if (req->should_be_same != 0)
Matthias Braun's avatar
Matthias Braun committed
205
		return true;
Daniel Grund's avatar
Daniel Grund committed
206

Matthias Braun's avatar
Matthias Braun committed
207
	return false;
Daniel Grund's avatar
Daniel Grund committed
208
209
}

Matthias Braun's avatar
Matthias Braun committed
210
211
212
213
214
215
/**
 * Computes the costs of a copy according to loop depth
 * @param pos  the argument position of arg in the root arguments
 * @return     Must be >= 0 in all cases.
 */
static int co_get_costs_loop_depth(const ir_node *root, int pos)
216
{
Matthias Braun's avatar
Matthias Braun committed
217
	ir_node *block = get_nodes_block(root);
Matthias Braun's avatar
Matthias Braun committed
218
	if (is_Phi(root))
Matthias Braun's avatar
Matthias Braun committed
219
		block = get_Block_cfgpred_block(block, pos);
Matthias Braun's avatar
Matthias Braun committed
220

Matthias Braun's avatar
Matthias Braun committed
221
222
	ir_loop *loop = get_irn_loop(block);
	int cost;
Matthias Braun's avatar
Matthias Braun committed
223
	if (loop != NULL) {
Daniel Grund's avatar
Daniel Grund committed
224
225
		int d = get_loop_depth(loop);
		cost = d*d;
Matthias Braun's avatar
Matthias Braun committed
226
227
	} else {
		cost = 0;
Daniel Grund's avatar
Daniel Grund committed
228
	}
Matthias Braun's avatar
Matthias Braun committed
229
	return cost+1;
Daniel Grund's avatar
Daniel Grund committed
230
231
}

232
static ir_execfreq_int_factors factors;
233
/* Remember the graph that we computed the factors for. */
Matthias Braun's avatar
Matthias Braun committed
234
static ir_graph               *irg_for_factors;
235

Matthias Braun's avatar
Matthias Braun committed
236
237
238
239
240
241
/**
 * Computes the costs of a copy according to execution frequency
 * @param pos  the argument position of arg in the root arguments
 * @return Must be >= 0 in all cases.
 */
static int co_get_costs_exec_freq(const ir_node *root, int pos)
242
{
243
244
	ir_node *root_bl = get_nodes_block(root);
	ir_node *copy_bl
Matthias Braun's avatar
Matthias Braun committed
245
		= is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
246
	int      res     = get_block_execfreq_int(&factors, copy_bl);
247
248

	/* don't allow values smaller than one. */
Christoph Mallon's avatar
Christoph Mallon committed
249
	return MAX(1, res);
Sebastian Hack's avatar
Sebastian Hack committed
250
251
}

Matthias Braun's avatar
Matthias Braun committed
252
253
254
255
256
257
/**
 * All costs equal 1. Using this will reduce the _number_ of copies.
 * @param co   The copy opt object.
 * @return Must be >= 0 in all cases.
 */
static int co_get_costs_all_one(const ir_node *root, int pos)
258
{
Matthias Braun's avatar
Matthias Braun committed
259
260
	(void)root;
	(void)pos;
Daniel Grund's avatar
Daniel Grund committed
261
262
263
	return 1;
}

Daniel Grund's avatar
Daniel Grund committed
264
/**
Daniel Grund's avatar
Daniel Grund committed
265
266
 * Determines a maximum weighted independent set with respect to
 * the interference and conflict edges of all nodes in a qnode.
Daniel Grund's avatar
Daniel Grund committed
267
 */
268
static int ou_max_ind_set_costs(unit_t *const ou)
269
{
Daniel Grund's avatar
Daniel Grund committed
270
271
	/* assign the nodes into two groups.
	 * safe: node has no interference, hence it is in every max stable set.
Matthias Braun's avatar
Matthias Braun committed
272
273
274
275
276
277
278
279
	 * unsafe: node has an interference */
	ir_node **safe         = ALLOCAN(ir_node*, ou->node_count - 1);
	int       safe_costs   = 0;
	int       safe_count   = 0;
	ir_node **unsafe       = ALLOCAN(ir_node*, ou->node_count - 1);
	int      *unsafe_costs = ALLOCAN(int,      ou->node_count - 1);
	int       unsafe_count = 0;
	for (int i=1; i<ou->node_count; ++i) {
Matthias Braun's avatar
Matthias Braun committed
280
281
		bool     is_safe = true;
		ir_node *i_node  = ou->nodes[i];
Matthias Braun's avatar
Matthias Braun committed
282
		for (int o=1; o<ou->node_count; ++o) {
Matthias Braun's avatar
Matthias Braun committed
283
284
			ir_node *o_node = ou->nodes[o];
			if (i_node == o_node)
Daniel Grund's avatar
Daniel Grund committed
285
				continue;
286
			if (be_values_interfere(i_node, o_node)) {
Daniel Grund's avatar
Daniel Grund committed
287
				unsafe_costs[unsafe_count] = ou->costs[i];
Matthias Braun's avatar
Matthias Braun committed
288
				unsafe[unsafe_count] = i_node;
Daniel Grund's avatar
Daniel Grund committed
289
				++unsafe_count;
Matthias Braun's avatar
Matthias Braun committed
290
				is_safe = false;
Daniel Grund's avatar
Daniel Grund committed
291
292
293
294
295
				break;
			}
		}
		if (is_safe) {
			safe_costs += ou->costs[i];
Matthias Braun's avatar
Matthias Braun committed
296
			safe[safe_count++] = i_node;
Daniel Grund's avatar
Daniel Grund committed
297
298
		}
	}
Daniel Grund's avatar
Daniel Grund committed
299

300
	/* now compute the best set out of the unsafe nodes*/
Matthias Braun's avatar
Matthias Braun committed
301
	int best_weight = 0;
302
303
	if (unsafe_count > MIS_HEUR_TRIGGER) {
		bitset_t *best = bitset_alloca(unsafe_count);
304
		/* Heuristic: Greedy trial and error form index 0 to unsafe_count-1 */
Matthias Braun's avatar
Matthias Braun committed
305
		for (int i=0; i<unsafe_count; ++i) {
306
307
			bitset_set(best, i);
			/* check if it is a stable set */
Matthias Braun's avatar
Matthias Braun committed
308
			for (int o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
309
				if (be_values_interfere(unsafe[i], unsafe[o])) {
310
311
312
					bitset_clear(best, i); /* clear the bit and try next one */
					break;
				}
Daniel Grund's avatar
Daniel Grund committed
313
		}
314
315
316
317
318
		/* compute the weight */
		bitset_foreach(best, pos)
			best_weight += unsafe_costs[pos];
	} else {
		/* Exact Algorithm: Brute force */
Matthias Braun's avatar
Matthias Braun committed
319
		bitset_t *curr = bitset_alloca(unsafe_count);
320
		bitset_set_all(curr);
321
		while (bitset_popcount(curr) != 0) {
322
			/* check if curr is a stable set */
Matthias Braun's avatar
Matthias Braun committed
323
324
			for (int i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
				for (int o=bitset_next_set(curr, i+1); o!=-1; o=bitset_next_set(curr, o+1)) /* !!!!! difference to qnode_max_ind_set(): NOT (curr, i) */
325
						if (be_values_interfere(unsafe[i], unsafe[o]))
326
327
328
							goto no_stable_set;

			/* if we arrive here, we have a stable set */
329
			/* compute the weight of the stable set*/
Matthias Braun's avatar
Matthias Braun committed
330
			int curr_weight = 0;
331
332
333
334
335
336
337
			bitset_foreach(curr, pos)
				curr_weight += unsafe_costs[pos];

			/* any better ? */
			if (curr_weight > best_weight) {
				best_weight = curr_weight;
			}
Daniel Grund's avatar
Daniel Grund committed
338

339
340
341
	no_stable_set:
			bitset_minus1(curr);
		}
Daniel Grund's avatar
Daniel Grund committed
342
	}
Daniel Grund's avatar
Daniel Grund committed
343
344

	return safe_costs+best_weight;
Daniel Grund's avatar
Daniel Grund committed
345
}
346

347
348
static void co_collect_units(ir_node *irn, void *env)
{
349
350
	if (get_irn_mode(irn) == mode_T)
		return;
Matthias Braun's avatar
Matthias Braun committed
351
352
	copy_opt_t                *co  = (copy_opt_t*)env;
	const arch_register_req_t *req = arch_get_irn_register_req(irn);
353
	if (req->cls != co->cls)
354
		return;
355
	if (!co_is_optimizable_root(irn))
356
		return;
357

358
	/* Init a new unit */
Matthias Braun's avatar
Matthias Braun committed
359
	unit_t *unit = XMALLOCZ(unit_t);
360
	unit->node_count = 1;
361
362
	INIT_LIST_HEAD(&unit->queue);

363
	/* Phi with some/all of its arguments */
364
	if (is_Phi(irn)) {
365
		/* init */
366
		int const arity = get_irn_arity(irn);
367
368
		unit->nodes = XMALLOCN(ir_node*, arity + 1);
		unit->costs = XMALLOCN(int,      arity + 1);
369
370
371
		unit->nodes[0] = irn;

		/* fill */
372
		foreach_irn_in(irn, i, arg) {
373
			assert(arch_get_irn_register_req(arg)->cls == co->cls && "Argument not in same register class.");
374
			if (arg == irn)
375
				continue;
376
			if (be_values_interfere(irn, arg)) {
Matthias Braun's avatar
Matthias Braun committed
377
				unit->inevitable_costs += co->get_costs(irn, i);
378
379
380
381
				continue;
			}

			/* Else insert the argument of the phi to the members of this ou */
382
			DBG((dbg, LEVEL_1, "\t   Member: %+F\n", arg));
383

384
385
			if (arch_irn_is_ignore(arg))
				continue;
386

387
			/* Check if arg has occurred at a prior position in the arg/list */
Matthias Braun's avatar
Matthias Braun committed
388
389
			int arg_pos = 0;
			for (int o=1; o<unit->node_count; ++o) {
390
391
392
				if (unit->nodes[o] == arg) {
					arg_pos = o;
					break;
393
				}
394
			}
395
396
397
398

			if (!arg_pos) { /* a new argument */
				/* insert node, set costs */
				unit->nodes[unit->node_count] = arg;
Matthias Braun's avatar
Matthias Braun committed
399
				unit->costs[unit->node_count] = co->get_costs(irn, i);
400
401
402
				unit->node_count++;
			} else { /* arg has occurred before in same phi */
				/* increase costs for existing arg */
Matthias Braun's avatar
Matthias Braun committed
403
				unit->costs[arg_pos] += co->get_costs(irn, i);
404
			}
Daniel Grund's avatar
Daniel Grund committed
405
		}
406
407
		unit->nodes = XREALLOC(unit->nodes, ir_node*, unit->node_count);
		unit->costs = XREALLOC(unit->costs, int,      unit->node_count);
408
	} else if (is_Perm_Proj(irn)) {
409
		/* Proj of a perm with corresponding arg */
410
		assert(!be_values_interfere(irn, get_Perm_src(irn)));
Matthias Braun's avatar
Matthias Braun committed
411
412
		unit->nodes      = XMALLOCN(ir_node*, 2);
		unit->costs      = XMALLOCN(int,      2);
413
		unit->node_count = 2;
Matthias Braun's avatar
Matthias Braun committed
414
415
416
		unit->nodes[0]   = irn;
		unit->nodes[1]   = get_Perm_src(irn);
		unit->costs[1]   = co->get_costs(irn, -1);
417
	} else if (req->should_be_same != 0) {
Matthias Braun's avatar
Matthias Braun committed
418
		/* Src == Tgt of a 2-addr-code instruction */
419
		const unsigned other = req->should_be_same;
420

Matthias Braun's avatar
Matthias Braun committed
421
422
		int count = 0;
		for (int i = 0; (1U << i) <= other; ++i) {
423
			if (other & (1U << i)) {
Matthias Braun's avatar
Matthias Braun committed
424
				ir_node *o = get_irn_n(skip_Proj(irn), i);
425
426
				if (arch_irn_is_ignore(o))
					continue;
427
				if (be_values_interfere(irn, o))
428
429
430
431
					continue;
				++count;
			}
		}
432

433
434
435
436
437
438
439
440
		if (count != 0) {
			int k = 0;
			++count;
			unit->nodes = XMALLOCN(ir_node*, count);
			unit->costs = XMALLOCN(int,      count);
			unit->node_count = count;
			unit->nodes[k++] = irn;

Matthias Braun's avatar
Matthias Braun committed
441
			for (int i = 0; 1U << i <= other; ++i) {
442
				if (other & (1U << i)) {
Matthias Braun's avatar
Matthias Braun committed
443
					ir_node *o = get_irn_n(skip_Proj(irn), i);
444
					if (!arch_irn_is_ignore(o) &&
445
							!be_values_interfere(irn, o)) {
446
447
448
						unit->nodes[k] = o;
						unit->costs[k] = co->get_costs(irn, -1);
						++k;
449
450
					}
				}
Matthias Braun's avatar
Matthias Braun committed
451
			}
452
		}
453
	} else {
454
		panic("this is not an optimizable node");
Matthias Braun's avatar
Matthias Braun committed
455
	}
456

457
	/* Insert the new unit at a position according to its costs */
458
	if (unit->node_count > 1) {
459
		/* Determine the maximum costs this unit can cause: all_nodes_cost */
Matthias Braun's avatar
Matthias Braun committed
460
		for (int i=1; i<unit->node_count; ++i) {
461
462
463
			unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
			unit->all_nodes_costs += unit->costs[i];
		}
464

465
		/* Determine the minimal costs this unit will cause: min_nodes_costs */
466
		unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
467
		/* Insert the new ou according to its sort_key */
Matthias Braun's avatar
Matthias Braun committed
468
469
470
		struct list_head *tmp = &co->units;
		while (tmp->next != &co->units
		       && list_entry_units(tmp->next)->sort_key > unit->sort_key) {
471
			tmp = tmp->next;
Matthias Braun's avatar
Matthias Braun committed
472
		}
473
		list_add(&unit->units, tmp);
474
475
	} else {
		free(unit);
476
	}
477
478
}

Matthias Braun's avatar
Matthias Braun committed
479
static void co_build_ou_structure(copy_opt_t *co)
480
{
481
	DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
482
	INIT_LIST_HEAD(&co->units);
483
	irg_walk_graph(co->irg, co_collect_units, NULL, co);
484
485
}

Matthias Braun's avatar
Matthias Braun committed
486
static void co_free_ou_structure(copy_opt_t *co)
487
{
Daniel Grund's avatar
Daniel Grund committed
488
	ASSERT_OU_AVAIL(co);
Daniel Grund's avatar
Daniel Grund committed
489
	list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
490
491
492
		free(curr->nodes);
		free(curr->costs);
		free(curr);
493
	}
Daniel Grund's avatar
Daniel Grund committed
494
	co->units.next = NULL;
495
496
}

497
498
int co_get_inevit_copy_costs(const copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
499
500
	ASSERT_OU_AVAIL(co);

Matthias Braun's avatar
Matthias Braun committed
501
	int res = 0;
502
503
504
505
506
	list_for_each_entry(unit_t, curr, &co->units, units)
		res += curr->inevitable_costs;
	return res;
}

507
508
int co_get_lower_bound(const copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
509
510
	ASSERT_OU_AVAIL(co);

Matthias Braun's avatar
Matthias Braun committed
511
	int res = 0;
512
	list_for_each_entry(unit_t, curr, &co->units, units)
513
		res += curr->inevitable_costs + curr->min_nodes_costs;
514
515
	return res;
}
Daniel Grund's avatar
Daniel Grund committed
516

Matthias Braun's avatar
Matthias Braun committed
517
static void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
518
{
Matthias Braun's avatar
Matthias Braun committed
519
	bitset_t *seen = bitset_malloc(get_irg_last_idx(co->irg));
520
521
522
523
524
525

	memset(stat, 0, sizeof(stat[0]));

	/* count affinity edges. */
	co_gs_foreach_aff_node(co, an) {
		stat->aff_nodes += 1;
Matthias Braun's avatar
Matthias Braun committed
526
		bitset_set(seen, get_irn_idx(an->irn));
527
		co_gs_foreach_neighb(an, neigh) {
Matthias Braun's avatar
Matthias Braun committed
528
			if (!bitset_is_set(seen, get_irn_idx(neigh->irn))) {
529
530
531
				stat->aff_edges += 1;
				stat->max_costs += neigh->costs;

532
				if (arch_get_irn_register(an->irn) != arch_get_irn_register(neigh->irn)) {
533
534
535
536
					stat->costs += neigh->costs;
					stat->unsatisfied_edges += 1;
				}

537
				if (be_values_interfere(an->irn, neigh->irn)) {
538
539
540
541
542
543
544
					stat->aff_int += 1;
					stat->inevit_costs += neigh->costs;
				}
			}
		}
	}

545
	free(seen);
546
547
}

548
549
static int compare_affinity_node_t(const void *k1, const void *k2, size_t size)
{
Matthias Braun's avatar
Matthias Braun committed
550
	(void)size;
551
552
	const affinity_node_t *n1 = (const affinity_node_t*)k1;
	const affinity_node_t *n2 = (const affinity_node_t*)k2;
Matthias Braun's avatar
Matthias Braun committed
553
	return n1->irn != n2->irn;
Daniel Grund's avatar
Daniel Grund committed
554
555
}

556
557
static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
{
Matthias Braun's avatar
Matthias Braun committed
558
	affinity_node_t new_node;
Daniel Grund's avatar
Daniel Grund committed
559
560
	new_node.irn        = n1;
	new_node.neighbours = NULL;
Matthias Braun's avatar
Matthias Braun committed
561
562
	affinity_node_t *node = set_insert(affinity_node_t, co->nodes, &new_node,
	                                   sizeof(new_node), hash_irn(new_node.irn));
Daniel Grund's avatar
Daniel Grund committed
563

Matthias Braun's avatar
Matthias Braun committed
564
565
566
	neighb_t *nbr;
	bool      allocnew = true;
	for (nbr = node->neighbours; nbr; nbr = nbr->next) {
Daniel Grund's avatar
Daniel Grund committed
567
		if (nbr->irn == n2) {
Matthias Braun's avatar
Matthias Braun committed
568
			allocnew = false;
Daniel Grund's avatar
Daniel Grund committed
569
570
			break;
		}
Matthias Braun's avatar
Matthias Braun committed
571
	}
Daniel Grund's avatar
Daniel Grund committed
572
573
574

	/* if we did not find n2 in n1's neighbourhood insert it */
	if (allocnew) {
575
		nbr        = OALLOC(&co->obst, neighb_t);
Daniel Grund's avatar
Daniel Grund committed
576
577
578
		nbr->irn   = n2;
		nbr->costs = 0;
		nbr->next  = node->neighbours;
579

Daniel Grund's avatar
Daniel Grund committed
580
581
582
583
584
585
586
		node->neighbours = nbr;
	}

	/* now nbr points to n1's neighbour-entry of n2 */
	nbr->costs += costs;
}

587
588
static inline void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
{
589
	if (n1 != n2 && !be_values_interfere(n1, n2)) {
Daniel Grund's avatar
Daniel Grund committed
590
591
592
593
594
		add_edge(co, n1, n2, costs);
		add_edge(co, n2, n1, costs);
	}
}

595
596
static void build_graph_walker(ir_node *irn, void *env)
{
597
598
	if (get_irn_mode(irn) == mode_T)
		return;
Matthias Braun's avatar
Matthias Braun committed
599
600
	copy_opt_t                *co  = (copy_opt_t*)env;
	const arch_register_req_t *req = arch_get_irn_register_req(irn);
601
	if (req->cls != co->cls || req->ignore)
Daniel Grund's avatar
Daniel Grund committed
602
603
		return;

604
	if (is_Phi(irn)) { /* Phis */
605
		foreach_irn_in(irn, pos, arg) {
Matthias Braun's avatar
Matthias Braun committed
606
			add_edges(co, irn, arg, co->get_costs(irn, pos));
Daniel Grund's avatar
Daniel Grund committed
607
		}
608
	} else if (is_Perm_Proj(irn)) { /* Perms */
Daniel Grund's avatar
Daniel Grund committed
609
		ir_node *arg = get_Perm_src(irn);
Matthias Braun's avatar
Matthias Braun committed
610
		add_edges(co, irn, arg, co->get_costs(irn, -1));
611
612
	} else if (req->should_be_same != 0) {
		const unsigned other = req->should_be_same;
Matthias Braun's avatar
Matthias Braun committed
613
		for (int i = 0; 1U << i <= other; ++i) {
614
615
616
617
			if (other & (1U << i)) {
				ir_node *other = get_irn_n(skip_Proj(irn), i);
				if (!arch_irn_is_ignore(other))
					add_edges(co, irn, other, co->get_costs(irn, -1));
618
			}
Matthias Braun's avatar
Matthias Braun committed
619
620
		}
	}
Daniel Grund's avatar
Daniel Grund committed
621
622
}

Matthias Braun's avatar
Matthias Braun committed
623
624
625
626
/**
 * Constructs another internal representation of the affinity edges
 */
static void co_build_graph_structure(copy_opt_t *co)
627
{
Daniel Grund's avatar
Daniel Grund committed
628
	obstack_init(&co->obst);
Daniel Grund's avatar
Daniel Grund committed
629
	co->nodes = new_set(compare_affinity_node_t, 32);
Daniel Grund's avatar
Daniel Grund committed
630
631
632
633

	irg_walk_graph(co->irg, build_graph_walker, NULL, co);
}

Matthias Braun's avatar
Matthias Braun committed
634
635
636
637
638
/**
 * Frees the space used by the graph representation.
 * Does NOT free the whole copyopt structure
 */
static void co_free_graph_structure(copy_opt_t *co)
639
{
Daniel Grund's avatar
Daniel Grund committed
640
641
	ASSERT_GS_AVAIL(co);

Daniel Grund's avatar
Daniel Grund committed
642
643
	del_set(co->nodes);
	obstack_free(&co->obst, NULL);
Daniel Grund's avatar
Daniel Grund committed
644
	co->nodes = NULL;
Daniel Grund's avatar
Daniel Grund committed
645
646
}

Matthias Braun's avatar
Matthias Braun committed
647
bool co_gs_is_optimizable(copy_opt_t const *const co, ir_node *const irn)
648
{
Daniel Grund's avatar
Daniel Grund committed
649
	ASSERT_GS_AVAIL(co);
Daniel Grund's avatar
Daniel Grund committed
650

Matthias Braun's avatar
Matthias Braun committed
651
	affinity_node_t new_node;
652
	new_node.irn = irn;
Matthias Braun's avatar
Matthias Braun committed
653
654
	affinity_node_t *n = set_find(affinity_node_t, co->nodes, &new_node,
	                              sizeof(new_node), hash_irn(new_node.irn));
655
	return n && n->neighbours;
Daniel Grund's avatar
Daniel Grund committed
656
}
Sebastian Hack's avatar
Sebastian Hack committed
657

658
static bool co_dump_appel_disjoint_constraints(ir_node *const a, ir_node *const b)
Sebastian Hack's avatar
Sebastian Hack committed
659
{
660
	arch_register_req_t const *const reqa = arch_get_irn_register_req(a);
661
	if (reqa->limited == NULL)
662
		return false;
Sebastian Hack's avatar
Sebastian Hack committed
663

664
	arch_register_req_t const *const reqb = arch_get_irn_register_req(b);
665
	if (reqb->limited == NULL)
666
		return false;
Sebastian Hack's avatar
Sebastian Hack committed
667

668
	return !rbitsets_have_common(reqa->limited, reqb->limited, reqa->cls->n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
669
670
}

Matthias Braun's avatar
Matthias Braun committed
671
672
673
674
675
676
677
678
/**
 * Dump the interference graph according to the Appel/George coalescing contest file format.
 * See: http://www.cs.princeton.edu/~appel/coalesce/format.html
 * @note Requires graph structure.
 * @param co The copy opt object.
 * @param f  A file to dump to.
 */
static void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
Sebastian Hack's avatar
Sebastian Hack committed
679
{
680
681
682
	be_ifg_t *ifg       = co->cenv->ifg;
	int      *color_map = ALLOCAN(int, co->cls->n_regs);
	int      *node_map  = XMALLOCN(int, get_irg_last_idx(co->irg) + 1);
683
684
	ir_graph *irg       = co->irg;
	be_irg_t *birg      = be_birg_from_irg(irg);
Sebastian Hack's avatar
Sebastian Hack committed
685

Matthias Braun's avatar
Matthias Braun committed
686
687
	unsigned n_regs = 0;
	for (unsigned i = 0; i < co->cls->n_regs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
688
		const arch_register_t *reg = &co->cls->regs[i];
689
690
691
692
693
		if (rbitset_is_set(birg->allocatable_regs, reg->global_index)) {
			color_map[i] = n_regs++;
		} else {
			color_map[i] = -1;
		}
Sebastian Hack's avatar
Sebastian Hack committed
694
695
696
697
698
699
	}

	/*
	 * n contains the first node number.
	 * the values below n are the pre-colored register nodes
	 */
Sebastian Hack's avatar
Sebastian Hack committed
700

Matthias Braun's avatar
Matthias Braun committed
701
	unsigned n = n_regs;
702
	be_ifg_foreach_node(ifg, irn) {
703
704
705
		if (arch_irn_is_ignore(irn))
			continue;
		node_map[get_irn_idx(irn)] = n++;
Sebastian Hack's avatar
Sebastian Hack committed
706
707
	}

Matthias Braun's avatar
Matthias Braun committed
708
	fprintf(f, "%u %u\n", n, n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
709

710
	be_ifg_foreach_node(ifg, irn) {
711
		arch_register_req_t const *const req = arch_get_irn_register_req(irn);
712
		if (req->ignore)
713
714
715
716
717
			continue;

		int              idx = node_map[get_irn_idx(irn)];
		affinity_node_t *a   = get_affinity_info(co, irn);

718
		if (req->limited != NULL) {
Matthias Braun's avatar
Matthias Braun committed
719
			for (unsigned i = 0; i < co->cls->n_regs; ++i) {
720
721
				if (!rbitset_is_set(req->limited, i) && color_map[i] >= 0)
					fprintf(f, "%d %d -1\n", color_map[i], idx);
Sebastian Hack's avatar
Sebastian Hack committed
722
			}
723
		}
Sebastian Hack's avatar
Sebastian Hack committed
724

Matthias Braun's avatar
Matthias Braun committed
725
		neighbours_iter_t nit;
726
		be_ifg_foreach_neighbour(ifg, &nit, irn, adj) {
Matthias Braun's avatar
Matthias Braun committed
727
728
			if (!arch_irn_is_ignore(adj)
			    && !co_dump_appel_disjoint_constraints(irn, adj)) {
729
730
731
				int adj_idx = node_map[get_irn_idx(adj)];
				if (idx < adj_idx)
					fprintf(f, "%d %d -1\n", idx, adj_idx);
Sebastian Hack's avatar
Sebastian Hack committed
732
			}
733
		}
Sebastian Hack's avatar
Sebastian Hack committed
734

735
736
737
738
739
740
		if (a) {
			co_gs_foreach_neighb(a, n) {
				if (!arch_irn_is_ignore(n->irn)) {
					int n_idx = node_map[get_irn_idx(n->irn)];
					if (idx < n_idx)
						fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
Sebastian Hack's avatar
Sebastian Hack committed
741
742
743
744
				}
			}
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
745

746
	free(node_map);
Sebastian Hack's avatar
Sebastian Hack committed
747
748
}

Matthias Braun's avatar
Matthias Braun committed
749
750
static FILE *my_open(const be_chordal_env_t *env, const char *prefix,
                     const char *suffix)
751
{
752
	const char *cup_name = be_get_irg_main_env(env->irg)->cup_name;
Matthias Braun's avatar
Matthias Braun committed
753
754
	size_t      n        = strlen(cup_name);
	char       *tu_name  = XMALLOCN(char, n + 1);
755
	strcpy(tu_name, cup_name);
Matthias Braun's avatar
Matthias Braun committed
756
	for (size_t i = 0; i < n; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
757
758
		if (tu_name[i] == '.')
			tu_name[i] = '_';
Matthias Braun's avatar
Matthias Braun committed
759
	}
760

Sebastian Hack's avatar
Sebastian Hack committed
761

Matthias Braun's avatar
Matthias Braun committed
762
	char buf[1024];
Matthias Braun's avatar
Matthias Braun committed
763
764
	ir_snprintf(buf, sizeof(buf), "%s%s_%F_%s%s", prefix, tu_name, env->irg,
	            env->cls->name, suffix);
765
	free(tu_name);
Matthias Braun's avatar
Matthias Braun committed
766
	FILE *result = fopen(buf, "wt");
767
	if (result == NULL) {
768
		panic("couldn't open '%s' for writing", buf);
769
770
771
772
773
	}

	return result;
}

Sebastian Hack's avatar
Sebastian Hack committed
774
775
void co_driver(be_chordal_env_t *cenv)
{
Matthias Braun's avatar
Matthias Braun committed
776
	ir_timer_t *timer = ir_timer_new();
Sebastian Hack's avatar
Sebastian Hack committed
777

778
	/* skip copymin if algo is 'none' */
779
	if (selected_copyopt->copyopt == void_algo)
780
781
		return;

782
783
784
785
786
	if (cost_func == co_get_costs_exec_freq && irg_for_factors != cenv->irg) {
		ir_calculate_execfreq_int_factors(&factors, cenv->irg);
		irg_for_factors = cenv->irg;
	}

787
	be_assure_live_chk(cenv->irg);
Sebastian Hack's avatar
Sebastian Hack committed
788

Matthias Braun's avatar
Matthias Braun committed
789
	copy_opt_t *co = new_copy_opt(cenv, cost_func);
Sebastian Hack's avatar
Sebastian Hack committed
790
791
	co_build_ou_structure(co);
	co_build_graph_structure(co);
792

Matthias Braun's avatar
Matthias Braun committed
793
	co_complete_stats_t before;
794
795
	co_complete_stats(co, &before);

Matthias Braun's avatar
Matthias Braun committed
796
797
798
799
800
	stat_ev_ull("co_aff_nodes",    before.aff_nodes);
	stat_ev_ull("co_aff_edges",    before.aff_edges);
	stat_ev_ull("co_max_costs",    before.max_costs);
	stat_ev_ull("co_inevit_costs", before.inevit_costs);
	stat_ev_ull("co_aff_int",      before.aff_int);
801

Matthias Braun's avatar
Matthias Braun committed
802
803
	stat_ev_ull("co_init_costs",   before.costs);
	stat_ev_ull("co_init_unsat",   before.unsatisfied_edges);
Sebastian Hack's avatar
Sebastian Hack committed
804

Christian Würdig's avatar
Christian Würdig committed
805
	if (dump_flags & DUMP_BEFORE) {
Matthias Braun's avatar
Matthias Braun committed
806
807
		FILE *f = my_open(cenv, "", "-before.vcg");
		be_dump_ifg_co(f, co, style_flags & CO_IFG_DUMP_LABELS, style_flags & CO_IFG_DUMP_COLORS);
Sebastian Hack's avatar
Sebastian Hack committed
808
809
810
		fclose(f);
	}

Christian Würdig's avatar
Christian Würdig committed
811
	/* perform actual copy minimization */
Matthias Braun's avatar
Matthias Braun committed
812
	ir_timer_reset_and_start(timer);
Matthias Braun's avatar
Matthias Braun committed
813
	int was_optimal = selected_copyopt->copyopt(co);
Matthias Braun's avatar
Matthias Braun committed
814
	ir_timer_stop(timer);
Sebastian Hack's avatar
Sebastian Hack committed
815

Matthias Braun's avatar
Matthias Braun committed
816
817
	stat_ev_dbl("co_time", ir_timer_elapsed_msec(timer));
	stat_ev_ull("co_optimal", was_optimal);
818
	ir_timer_free(timer);
Sebastian Hack's avatar
Sebastian Hack committed
819

Christian Würdig's avatar
Christian Würdig committed
820
	if (dump_flags & DUMP_AFTER) {
Matthias Braun's avatar
Matthias Braun committed
821
822
		FILE *f = my_open(cenv, "", "-after.vcg");
		be_dump_ifg_co(f, co, style_flags & CO_IFG_DUMP_LABELS, style_flags & CO_IFG_DUMP_COLORS);
Sebastian Hack's avatar
Sebastian Hack committed
823
824
825
		fclose(f);
	}

Matthias Braun's avatar
Matthias Braun committed
826
	co_complete_stats_t after;
827
828
	co_complete_stats(co, &after);

Christian Würdig's avatar
Christian Würdig committed
829
	if (do_stats) {
Matthias Braun's avatar
Matthias Braun committed
830
831
		unsigned long long optimizable_costs = after.max_costs - after.inevit_costs;
		unsigned long long evitable          = after.costs     - after.inevit_costs;
Sebastian Hack's avatar
Sebastian Hack committed