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

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
25
26
27
28
29
30
 * @file
 * @brief       Copy minimization driver.
 * @author      Daniel Grund
 * @date        12.04.2005
 * @version     $Id$
 *
 * Main file for the optimization reducing the copies needed for:
 * - Phi coalescing
 * - Register-constrained nodes
 * - Two-address code instructions
31
 */
32
#include "config.h"
33

Sebastian Hack's avatar
Sebastian Hack committed
34
#include "execfreq.h"
35
36
37
#include "xmalloc.h"
#include "debug.h"
#include "pmap.h"
Matthias Braun's avatar
Matthias Braun committed
38
#include "raw_bitset.h"
Michael Beck's avatar
Michael Beck committed
39
#include "irnode.h"
40
41
#include "irgraph.h"
#include "irgwalk.h"
Sebastian Hack's avatar
Sebastian Hack committed
42
#include "irprog.h"
Daniel Grund's avatar
Daniel Grund committed
43
#include "irloop_t.h"
44
#include "iredges_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
45
46
#include "irbitset.h"
#include "irphase_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
47
48
#include "irprintf_t.h"

49
#include "bemodule.h"
50
#include "bearch.h"
51
#include "benode.h"
Daniel Grund's avatar
Daniel Grund committed
52
#include "beutil.h"
53
#include "beifg.h"
54
#include "beintlive_t.h"
55
#include "becopyopt_t.h"
56
#include "becopystat.h"
Sebastian Hack's avatar
Sebastian Hack committed
57
58
#include "belive_t.h"
#include "beinsn_t.h"
59
#include "besched.h"
60
#include "bestatevent.h"
61
#include "beirg.h"
62
#include "error.h"
Daniel Grund's avatar
Daniel Grund committed
63

Matthias Braun's avatar
Matthias Braun committed
64
65
#include "lc_opts.h"
#include "lc_opts_enum.h"
66

Sebastian Hack's avatar
Sebastian Hack committed
67
68
69
70
71
72
73
74
75
#define DUMP_BEFORE 1
#define DUMP_AFTER  2
#define DUMP_APPEL  4
#define DUMP_ALL    2 * DUMP_APPEL - 1

#define COST_FUNC_FREQ     1
#define COST_FUNC_LOOP     2
#define COST_FUNC_ALL_ONE  3

Christian Würdig's avatar
Christian Würdig committed
76
77
static unsigned   dump_flags  = 0;
static unsigned   style_flags = 0;
78
static int        do_stats    = 0;
Sebastian Hack's avatar
Sebastian Hack committed
79
static cost_fct_t cost_func   = co_get_costs_exec_freq;
Christian Würdig's avatar
Christian Würdig committed
80
static int        improve     = 1;
Sebastian Hack's avatar
Sebastian Hack committed
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

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
99
100
typedef int (*opt_funcptr)(void);

Sebastian Hack's avatar
Sebastian Hack committed
101
static const lc_opt_enum_func_ptr_items_t cost_func_items[] = {
Matthias Braun's avatar
Matthias Braun committed
102
103
104
105
	{ "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
106
107
108
109
110
111
112
113
114
115
116
};

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
117
	(opt_funcptr*) &cost_func, cost_func_items
Sebastian Hack's avatar
Sebastian Hack committed
118
119
120
};

static const lc_opt_table_entry_t options[] = {
121
	LC_OPT_ENT_ENUM_FUNC_PTR ("cost",    "select a cost function",                                  &cost_func_var),
Sebastian Hack's avatar
Sebastian Hack committed
122
123
124
	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),
yb9976's avatar
yb9976 committed
125
	LC_OPT_ENT_BOOL          ("improve", "run heur1 before if algo can exploit start solutions",    &improve),
126
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
127
};
Sebastian Hack's avatar
Sebastian Hack committed
128

129
130
131
132
133
134
135
136
137
138
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
139
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyopt)
yb9976's avatar
yb9976 committed
140
void be_init_copyopt(void)
Sebastian Hack's avatar
Sebastian Hack committed
141
{
142
143
144
145
	lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
	lc_opt_entry_t *ra_grp = lc_opt_get_grp(be_grp, "ra");
	lc_opt_entry_t *chordal_grp = lc_opt_get_grp(ra_grp, "chordal");
	lc_opt_entry_t *co_grp = lc_opt_get_grp(chordal_grp, "co");
Sebastian Hack's avatar
Sebastian Hack committed
146

147
	lc_opt_add_table(co_grp, options);
148
149
150
151
152
153
154
155
156
157
	be_add_module_list_opt(co_grp, "algo", "select copy optimization algo",
		                       &copyopts, (void**) &selected_copyopt);
}

static int void_algo(copy_opt_t *co)
{
	(void) co;
	return 0;
}

Matthias Braun's avatar
Matthias Braun committed
158
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copynone)
159
160
161
162
163
164
165
void be_init_copynone(void)
{
	static co_algo_info copyheur = {
		void_algo, 0
	};

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

Daniel Grund's avatar
Daniel Grund committed
168
#undef QUICK_AND_DIRTY_HACK
Daniel Grund's avatar
Daniel Grund committed
169

170
171
static int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b)
{
Christian Würdig's avatar
Christian Würdig committed
172
	if (env->ifg)
173
		return be_ifg_connected(env->ifg, a, b);
174
175
176
177
	else {
		be_lv_t *lv = be_get_irg_liveness(env->irg);
		return be_values_interfere(lv, a, b);
	}
178
179
180
}


Daniel Grund's avatar
Daniel Grund committed
181
182
183
184
185
186
187
188
189
/******************************************************************************
    _____                           _
   / ____|                         | |
  | |  __  ___ _ __   ___ _ __ __ _| |
  | | |_ |/ _ \ '_ \ / _ \ '__/ _` | |
  | |__| |  __/ | | |  __/ | | (_| | |
   \_____|\___|_| |_|\___|_|  \__,_|_|

 ******************************************************************************/
Daniel Grund's avatar
Daniel Grund committed
190

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

Sebastian Hack's avatar
Sebastian Hack committed
193

Sebastian Hack's avatar
Sebastian Hack committed
194
195
copy_opt_t *new_copy_opt(be_chordal_env_t *chordal_env, cost_fct_t get_costs)
{
Daniel Grund's avatar
Daniel Grund committed
196
	const char *s1, *s2, *s3;
197
	size_t len;
Daniel Grund's avatar
Daniel Grund committed
198
199
	copy_opt_t *co;

200
	FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
Daniel Grund's avatar
Daniel Grund committed
201

202
	co = XMALLOCZ(copy_opt_t);
Daniel Grund's avatar
Daniel Grund committed
203
204
205
206
207
	co->cenv      = chordal_env;
	co->irg       = chordal_env->irg;
	co->cls       = chordal_env->cls;
	co->get_costs = get_costs;

208
	s1 = get_irp_name();
Daniel Grund's avatar
Daniel Grund committed
209
210
211
	s2 = get_entity_name(get_irg_entity(co->irg));
	s3 = chordal_env->cls->name;
	len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
212
	co->name = XMALLOCN(char, len);
Daniel Grund's avatar
Daniel Grund committed
213
214
215
216
217
	snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);

	return co;
}

218
219
void free_copy_opt(copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
220
	xfree(co->name);
Daniel Grund's avatar
Daniel Grund committed
221
	free(co);
Daniel Grund's avatar
Daniel Grund committed
222
223
}

224
225
226
227
228
229
/**
 * Checks if a node is optimizable, viz. has something to do with coalescing
 * @param irn  The irn to check
 */
static int co_is_optimizable_root(ir_node *irn)
{
Matthias Braun's avatar
Matthias Braun committed
230
	const arch_register_req_t *req;
Daniel Grund's avatar
Daniel Grund committed
231

232
	if (arch_irn_is_ignore(irn))
Daniel Grund's avatar
Daniel Grund committed
233
234
		return 0;

235
236
237
	if (is_Reg_Phi(irn) || is_Perm_Proj(irn))
		return 1;

238
	req = arch_get_register_req_out(irn);
239
	if (is_2addr_code(req))
Daniel Grund's avatar
Daniel Grund committed
240
241
242
243
244
		return 1;

	return 0;
}

245
246
int co_get_costs_loop_depth(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos)
{
Daniel Grund's avatar
Daniel Grund committed
247
248
249
	int cost = 0;
	ir_loop *loop;
	ir_node *root_block = get_nodes_block(root);
250
251
	(void) co;
	(void) arg;
Daniel Grund's avatar
Daniel Grund committed
252
253
254
255
256
257
258
259
260
261
262
263

	if (is_Phi(root)) {
		/* for phis the copies are placed in the corresponding pred-block */
		loop = get_irn_loop(get_Block_cfgpred_block(root_block, pos));
	} else {
		/* a perm places the copy in the same block as it resides */
		loop = get_irn_loop(root_block);
	}
	if (loop) {
		int d = get_loop_depth(loop);
		cost = d*d;
	}
264
	return 1+cost;
Daniel Grund's avatar
Daniel Grund committed
265
266
}

267
268
int co_get_costs_exec_freq(const copy_opt_t *co, ir_node *root, ir_node* arg, int pos)
{
269
	int res;
Sebastian Hack's avatar
Sebastian Hack committed
270
271
	ir_node *root_bl = get_nodes_block(root);
	ir_node *copy_bl = is_Phi(root) ? get_Block_cfgpred_block(root_bl, pos) : root_bl;
272
	ir_exec_freq *exec_freq = be_get_irg_exec_freq(co->cenv->irg);
273
	(void) arg;
274
	res = get_block_execfreq_ulong(exec_freq, copy_bl);
275
276
277

	/* don't allow values smaller than one. */
	return res < 1 ? 1 : res;
Sebastian Hack's avatar
Sebastian Hack committed
278
279
280
}


281
282
int co_get_costs_all_one(const copy_opt_t *co, ir_node *root, ir_node *arg, int pos)
{
283
284
285
286
	(void) co;
	(void) root;
	(void) arg;
	(void) pos;
Daniel Grund's avatar
Daniel Grund committed
287
288
289
290
291
292
293
294
295
296
297
298
299
300
	return 1;
}

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

Daniel Grund's avatar
Daniel Grund committed
301
/**
Daniel Grund's avatar
Daniel Grund committed
302
303
 * 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
304
 */
305
306
static int ou_max_ind_set_costs(unit_t *ou)
{
307
	be_chordal_env_t *chordal_env = ou->co->cenv;
Daniel Grund's avatar
Daniel Grund committed
308
309
	ir_node **safe, **unsafe;
	int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
Daniel Grund's avatar
Daniel Grund committed
310
	bitset_t *curr;
311
	size_t  pos;
312
	int curr_weight, best_weight = 0;
Daniel Grund's avatar
Daniel Grund committed
313
314
315
316
317

	/* assign the nodes into two groups.
	 * safe: node has no interference, hence it is in every max stable set.
	 * unsafe: node has an interference
	 */
318
319
320
321
322
	safe         = ALLOCAN(ir_node*, ou->node_count - 1);
	safe_costs   = 0;
	safe_count   = 0;
	unsafe       = ALLOCAN(ir_node*, ou->node_count - 1);
	unsafe_costs = ALLOCAN(int,      ou->node_count - 1);
Daniel Grund's avatar
Daniel Grund committed
323
	unsafe_count = 0;
324
	for (i=1; i<ou->node_count; ++i) {
Daniel Grund's avatar
Daniel Grund committed
325
		int is_safe = 1;
326
		for (o=1; o<ou->node_count; ++o) {
Daniel Grund's avatar
Daniel Grund committed
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
			if (i==o)
				continue;
			if (nodes_interfere(chordal_env, ou->nodes[i], ou->nodes[o])) {
				unsafe_costs[unsafe_count] = ou->costs[i];
				unsafe[unsafe_count] = ou->nodes[i];
				++unsafe_count;
				is_safe = 0;
				break;
			}
		}
		if (is_safe) {
			safe_costs += ou->costs[i];
			safe[safe_count++] = ou->nodes[i];
		}
	}
Daniel Grund's avatar
Daniel Grund committed
342
343


344
345
346
	/* now compute the best set out of the unsafe nodes*/
	if (unsafe_count > MIS_HEUR_TRIGGER) {
		bitset_t *best = bitset_alloca(unsafe_count);
347
		/* Heuristic: Greedy trial and error form index 0 to unsafe_count-1 */
348
349
350
351
352
353
354
355
		for (i=0; i<unsafe_count; ++i) {
			bitset_set(best, i);
			/* check if it is a stable set */
			for (o=bitset_next_set(best, 0); o!=-1 && o<i; o=bitset_next_set(best, o+1))
				if (nodes_interfere(chordal_env, unsafe[i], unsafe[o])) {
					bitset_clear(best, i); /* clear the bit and try next one */
					break;
				}
Daniel Grund's avatar
Daniel Grund committed
356
		}
357
358
359
360
361
362
363
		/* compute the weight */
		bitset_foreach(best, pos)
			best_weight += unsafe_costs[pos];
	} else {
		/* Exact Algorithm: Brute force */
		curr = bitset_alloca(unsafe_count);
		bitset_set_all(curr);
364
		while (bitset_popcount(curr) != 0) {
365
366
367
368
369
370
371
			/* check if curr is a stable set */
			for (i=bitset_next_set(curr, 0); i!=-1; i=bitset_next_set(curr, i+1))
				for (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) */
						if (nodes_interfere(chordal_env, unsafe[i], unsafe[o]))
							goto no_stable_set;

			/* if we arrive here, we have a stable set */
372
			/* compute the weight of the stable set*/
373
374
375
376
377
378
379
380
			curr_weight = 0;
			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
381

382
383
384
	no_stable_set:
			bitset_minus1(curr);
		}
Daniel Grund's avatar
Daniel Grund committed
385
	}
Daniel Grund's avatar
Daniel Grund committed
386
387

	return safe_costs+best_weight;
Daniel Grund's avatar
Daniel Grund committed
388
}
389

390
391
static void co_collect_units(ir_node *irn, void *env)
{
392
	const arch_register_req_t *req;
393
	copy_opt_t                *co  = (copy_opt_t*)env;
394
	unit_t *unit;
Daniel Grund's avatar
Daniel Grund committed
395

396
397
398
	if (get_irn_mode(irn) == mode_T)
		return;
	req = arch_get_register_req_out(irn);
399
	if (req->cls != co->cls)
400
		return;
401
	if (!co_is_optimizable_root(irn))
402
		return;
403

404
	/* Init a new unit */
405
	unit = XMALLOCZ(unit_t);
406
	unit->co = co;
407
	unit->node_count = 1;
408
409
	INIT_LIST_HEAD(&unit->queue);

410
411
412
413
414
415
	/* Phi with some/all of its arguments */
	if (is_Reg_Phi(irn)) {
		int i, arity;

		/* init */
		arity = get_irn_arity(irn);
416
417
		unit->nodes = XMALLOCN(ir_node*, arity + 1);
		unit->costs = XMALLOCN(int,      arity + 1);
418
419
420
		unit->nodes[0] = irn;

		/* fill */
421
		for (i=0; i<arity; ++i) {
422
423
			int o, arg_pos;
			ir_node *arg = get_irn_n(irn, i);
424

425
			assert(arch_get_irn_reg_class_out(arg) == co->cls && "Argument not in same register class.");
426
			if (arg == irn)
427
				continue;
428
			if (nodes_interfere(co->cenv, irn, arg)) {
Sebastian Hack's avatar
Sebastian Hack committed
429
				unit->inevitable_costs += co->get_costs(co, irn, arg, i);
430
431
432
433
				continue;
			}

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

436
437
			if (arch_irn_is_ignore(arg))
				continue;
438

439
440
441
442
443
444
			/* Check if arg has occurred at a prior position in the arg/list */
			arg_pos = 0;
			for (o=1; o<unit->node_count; ++o) {
				if (unit->nodes[o] == arg) {
					arg_pos = o;
					break;
445
				}
446
			}
447
448
449
450
451
452
453
454
455
456

			if (!arg_pos) { /* a new argument */
				/* insert node, set costs */
				unit->nodes[unit->node_count] = arg;
				unit->costs[unit->node_count] = co->get_costs(co, irn, arg, i);
				unit->node_count++;
			} else { /* arg has occurred before in same phi */
				/* increase costs for existing arg */
				unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
			}
Daniel Grund's avatar
Daniel Grund committed
457
		}
458
459
		unit->nodes = XREALLOC(unit->nodes, ir_node*, unit->node_count);
		unit->costs = XREALLOC(unit->costs, int,      unit->node_count);
460
	} else if (is_Perm_Proj(irn)) {
461
		/* Proj of a perm with corresponding arg */
Daniel Grund's avatar
Daniel Grund committed
462
		assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
463
464
		unit->nodes = XMALLOCN(ir_node*, 2);
		unit->costs = XMALLOCN(int,      2);
465
466
		unit->node_count = 2;
		unit->nodes[0] = irn;
Daniel Grund's avatar
Daniel Grund committed
467
		unit->nodes[1] = get_Perm_src(irn);
Sebastian Hack's avatar
Sebastian Hack committed
468
		unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
Matthias Braun's avatar
Matthias Braun committed
469
470
471
	} else {
		/* Src == Tgt of a 2-addr-code instruction */
		if (is_2addr_code(req)) {
472
473
474
475
476
477
478
			const unsigned other = req->other_same;
			int            count = 0;
			int            i;

			for (i = 0; (1U << i) <= other; ++i) {
				if (other & (1U << i)) {
					ir_node *o  = get_irn_n(skip_Proj(irn), i);
479
480
481
482
483
					if (arch_irn_is_ignore(o))
						continue;
					if (nodes_interfere(co->cenv, irn, o))
						continue;
					++count;
484
485
486
				}
			}

487
488
489
			if (count != 0) {
				int k = 0;
				++count;
490
491
				unit->nodes = XMALLOCN(ir_node*, count);
				unit->costs = XMALLOCN(int,      count);
492
				unit->node_count = count;
493
494
495
496
497
				unit->nodes[k++] = irn;

				for (i = 0; 1U << i <= other; ++i) {
					if (other & (1U << i)) {
						ir_node *o  = get_irn_n(skip_Proj(irn), i);
498
						if (!arch_irn_is_ignore(o) &&
499
500
501
502
503
								!nodes_interfere(co->cenv, irn, o)) {
							unit->nodes[k] = o;
							unit->costs[k] = co->get_costs(co, irn, o, -1);
							++k;
						}
504
505
					}
				}
Matthias Braun's avatar
Matthias Braun committed
506
507
508
			}
		} else {
			assert(0 && "This is not an optimizable node!");
509
		}
Matthias Braun's avatar
Matthias Braun committed
510
	}
511

512
	/* Insert the new unit at a position according to its costs */
513
	if (unit->node_count > 1) {
514
515
		int i;
		struct list_head *tmp;
516

517
		/* Determine the maximum costs this unit can cause: all_nodes_cost */
518
		for (i=1; i<unit->node_count; ++i) {
519
520
521
			unit->sort_key = MAX(unit->sort_key, unit->costs[i]);
			unit->all_nodes_costs += unit->costs[i];
		}
522

523
524
525
526
527
528
529
		/* Determine the minimal costs this unit will cause: min_nodes_costs */
		unit->min_nodes_costs += unit->all_nodes_costs - ou_max_ind_set_costs(unit);
		/* Insert the new ou according to its sort_key */
		tmp = &co->units;
		while (tmp->next != &co->units && list_entry_units(tmp->next)->sort_key > unit->sort_key)
			tmp = tmp->next;
		list_add(&unit->units, tmp);
530
531
	} else {
		free(unit);
532
	}
533
534
}

Daniel Grund's avatar
Daniel Grund committed
535
536
#ifdef QUICK_AND_DIRTY_HACK

537
538
static int compare_ous(const void *k1, const void *k2)
{
Daniel Grund's avatar
Daniel Grund committed
539
540
541
542
543
544
545
546
	const unit_t *u1 = *((const unit_t **) k1);
	const unit_t *u2 = *((const unit_t **) k2);
	int i, o, u1_has_constr, u2_has_constr;
	arch_register_req_t req;

	/* Units with constraints come first */
	u1_has_constr = 0;
	for (i=0; i<u1->node_count; ++i) {
547
		arch_get_register_req_out(&req, u1->nodes[i]);
Daniel Grund's avatar
Daniel Grund committed
548
549
550
551
552
553
554
555
		if (arch_register_req_is(&req, limited)) {
			u1_has_constr = 1;
			break;
		}
	}

	u2_has_constr = 0;
	for (i=0; i<u2->node_count; ++i) {
556
		arch_get_register_req_out(&req, u2->nodes[i]);
Daniel Grund's avatar
Daniel Grund committed
557
558
559
560
561
562
563
564
565
566
		if (arch_register_req_is(&req, limited)) {
			u2_has_constr = 1;
			break;
		}
	}

	if (u1_has_constr != u2_has_constr)
		return u2_has_constr - u1_has_constr;

	/* Now check, whether the two units are connected */
Daniel Grund's avatar
Daniel Grund committed
567
#if 0
Daniel Grund's avatar
Daniel Grund committed
568
569
570
571
	for (i=0; i<u1->node_count; ++i)
		for (o=0; o<u2->node_count; ++o)
			if (u1->nodes[i] == u2->nodes[o])
				return 0;
Daniel Grund's avatar
Daniel Grund committed
572
#endif
Daniel Grund's avatar
Daniel Grund committed
573
574
575
576
577
578
579
580
581

	/* After all, the sort key decides. Greater keys come first. */
	return u2->sort_key - u1->sort_key;

}

/**
 * Sort the ou's according to constraints and their sort_key
 */
582
583
static void co_sort_units(copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
584
585
	int i, count = 0, costs;
	unit_t *ou, **ous;
Daniel Grund's avatar
Daniel Grund committed
586
587
588
589

	/* get the number of ous, remove them form the list and fill the array */
	list_for_each_entry(unit_t, ou, &co->units, units)
		count++;
590
	ous = ALLOCAN(unit_t, count);
Daniel Grund's avatar
Daniel Grund committed
591

Daniel Grund's avatar
Daniel Grund committed
592
593
	costs = co_get_max_copy_costs(co);

Daniel Grund's avatar
Daniel Grund committed
594
	i = 0;
Daniel Grund's avatar
Daniel Grund committed
595
	list_for_each_entry(unit_t, ou, &co->units, units)
Daniel Grund's avatar
Daniel Grund committed
596
597
		ous[i++] = ou;

Daniel Grund's avatar
Daniel Grund committed
598
599
600
601
602
603
	INIT_LIST_HEAD(&co->units);

	assert(count == i && list_empty(&co->units));

	for (i=0; i<count; ++i)
		ir_printf("%+F\n", ous[i]->nodes[0]);
Daniel Grund's avatar
Daniel Grund committed
604
605
606

	qsort(ous, count, sizeof(*ous), compare_ous);

Daniel Grund's avatar
Daniel Grund committed
607
608
609
610
	ir_printf("\n\n");
	for (i=0; i<count; ++i)
		ir_printf("%+F\n", ous[i]->nodes[0]);

Daniel Grund's avatar
Daniel Grund committed
611
612
613
	/* reinsert into list in correct order */
	for (i=0; i<count; ++i)
		list_add_tail(&ous[i]->units, &co->units);
Daniel Grund's avatar
Daniel Grund committed
614
615

	assert(costs == co_get_max_copy_costs(co));
Daniel Grund's avatar
Daniel Grund committed
616
617
618
}
#endif

619
620
void co_build_ou_structure(copy_opt_t *co)
{
621
	DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
622
	INIT_LIST_HEAD(&co->units);
623
	irg_walk_graph(co->irg, co_collect_units, NULL, co);
Daniel Grund's avatar
Daniel Grund committed
624
625
626
#ifdef QUICK_AND_DIRTY_HACK
	co_sort_units(co);
#endif
627
628
}

629
630
void co_free_ou_structure(copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
631
	unit_t *curr, *tmp;
Daniel Grund's avatar
Daniel Grund committed
632
	ASSERT_OU_AVAIL(co);
Daniel Grund's avatar
Daniel Grund committed
633
	list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
Michael Beck's avatar
Michael Beck committed
634
		xfree(curr->nodes);
635
		xfree(curr->costs);
Michael Beck's avatar
Michael Beck committed
636
		xfree(curr);
637
	}
Daniel Grund's avatar
Daniel Grund committed
638
	co->units.next = NULL;
639
640
}

Daniel Grund's avatar
Daniel Grund committed
641
/* co_solve_heuristic() is implemented in becopyheur.c */
Daniel Grund's avatar
Daniel Grund committed
642

643
644
int co_get_max_copy_costs(const copy_opt_t *co)
{
645
646
647
	int i, res = 0;
	unit_t *curr;

Daniel Grund's avatar
Daniel Grund committed
648
649
	ASSERT_OU_AVAIL(co);

650
651
652
653
654
655
656
657
	list_for_each_entry(unit_t, curr, &co->units, units) {
		res += curr->inevitable_costs;
		for (i=1; i<curr->node_count; ++i)
			res += curr->costs[i];
	}
	return res;
}

658
659
int co_get_inevit_copy_costs(const copy_opt_t *co)
{
660
661
662
	int res = 0;
	unit_t *curr;

Daniel Grund's avatar
Daniel Grund committed
663
664
	ASSERT_OU_AVAIL(co);

665
666
667
668
669
	list_for_each_entry(unit_t, curr, &co->units, units)
		res += curr->inevitable_costs;
	return res;
}

670
671
int co_get_copy_costs(const copy_opt_t *co)
{
672
673
	int i, res = 0;
	unit_t *curr;
674

Daniel Grund's avatar
Daniel Grund committed
675
676
	ASSERT_OU_AVAIL(co);

677
	list_for_each_entry(unit_t, curr, &co->units, units) {
678
		int root_col = get_irn_col(curr->nodes[0]);
Daniel Grund's avatar
Daniel Grund committed
679
		DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
680
		res += curr->inevitable_costs;
Daniel Grund's avatar
Daniel Grund committed
681
		for (i=1; i<curr->node_count; ++i) {
682
			int arg_col = get_irn_col(curr->nodes[i]);
Daniel Grund's avatar
Daniel Grund committed
683
			if (root_col != arg_col) {
Daniel Grund's avatar
Daniel Grund committed
684
				DBG((dbg, LEVEL_1, "  %3d for arg %+F color %d\n", curr->costs[i], curr->nodes[i], arg_col));
Daniel Grund's avatar
Daniel Grund committed
685
				res += curr->costs[i];
686
			}
Daniel Grund's avatar
Daniel Grund committed
687
		}
688
689
690
691
	}
	return res;
}

692
693
int co_get_lower_bound(const copy_opt_t *co)
{
694
695
	int res = 0;
	unit_t *curr;
Daniel Grund's avatar
Daniel Grund committed
696
697
698

	ASSERT_OU_AVAIL(co);

699
	list_for_each_entry(unit_t, curr, &co->units, units)
700
		res += curr->inevitable_costs + curr->min_nodes_costs;
701
702
	return res;
}
Daniel Grund's avatar
Daniel Grund committed
703

704
705
706
707
708
709
710
711
712
713
714
715
716
void co_complete_stats(const copy_opt_t *co, co_complete_stats_t *stat)
{
	bitset_t *seen = bitset_irg_malloc(co->irg);
	affinity_node_t *an;

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

	/* count affinity edges. */
	co_gs_foreach_aff_node(co, an) {
		neighb_t *neigh;
		stat->aff_nodes += 1;
		bitset_add_irn(seen, an->irn);
		co_gs_foreach_neighb(an, neigh) {
717
			if (!bitset_contains_irn(seen, neigh->irn)) {
718
719
720
				stat->aff_edges += 1;
				stat->max_costs += neigh->costs;

721
				if (get_irn_col(an->irn) != get_irn_col(neigh->irn)) {
722
723
724
725
					stat->costs += neigh->costs;
					stat->unsatisfied_edges += 1;
				}

726
				if (nodes_interfere(co->cenv, an->irn, neigh->irn)) {
727
728
729
730
731
732
733
734
735
736
737
					stat->aff_int += 1;
					stat->inevit_costs += neigh->costs;
				}

			}
		}
	}

	bitset_free(seen);
}

Daniel Grund's avatar
Daniel Grund committed
738
739
740
741
742
743
744
745
746
747
748
/******************************************************************************
   _____                 _        _____ _
  / ____|               | |      / ____| |
 | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
  \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
                  | |                                       __/ |
                  |_|                                      |___/
 ******************************************************************************/

749
750
static int compare_affinity_node_t(const void *k1, const void *k2, size_t size)
{
751
752
	const affinity_node_t *n1 = (const affinity_node_t*)k1;
	const affinity_node_t *n2 = (const affinity_node_t*)k2;
753
	(void) size;
Daniel Grund's avatar
Daniel Grund committed
754
755
756
757

	return (n1->irn != n2->irn);
}

758
759
static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
{
Daniel Grund's avatar
Daniel Grund committed
760
	affinity_node_t new_node, *node;
Christoph Mallon's avatar
Christoph Mallon committed
761
	neighb_t        *nbr;
762
	int             allocnew = 1;
Daniel Grund's avatar
Daniel Grund committed
763
764

	new_node.irn        = n1;
Daniel Grund's avatar
Daniel Grund committed
765
	new_node.degree     = 0;
Daniel Grund's avatar
Daniel Grund committed
766
	new_node.neighbours = NULL;
767
	node = (affinity_node_t*)set_insert(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
Daniel Grund's avatar
Daniel Grund committed
768
769
770
771
772
773
774
775
776

	for (nbr = node->neighbours; nbr; nbr = nbr->next)
		if (nbr->irn == n2) {
			allocnew = 0;
			break;
		}

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

Daniel Grund's avatar
Daniel Grund committed
782
		node->neighbours = nbr;
Daniel Grund's avatar
Daniel Grund committed
783
		node->degree++;
Daniel Grund's avatar
Daniel Grund committed
784
785
786
787
788
789
	}

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

790
791
static inline void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs)
{
Daniel Grund's avatar
Daniel Grund committed
792
793
794
795
796
797
	if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
		add_edge(co, n1, n2, costs);
		add_edge(co, n2, n1, costs);
	}
}

798
799
static void build_graph_walker(ir_node *irn, void *env)
{
800
	const arch_register_req_t *req;
801
	copy_opt_t                *co  = (copy_opt_t*)env;
Daniel Grund's avatar
Daniel Grund committed
802
803
	int pos, max;

804
805
806
	if (get_irn_mode(irn) == mode_T)
		return;
	req = arch_get_register_req_out(irn);
807
	if (req->cls != co->cls || arch_irn_is_ignore(irn))
Daniel Grund's avatar
Daniel Grund committed
808
809
		return;

810
	if (is_Reg_Phi(irn)) { /* Phis */
Daniel Grund's avatar
Daniel Grund committed
811
812
		for (pos=0, max=get_irn_arity(irn); pos<max; ++pos) {
			ir_node *arg = get_irn_n(irn, pos);
Sebastian Hack's avatar
Sebastian Hack committed
813
			add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
Daniel Grund's avatar
Daniel Grund committed
814
		}
815
	} else if (is_Perm_Proj(irn)) { /* Perms */
Daniel Grund's avatar
Daniel Grund committed
816
		ir_node *arg = get_Perm_src(irn);
Sebastian Hack's avatar
Sebastian Hack committed
817
		add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
818
	} else { /* 2-address code */
Matthias Braun's avatar
Matthias Braun committed
819
		if (is_2addr_code(req)) {
820
821
822
823
824
825
			const unsigned other = req->other_same;
			int i;

			for (i = 0; 1U << i <= other; ++i) {
				if (other & (1U << i)) {
					ir_node *other = get_irn_n(skip_Proj(irn), i);
826
					if (!arch_irn_is_ignore(other))
827
828
						add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
				}
829
			}
Matthias Braun's avatar
Matthias Braun committed
830
831
		}
	}
Daniel Grund's avatar
Daniel Grund committed
832
833
}

834
835
void co_build_graph_structure(copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
836
	obstack_init(&co->obst);
Daniel Grund's avatar
Daniel Grund committed
837
	co->nodes = new_set(compare_affinity_node_t, 32);
Daniel Grund's avatar
Daniel Grund committed
838
839
840
841

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

842
843
void co_free_graph_structure(copy_opt_t *co)
{
Daniel Grund's avatar
Daniel Grund committed
844
845
	ASSERT_GS_AVAIL(co);

Daniel Grund's avatar
Daniel Grund committed
846
847
	del_set(co->nodes);
	obstack_free(&co->obst, NULL);
Daniel Grund's avatar
Daniel Grund committed
848
	co->nodes = NULL;
Daniel Grund's avatar
Daniel Grund committed
849
850
}

851
852
int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn)
{
Daniel Grund's avatar
Daniel Grund committed
853
854
855
	affinity_node_t new_node, *n;

	ASSERT_GS_AVAIL(co);
Daniel Grund's avatar
Daniel Grund committed
856

857
	new_node.irn = irn;
858
	n = (affinity_node_t*)set_find(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
859
	if (n) {
Daniel Grund's avatar
Daniel Grund committed
860
		return (n->degree > 0);
861
862
	} else
		return 0;
Daniel Grund's avatar
Daniel Grund committed
863
}
Sebastian Hack's avatar
Sebastian Hack committed
864

Sebastian Hack's avatar
Sebastian Hack committed
865
866
867
868
869
870
871
872
873
874
static int co_dump_appel_disjoint_constraints(const copy_opt_t *co, ir_node *a, ir_node *b)
{
	ir_node *nodes[]  = { a, b };
	bitset_t *constr[] = { NULL, NULL };
	int j;

	constr[0] = bitset_alloca(co->cls->n_regs);
	constr[1] = bitset_alloca(co->cls->n_regs);

	for (j = 0; j < 2; ++j) {
875
		const arch_register_req_t *req = arch_get_register_req_out(nodes[j]);
876
		if (arch_register_req_is(req, limited))
Sebastian Hack's avatar
Sebastian Hack committed
877
878
879
880
881
882
883
884
885
			rbitset_copy_to_bitset(req->limited, constr[j]);
		else
			bitset_set_all(constr[j]);

	}

	return !bitset_intersect(constr[0], constr[1]);
}

Sebastian Hack's avatar
Sebastian Hack committed
886
887
void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
{
888
889
890
	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);
891
892
	ir_graph *irg       = co->irg;
	be_irg_t *birg      = be_birg_from_irg(irg);
Sebastian Hack's avatar
Sebastian Hack committed
893
894

	ir_node *irn;
895
896
	nodes_iter_t it;
	neighbours_iter_t nit;
897
	int n, n_regs;
898
	unsigned i;
Sebastian Hack's avatar
Sebastian Hack committed
899
900

	n_regs = 0;
901
	for (i = 0; i < co->cls->n_regs; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
902
		const arch_register_t *reg = &co->cls->regs[i];
903
904
905
906
907
		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
908
909
910
911
912
913
	}

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

Sebastian Hack's avatar
Sebastian Hack committed
915
	n = n_regs;
916
	be_ifg_foreach_node(ifg, &it, irn) {
917
918
919
		if (arch_irn_is_ignore(irn))
			continue;
		node_map[get_irn_idx(irn)] = n++;
Sebastian Hack's avatar
Sebastian Hack committed
920
921
	}

Sebastian Hack's avatar
Sebastian Hack committed
922
	fprintf(f, "%d %d\n", n, n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
923

924
	be_ifg_foreach_node(ifg, &it, irn) {
925
		if (!arch_irn_is_ignore(irn)) {
926
927
928
929
			int idx                        = node_map[get_irn_idx(irn)];
			affinity_node_t           *a   = get_affinity_info(co, irn);
			const arch_register_req_t *req = arch_get_register_req_out(irn);
			ir_node                   *adj;
Sebastian Hack's avatar
Sebastian Hack committed
930

931
932
933
			if (arch_register_req_is(req, limited)) {
				for (i = 0; i < co->cls->n_regs; ++i) {
					if (!rbitset_is_set(req->limited, i) && color_map[i] >= 0)
Sebastian Hack's avatar
Sebastian Hack committed
934
						fprintf(f, "%d %d -1\n", color_map[i], idx);
Matthias Braun's avatar
Matthias Braun committed
935
				}
Sebastian Hack's avatar
Sebastian Hack committed
936
937
			}

938
			be_ifg_foreach_neighbour(ifg, &nit, irn, adj) {
939
				if (!arch_irn_is_ignore(adj) &&
940
						!co_dump_appel_disjoint_constraints(co, irn, adj)) {
Sebastian Hack's avatar
Sebastian Hack committed
941
					int adj_idx = node_map[get_irn_idx(adj)];
942
					if (idx < adj_idx)
Sebastian Hack's avatar
Sebastian Hack committed
943
944
945
946
						fprintf(f, "%d %d -1\n", idx, adj_idx);
				}
			}

947
			if (a) {
Sebastian Hack's avatar
Sebastian Hack committed
948
949
950
				neighb_t *n;

				co_gs_foreach_neighb(a, n) {
951
					if (!arch_irn_is_ignore(n->irn)) {
Sebastian Hack's avatar
Sebastian Hack committed
952
						int n_idx = node_map[get_irn_idx(n->irn)];
953
						if (idx < n_idx)
954
							fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
Sebastian Hack's avatar
Sebastian Hack committed
955
956
957
958
959
					}
				}
			}
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
960
961

	xfree(node_map);
Sebastian Hack's avatar
Sebastian Hack committed
962
963
}

Sebastian Hack's avatar
Sebastian Hack committed
964
/*
Sebastian Hack's avatar
Sebastian Hack committed
965
966
967
968
969
970
	 ___ _____ ____   ____   ___ _____   ____                        _
	|_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
	 | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
	 | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
	|___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
	                                                          |_|            |___/
Sebastian Hack's avatar
Sebastian Hack committed
971
972
*/

973
static const char *get_dot_color_name(size_t col)
Sebastian Hack's avatar
Sebastian Hack committed
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
{
	static const char *names[] = {
		"blue",
		"red",
		"green",
		"yellow",
		"cyan",
		"magenta",
		"orange",
		"chocolate",
		"beige",
		"navy",
		"darkgreen",
		"darkred",
		"lightPink",
		"chartreuse",
		"lightskyblue",
		"linen",
		"pink",
		"lightslateblue",
		"mintcream",
		"red",
		"darkolivegreen",
		"mediumblue",
		"mistyrose",
		"salmon",
		"darkseagreen",