becopyopt.c 31.8 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"
Sebastian Hack's avatar
Sebastian Hack committed
51
#include "benode_t.h"
Daniel Grund's avatar
Daniel Grund committed
52
#include "beutil.h"
Daniel Grund's avatar
Daniel Grund committed
53
#include "beifg_t.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
78
static unsigned   dump_flags  = 0;
static unsigned   style_flags = 0;
static unsigned   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);
}

yb9976's avatar
yb9976 committed
139
void be_init_copyopt(void)
Sebastian Hack's avatar
Sebastian Hack committed
140
{
141
142
143
144
	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
145

146
	lc_opt_add_table(co_grp, options);
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
	be_add_module_list_opt(co_grp, "algo", "select copy optimization algo",
		                       &copyopts, (void**) &selected_copyopt);
}

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copyopt);

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

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

168
BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copynone);
Sebastian Hack's avatar
Sebastian Hack committed
169

Daniel Grund's avatar
Daniel Grund committed
170
#undef QUICK_AND_DIRTY_HACK
Daniel Grund's avatar
Daniel Grund committed
171

172
173
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
174
	if (env->ifg)
175
176
		return be_ifg_connected(env->ifg, a, b);
	else
177
		return be_values_interfere(env->birg->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
197
198
199
	const char *s1, *s2, *s3;
	int len;
	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
218
219
	snprintf(co->name, len, "%s__%s__%s", s1, s2, s3);

	return co;
}

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

223
224
225
226
227
228
/**
 * 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
229
	const arch_register_req_t *req;
230
	const arch_register_t     *reg;
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
	reg = arch_get_irn_register(irn);
236
237
238
	if (arch_register_type_is(reg, ignore))
		return 0;

239
240
241
	if (is_Reg_Phi(irn) || is_Perm_Proj(irn))
		return 1;

242
	req = arch_get_register_req_out(irn);
243
	if (is_2addr_code(req))
Daniel Grund's avatar
Daniel Grund committed
244
245
246
247
248
		return 1;

	return 0;
}

Sebastian Hack's avatar
Sebastian Hack committed
249
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
250
251
252
	int cost = 0;
	ir_loop *loop;
	ir_node *root_block = get_nodes_block(root);
253
254
	(void) co;
	(void) arg;
Daniel Grund's avatar
Daniel Grund committed
255
256
257
258
259
260
261
262
263
264
265
266

	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;
	}
267
	return 1+cost;
Daniel Grund's avatar
Daniel Grund committed
268
269
}

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

	/* don't allow values smaller than one. */
	return res < 1 ? 1 : res;
Sebastian Hack's avatar
Sebastian Hack committed
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
 */
Daniel Grund's avatar
Daniel Grund committed
305
static int ou_max_ind_set_costs(unit_t *ou) {
306
	be_chordal_env_t *chordal_env = ou->co->cenv;
Daniel Grund's avatar
Daniel Grund committed
307
308
	ir_node **safe, **unsafe;
	int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
Daniel Grund's avatar
Daniel Grund committed
309
	bitset_t *curr;
310
311
	bitset_pos_t pos;
	int max, curr_weight, best_weight = 0;
Daniel Grund's avatar
Daniel Grund committed
312
313
314
315
316

	/* assign the nodes into two groups.
	 * safe: node has no interference, hence it is in every max stable set.
	 * unsafe: node has an interference
	 */
317
318
319
320
321
	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
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
	unsafe_count = 0;
	for(i=1; i<ou->node_count; ++i) {
		int is_safe = 1;
		for(o=1; o<ou->node_count; ++o) {
			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
341
342


343
344
345
346
347
348
349
350
351
352
353
354
	/* now compute the best set out of the unsafe nodes*/
	if (unsafe_count > MIS_HEUR_TRIGGER) {
		bitset_t *best = bitset_alloca(unsafe_count);
		/* Heuristik: Greedy trial and error form index 0 to unsafe_count-1 */
		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
355
		}
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
		/* 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);
		while ((max = bitset_popcnt(curr)) != 0) {
			/* 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 */
			/* compute the weigth of the stable set*/
			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
380

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

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

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

395
	if (req->cls != co->cls)
396
		return;
397
	if (!co_is_optimizable_root(irn))
398
		return;
399

400
	/* Init a new unit */
401
	unit = XMALLOCZ(unit_t);
402
	unit->co = co;
403
	unit->node_count = 1;
404
405
	INIT_LIST_HEAD(&unit->queue);

406
407
408
409
410
411
	/* Phi with some/all of its arguments */
	if (is_Reg_Phi(irn)) {
		int i, arity;

		/* init */
		arity = get_irn_arity(irn);
412
413
		unit->nodes = XMALLOCN(ir_node*, arity + 1);
		unit->costs = XMALLOCN(int,      arity + 1);
414
415
416
		unit->nodes[0] = irn;

		/* fill */
417
		for (i=0; i<arity; ++i) {
418
419
			int o, arg_pos;
			ir_node *arg = get_irn_n(irn, i);
420

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

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

432
433
			if (arch_irn_is_ignore(arg))
				continue;
434

435
436
437
438
439
440
			/* 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;
441
				}
442
			}
443
444
445
446
447
448
449
450
451
452

			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
453
		}
454
455
		unit->nodes = XREALLOC(unit->nodes, ir_node*, unit->node_count);
		unit->costs = XREALLOC(unit->costs, int,      unit->node_count);
456
	} else if (is_Perm_Proj(irn)) {
457
		/* Proj of a perm with corresponding arg */
Daniel Grund's avatar
Daniel Grund committed
458
		assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
459
460
		unit->nodes = XMALLOCN(ir_node*, 2);
		unit->costs = XMALLOCN(int,      2);
461
462
		unit->node_count = 2;
		unit->nodes[0] = irn;
Daniel Grund's avatar
Daniel Grund committed
463
		unit->nodes[1] = get_Perm_src(irn);
Sebastian Hack's avatar
Sebastian Hack committed
464
		unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
Matthias Braun's avatar
Matthias Braun committed
465
466
467
	} else {
		/* Src == Tgt of a 2-addr-code instruction */
		if (is_2addr_code(req)) {
468
469
470
471
472
473
474
			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);
475
476
477
478
479
					if (arch_irn_is_ignore(o))
						continue;
					if (nodes_interfere(co->cenv, irn, o))
						continue;
					++count;
480
481
482
				}
			}

483
484
485
			if (count != 0) {
				int k = 0;
				++count;
486
487
				unit->nodes = XMALLOCN(ir_node*, count);
				unit->costs = XMALLOCN(int,      count);
488
				unit->node_count = count;
489
490
491
492
493
				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);
494
						if (!arch_irn_is_ignore(o) &&
495
496
497
498
499
								!nodes_interfere(co->cenv, irn, o)) {
							unit->nodes[k] = o;
							unit->costs[k] = co->get_costs(co, irn, o, -1);
							++k;
						}
500
501
					}
				}
Matthias Braun's avatar
Matthias Braun committed
502
503
504
			}
		} else {
			assert(0 && "This is not an optimizable node!");
505
		}
Matthias Braun's avatar
Matthias Braun committed
506
	}
507

508
	/* Insert the new unit at a position according to its costs */
509
	if (unit->node_count > 1) {
510
511
		int i;
		struct list_head *tmp;
512

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

519
520
521
522
523
524
525
		/* 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);
526
527
	} else {
		free(unit);
528
	}
529
530
}

Daniel Grund's avatar
Daniel Grund committed
531
532
533
534
535
536
537
538
539
540
541
#ifdef QUICK_AND_DIRTY_HACK

static int compare_ous(const void *k1, const void *k2) {
	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) {
542
		arch_get_register_req_out(&req, u1->nodes[i]);
Daniel Grund's avatar
Daniel Grund committed
543
544
545
546
547
548
549
550
		if (arch_register_req_is(&req, limited)) {
			u1_has_constr = 1;
			break;
		}
	}

	u2_has_constr = 0;
	for (i=0; i<u2->node_count; ++i) {
551
		arch_get_register_req_out(&req, u2->nodes[i]);
Daniel Grund's avatar
Daniel Grund committed
552
553
554
555
556
557
558
559
560
561
		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
562
#if 0
Daniel Grund's avatar
Daniel Grund committed
563
564
565
566
	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
567
#endif
Daniel Grund's avatar
Daniel Grund committed
568
569
570
571
572
573
574
575
576
577

	/* 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
 */
static void co_sort_units(copy_opt_t *co) {
Daniel Grund's avatar
Daniel Grund committed
578
579
	int i, count = 0, costs;
	unit_t *ou, **ous;
Daniel Grund's avatar
Daniel Grund committed
580
581
582
583

	/* 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++;
584
	ous = ALLOCAN(unit_t, count);
Daniel Grund's avatar
Daniel Grund committed
585

Daniel Grund's avatar
Daniel Grund committed
586
587
	costs = co_get_max_copy_costs(co);

Daniel Grund's avatar
Daniel Grund committed
588
	i = 0;
Daniel Grund's avatar
Daniel Grund committed
589
	list_for_each_entry(unit_t, ou, &co->units, units)
Daniel Grund's avatar
Daniel Grund committed
590
591
		ous[i++] = ou;

Daniel Grund's avatar
Daniel Grund committed
592
593
594
595
596
597
	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
598
599
600

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

Daniel Grund's avatar
Daniel Grund committed
601
602
603
604
	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
605
606
607
	/* 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
608
609

	assert(costs == co_get_max_copy_costs(co));
Daniel Grund's avatar
Daniel Grund committed
610
611
612
}
#endif

Daniel Grund's avatar
Daniel Grund committed
613
void co_build_ou_structure(copy_opt_t *co) {
614
	DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
615
	INIT_LIST_HEAD(&co->units);
616
	irg_walk_graph(co->irg, co_collect_units, NULL, co);
Daniel Grund's avatar
Daniel Grund committed
617
618
619
#ifdef QUICK_AND_DIRTY_HACK
	co_sort_units(co);
#endif
620
621
}

Daniel Grund's avatar
Daniel Grund committed
622
void co_free_ou_structure(copy_opt_t *co) {
Daniel Grund's avatar
Daniel Grund committed
623
	unit_t *curr, *tmp;
Daniel Grund's avatar
Daniel Grund committed
624
	ASSERT_OU_AVAIL(co);
Daniel Grund's avatar
Daniel Grund committed
625
	list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
Michael Beck's avatar
Michael Beck committed
626
		xfree(curr->nodes);
627
		xfree(curr->costs);
Michael Beck's avatar
Michael Beck committed
628
		xfree(curr);
629
	}
Daniel Grund's avatar
Daniel Grund committed
630
	co->units.next = NULL;
631
632
}

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

635
636
637
638
int co_get_max_copy_costs(const copy_opt_t *co) {
	int i, res = 0;
	unit_t *curr;

Daniel Grund's avatar
Daniel Grund committed
639
640
	ASSERT_OU_AVAIL(co);

641
642
643
644
645
646
647
648
649
650
651
652
	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;
}

int co_get_inevit_copy_costs(const copy_opt_t *co) {
	int res = 0;
	unit_t *curr;

Daniel Grund's avatar
Daniel Grund committed
653
654
	ASSERT_OU_AVAIL(co);

655
656
657
658
659
	list_for_each_entry(unit_t, curr, &co->units, units)
		res += curr->inevitable_costs;
	return res;
}

Daniel Grund's avatar
Daniel Grund committed
660
int co_get_copy_costs(const copy_opt_t *co) {
661
662
	int i, res = 0;
	unit_t *curr;
663

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

666
	list_for_each_entry(unit_t, curr, &co->units, units) {
667
		int root_col = get_irn_col(curr->nodes[0]);
Daniel Grund's avatar
Daniel Grund committed
668
		DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
669
		res += curr->inevitable_costs;
Daniel Grund's avatar
Daniel Grund committed
670
		for (i=1; i<curr->node_count; ++i) {
671
			int arg_col = get_irn_col(curr->nodes[i]);
Daniel Grund's avatar
Daniel Grund committed
672
			if (root_col != arg_col) {
Daniel Grund's avatar
Daniel Grund committed
673
				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
674
				res += curr->costs[i];
675
			}
Daniel Grund's avatar
Daniel Grund committed
676
		}
677
678
679
680
	}
	return res;
}

681
int co_get_lower_bound(const copy_opt_t *co) {
682
683
	int res = 0;
	unit_t *curr;
Daniel Grund's avatar
Daniel Grund committed
684
685
686

	ASSERT_OU_AVAIL(co);

687
	list_for_each_entry(unit_t, curr, &co->units, units)
688
		res += curr->inevitable_costs + curr->min_nodes_costs;
689
690
	return res;
}
Daniel Grund's avatar
Daniel Grund committed
691

692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
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) {
			if(!bitset_contains_irn(seen, neigh->irn)) {
				stat->aff_edges += 1;
				stat->max_costs += neigh->costs;

709
				if (get_irn_col(an->irn) != get_irn_col(neigh->irn)) {
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
					stat->costs += neigh->costs;
					stat->unsatisfied_edges += 1;
				}

				if(nodes_interfere(co->cenv, an->irn, neigh->irn)) {
					stat->aff_int += 1;
					stat->inevit_costs += neigh->costs;
				}

			}
		}
	}

	bitset_free(seen);
}

Daniel Grund's avatar
Daniel Grund committed
726
727
728
729
730
731
732
733
734
735
736
/******************************************************************************
   _____                 _        _____ _
  / ____|               | |      / ____| |
 | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
  \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
                  | |                                       __/ |
                  |_|                                      |___/
 ******************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
737
738
739
static int compare_affinity_node_t(const void *k1, const void *k2, size_t size) {
	const affinity_node_t *n1 = k1;
	const affinity_node_t *n2 = k2;
740
	(void) size;
Daniel Grund's avatar
Daniel Grund committed
741
742
743
744
745

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

static void add_edge(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
Daniel Grund's avatar
Daniel Grund committed
746
	affinity_node_t new_node, *node;
Christoph Mallon's avatar
Christoph Mallon committed
747
	neighb_t        *nbr;
748
	int             allocnew = 1;
Daniel Grund's avatar
Daniel Grund committed
749
750

	new_node.irn        = n1;
Daniel Grund's avatar
Daniel Grund committed
751
	new_node.degree     = 0;
Daniel Grund's avatar
Daniel Grund committed
752
	new_node.neighbours = NULL;
753
	node = set_insert(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
Daniel Grund's avatar
Daniel Grund committed
754
755
756
757
758
759
760
761
762

	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) {
763
		nbr        = OALLOC(&co->obst, neighb_t);
Daniel Grund's avatar
Daniel Grund committed
764
765
766
		nbr->irn   = n2;
		nbr->costs = 0;
		nbr->next  = node->neighbours;
767

Daniel Grund's avatar
Daniel Grund committed
768
		node->neighbours = nbr;
Daniel Grund's avatar
Daniel Grund committed
769
		node->degree++;
Daniel Grund's avatar
Daniel Grund committed
770
771
772
773
774
775
	}

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

776
static inline void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
Daniel Grund's avatar
Daniel Grund committed
777
778
779
780
781
782
783
	if (! be_ifg_connected(co->cenv->ifg, n1, n2)) {
		add_edge(co, n1, n2, costs);
		add_edge(co, n2, n1, costs);
	}
}

static void build_graph_walker(ir_node *irn, void *env) {
784
	const arch_register_req_t *req = arch_get_register_req_out(irn);
785
	copy_opt_t                *co  = env;
Daniel Grund's avatar
Daniel Grund committed
786
	int pos, max;
787
	const arch_register_t *reg;
Daniel Grund's avatar
Daniel Grund committed
788

789
	if (req->cls != co->cls || arch_irn_is_ignore(irn))
Daniel Grund's avatar
Daniel Grund committed
790
791
		return;

792
	reg = arch_get_irn_register(irn);
793
794
795
	if (arch_register_type_is(reg, ignore))
		return;

796
	if (is_Reg_Phi(irn)) { /* Phis */
Daniel Grund's avatar
Daniel Grund committed
797
798
		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
799
			add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
Daniel Grund's avatar
Daniel Grund committed
800
		}
801
	} else if (is_Perm_Proj(irn)) { /* Perms */
Daniel Grund's avatar
Daniel Grund committed
802
		ir_node *arg = get_Perm_src(irn);
Sebastian Hack's avatar
Sebastian Hack committed
803
		add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
804
	} else { /* 2-address code */
Matthias Braun's avatar
Matthias Braun committed
805
		if (is_2addr_code(req)) {
806
807
808
809
810
811
			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);
812
					if (!arch_irn_is_ignore(other))
813
814
						add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
				}
815
			}
Matthias Braun's avatar
Matthias Braun committed
816
817
		}
	}
Daniel Grund's avatar
Daniel Grund committed
818
819
820
821
}

void co_build_graph_structure(copy_opt_t *co) {
	obstack_init(&co->obst);
Daniel Grund's avatar
Daniel Grund committed
822
	co->nodes = new_set(compare_affinity_node_t, 32);
Daniel Grund's avatar
Daniel Grund committed
823
824
825
826
827

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

void co_free_graph_structure(copy_opt_t *co) {
Daniel Grund's avatar
Daniel Grund committed
828
829
	ASSERT_GS_AVAIL(co);

Daniel Grund's avatar
Daniel Grund committed
830
831
	del_set(co->nodes);
	obstack_free(&co->obst, NULL);
Daniel Grund's avatar
Daniel Grund committed
832
	co->nodes = NULL;
Daniel Grund's avatar
Daniel Grund committed
833
834
835
836
837
}

/* co_solve_ilp1() co_solve_ilp2() are implemented in becopyilpX.c */

int co_gs_is_optimizable(copy_opt_t *co, ir_node *irn) {
Daniel Grund's avatar
Daniel Grund committed
838
839
840
	affinity_node_t new_node, *n;

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

842
	new_node.irn = irn;
843
	n = set_find(co->nodes, &new_node, sizeof(new_node), hash_irn(new_node.irn));
844
	if (n) {
Daniel Grund's avatar
Daniel Grund committed
845
		return (n->degree > 0);
846
847
	} else
		return 0;
Daniel Grund's avatar
Daniel Grund committed
848
}
Sebastian Hack's avatar
Sebastian Hack committed
849

Sebastian Hack's avatar
Sebastian Hack committed
850
851
852
853
854
855
856
857
858
859
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) {
860
		const arch_register_req_t *req = arch_get_register_req_out(nodes[j]);
Sebastian Hack's avatar
Sebastian Hack committed
861
862
863
864
865
866
867
868
869
870
		if(arch_register_req_is(req, limited))
			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
871
872
void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
{
873
874
875
	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);
Sebastian Hack's avatar
Sebastian Hack committed
876
877
878

	ir_node *irn;
	void *it, *nit;
879
	int n, n_regs;
880
	unsigned i;
Sebastian Hack's avatar
Sebastian Hack committed
881
882
883
884
885
886
887
888
889
890
891

	n_regs = 0;
	for(i = 0; i < co->cls->n_regs; ++i) {
		const arch_register_t *reg = &co->cls->regs[i];
		color_map[i] = arch_register_type_is(reg, ignore) ? -1 : n_regs++;
	}

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

	it  = be_ifg_nodes_iter_alloca(ifg);
	nit = be_ifg_neighbours_iter_alloca(ifg);

Sebastian Hack's avatar
Sebastian Hack committed
896
	n = n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
897
	be_ifg_foreach_node(ifg, it, irn) {
898
899
900
		if (arch_irn_is_ignore(irn))
			continue;
		node_map[get_irn_idx(irn)] = n++;
Sebastian Hack's avatar
Sebastian Hack committed
901
902
	}

Sebastian Hack's avatar
Sebastian Hack committed
903
	fprintf(f, "%d %d\n", n, n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
904
905

	be_ifg_foreach_node(ifg, it, irn) {
906
		if (!arch_irn_is_ignore(irn)) {
907
908
909
910
			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
911

Matthias Braun's avatar
Matthias Braun committed
912
913
914
			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
915
						fprintf(f, "%d %d -1\n", color_map[i], idx);
Matthias Braun's avatar
Matthias Braun committed
916
				}
Sebastian Hack's avatar
Sebastian Hack committed
917
918
919
			}

			be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
920
				if (!arch_irn_is_ignore(adj) &&
921
						!co_dump_appel_disjoint_constraints(co, irn, adj)) {
Sebastian Hack's avatar
Sebastian Hack committed
922
					int adj_idx = node_map[get_irn_idx(adj)];
Sebastian Hack's avatar
Sebastian Hack committed
923
924
925
926
927
928
929
930
931
					if(idx < adj_idx)
						fprintf(f, "%d %d -1\n", idx, adj_idx);
				}
			}

			if(a) {
				neighb_t *n;

				co_gs_foreach_neighb(a, n) {
932
					if (!arch_irn_is_ignore(n->irn)) {
Sebastian Hack's avatar
Sebastian Hack committed
933
						int n_idx = node_map[get_irn_idx(n->irn)];
Sebastian Hack's avatar
Sebastian Hack committed
934
						if(idx < n_idx)
935
							fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
Sebastian Hack's avatar
Sebastian Hack committed
936
937
938
939
940
					}
				}
			}
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
941
942

	xfree(node_map);
Sebastian Hack's avatar
Sebastian Hack committed
943
944
}

Sebastian Hack's avatar
Sebastian Hack committed
945
/*
Sebastian Hack's avatar
Sebastian Hack committed
946
947
948
949
950
951
	 ___ _____ ____   ____   ___ _____   ____                        _
	|_ _|  ___/ ___| |  _ \ / _ \_   _| |  _ \ _   _ _ __ ___  _ __ (_)_ __   __ _
	 | || |_ | |  _  | | | | | | || |   | | | | | | | '_ ` _ \| '_ \| | '_ \ / _` |
	 | ||  _|| |_| | | |_| | |_| || |   | |_| | |_| | | | | | | |_) | | | | | (_| |
	|___|_|   \____| |____/ \___/ |_|   |____/ \__,_|_| |_| |_| .__/|_|_| |_|\__, |
	                                                          |_|            |___/
Sebastian Hack's avatar
Sebastian Hack committed
952
953
*/

954
static const char *get_dot_color_name(size_t col)
Sebastian Hack's avatar
Sebastian Hack committed
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
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
{
	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",
		"mediumslateblue"
		"moccasin",
		"tomato",
		"forestgreen",
		"darkturquoise",
		"palevioletred"
	};

	return col < sizeof(names)/sizeof(names[0]) ? names[col] : "white";
}

typedef struct _co_ifg_dump_t {
	const copy_opt_t *co;
	unsigned flags;
} co_ifg_dump_t;

static void ifg_dump_graph_attr(FILE *f, void *self)
{
1000
	(void) self;
For faster browsing, not all history is shown. View entire blame