becopyopt.c 40.3 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * 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
 */
Michael Beck's avatar
Michael Beck committed
32
#ifdef HAVE_CONFIG_H
33
#include "config.h"
Michael Beck's avatar
Michael Beck committed
34
#endif
35

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

52
#include "bemodule.h"
53
#include "bearch_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
54
#include "benode_t.h"
Daniel Grund's avatar
Daniel Grund committed
55
#include "beutil.h"
Daniel Grund's avatar
Daniel Grund committed
56
#include "beifg_t.h"
57
#include "beintlive_t.h"
58
#include "becopyopt_t.h"
59
#include "becopystat.h"
Sebastian Hack's avatar
Sebastian Hack committed
60
61
62
#include "belive_t.h"
#include "beinsn_t.h"
#include "besched_t.h"
63
#include "benodesets.h"
Sebastian Hack's avatar
Sebastian Hack committed
64
#include "bejavacoal.h"
65
#include "bestatevent.h"
66
#include "beirg_t.h"
67
#include "error.h"
Daniel Grund's avatar
Daniel Grund committed
68

69
70
71
72
#include <libcore/lc_timing.h>
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>

Sebastian Hack's avatar
Sebastian Hack committed
73
74
75
76
77
78
79
80
81
#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
82
83
84
static unsigned   dump_flags  = 0;
static unsigned   style_flags = 0;
static unsigned   do_stats    = 0;
Sebastian Hack's avatar
Sebastian Hack committed
85
static cost_fct_t cost_func   = co_get_costs_exec_freq;
86
static unsigned   algo        = CO_ALGO_HEUR4;
Christian Würdig's avatar
Christian Würdig committed
87
static int        improve     = 1;
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 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 }
};

static const lc_opt_enum_mask_items_t algo_items[] = {
Sebastian Hack's avatar
Sebastian Hack committed
107
	{ "none",   CO_ALGO_NONE  },
Sebastian Hack's avatar
Sebastian Hack committed
108
109
	{ "heur",   CO_ALGO_HEUR  },
	{ "heur2",  CO_ALGO_HEUR2 },
110
#ifdef WITH_JVM
Sebastian Hack's avatar
Sebastian Hack committed
111
	{ "heur3",  CO_ALGO_HEUR3 },
112
#endif /* WITH_JVM */
Christian Würdig's avatar
Christian Würdig committed
113
	{ "heur4",  CO_ALGO_HEUR4 },
114
#ifdef WITH_ILP
Sebastian Hack's avatar
Sebastian Hack committed
115
	{ "ilp",    CO_ALGO_ILP   },
116
#endif /* WITH_ILP */
Sebastian Hack's avatar
Sebastian Hack committed
117
118
119
	{ NULL,     0 }
};

Matthias Braun's avatar
Matthias Braun committed
120
121
typedef int (*opt_funcptr)(void);

Sebastian Hack's avatar
Sebastian Hack committed
122
static const lc_opt_enum_func_ptr_items_t cost_func_items[] = {
Matthias Braun's avatar
Matthias Braun committed
123
124
125
126
	{ "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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
};

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_mask_var_t algo_var = {
	&algo, algo_items
};

static lc_opt_enum_func_ptr_var_t cost_func_var = {
Matthias Braun's avatar
Matthias Braun committed
142
	(opt_funcptr*) &cost_func, cost_func_items
Sebastian Hack's avatar
Sebastian Hack committed
143
144
145
};

static const lc_opt_table_entry_t options[] = {
146
147
	LC_OPT_ENT_ENUM_INT      ("algo",    "select copy optimization algo",                           &algo_var),
	LC_OPT_ENT_ENUM_FUNC_PTR ("cost",    "select a cost function",                                  &cost_func_var),
Sebastian Hack's avatar
Sebastian Hack committed
148
149
150
151
	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),
	LC_OPT_ENT_BOOL          ("improve", "run heur3 before if algo can exploit start solutions",    &improve),
152
	LC_OPT_LAST
Sebastian Hack's avatar
Sebastian Hack committed
153
};
Sebastian Hack's avatar
Sebastian Hack committed
154
155

/* Insert additional options registration functions here. */
Sebastian Hack's avatar
Sebastian Hack committed
156
extern void be_co_ilp_register_options(lc_opt_entry_t *grp);
Sebastian Hack's avatar
Sebastian Hack committed
157
extern void be_co2_register_options(lc_opt_entry_t *grp);
Sebastian Hack's avatar
Sebastian Hack committed
158
extern void be_co3_register_options(lc_opt_entry_t *grp);
Sebastian Hack's avatar
Sebastian Hack committed
159

160
void be_init_copycoal(void)
Sebastian Hack's avatar
Sebastian Hack committed
161
{
162
163
164
165
	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
166

167
	lc_opt_add_table(co_grp, options);
Sebastian Hack's avatar
Sebastian Hack committed
168
}
169
170

BE_REGISTER_MODULE_CONSTRUCTOR(be_init_copycoal);
Sebastian Hack's avatar
Sebastian Hack committed
171

Daniel Grund's avatar
Daniel Grund committed
172
#undef QUICK_AND_DIRTY_HACK
Daniel Grund's avatar
Daniel Grund committed
173

174
175
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
176
	if (env->ifg)
177
178
		return be_ifg_connected(env->ifg, a, b);
	else
179
		return values_interfere(env->birg, a, b);
180
181
182
}


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

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

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

Sebastian Hack's avatar
Sebastian Hack committed
195

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

202
	FIRM_DBG_REGISTER(dbg, "ir.be.copyopt");
Daniel Grund's avatar
Daniel Grund committed
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

	co = xcalloc(1, sizeof(*co));
	co->cenv      = chordal_env;
	co->aenv      = chordal_env->birg->main_env->arch_env;
	co->irg       = chordal_env->irg;
	co->cls       = chordal_env->cls;
	co->get_costs = get_costs;

	s1 = get_irp_prog_name();
	s2 = get_entity_name(get_irg_entity(co->irg));
	s3 = chordal_env->cls->name;
	len = strlen(s1) + strlen(s2) + strlen(s3) + 5;
	co->name = xmalloc(len);
	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
223
	free(co);
Daniel Grund's avatar
Daniel Grund committed
224
225
226
}

int co_is_optimizable_root(const copy_opt_t *co, ir_node *irn) {
Matthias Braun's avatar
Matthias Braun committed
227
	const arch_register_req_t *req;
228
	const arch_register_t *reg;
Daniel Grund's avatar
Daniel Grund committed
229

230
	if (arch_irn_is(co->aenv, irn, ignore))
Daniel Grund's avatar
Daniel Grund committed
231
232
		return 0;

233
234
235
236
	reg = arch_get_irn_register(co->aenv, irn);
	if (arch_register_type_is(reg, ignore))
		return 0;

Matthias Braun's avatar
Matthias Braun committed
237
238
	req = arch_get_register_req(co->aenv, irn, -1);
	if (is_Reg_Phi(irn) || is_Perm_Proj(co->aenv, irn) || is_2addr_code(req))
Daniel Grund's avatar
Daniel Grund committed
239
240
241
242
243
		return 1;

	return 0;
}

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

	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;
	}
262
	return 1+cost;
Daniel Grund's avatar
Daniel Grund committed
263
264
}

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

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


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

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

Daniel Grund's avatar
Daniel Grund committed
296
/**
Daniel Grund's avatar
Daniel Grund committed
297
298
 * 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
299
 */
Daniel Grund's avatar
Daniel Grund committed
300
static int ou_max_ind_set_costs(unit_t *ou) {
301
	be_chordal_env_t *chordal_env = ou->co->cenv;
Daniel Grund's avatar
Daniel Grund committed
302
303
	ir_node **safe, **unsafe;
	int i, o, safe_count, safe_costs, unsafe_count, *unsafe_costs;
Daniel Grund's avatar
Daniel Grund committed
304
	bitset_t *curr;
305
306
	bitset_pos_t pos;
	int max, curr_weight, best_weight = 0;
Daniel Grund's avatar
Daniel Grund committed
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335

	/* assign the nodes into two groups.
	 * safe: node has no interference, hence it is in every max stable set.
	 * unsafe: node has an interference
	 */
	safe = alloca((ou->node_count-1) * sizeof(*safe));
	safe_costs = 0;
	safe_count = 0;
	unsafe = alloca((ou->node_count-1) * sizeof(*unsafe));
	unsafe_costs = alloca((ou->node_count-1) * sizeof(*unsafe_costs));
	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
336
337


338
339
340
341
342
343
344
345
346
347
348
349
	/* 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
350
		}
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
		/* 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
375

376
377
378
	no_stable_set:
			bitset_minus1(curr);
		}
Daniel Grund's avatar
Daniel Grund committed
379
	}
Daniel Grund's avatar
Daniel Grund committed
380
381

	return safe_costs+best_weight;
Daniel Grund's avatar
Daniel Grund committed
382
}
383

384
385
static void co_collect_units(ir_node *irn, void *env) {
	copy_opt_t *co = env;
386
	unit_t *unit;
Daniel Grund's avatar
Daniel Grund committed
387

388
	if (!is_curr_reg_class(co, irn))
389
		return;
Daniel Grund's avatar
Daniel Grund committed
390
	if (!co_is_optimizable_root(co, irn))
391
		return;
392

393
	/* Init a new unit */
Michael Beck's avatar
Michael Beck committed
394
	unit = xcalloc(1, sizeof(*unit));
395
	unit->co = co;
396
	unit->node_count = 1;
397
398
	INIT_LIST_HEAD(&unit->queue);

399
400
401
402
403
404
405
406
407
408
409
	/* Phi with some/all of its arguments */
	if (is_Reg_Phi(irn)) {
		int i, arity;

		/* init */
		arity = get_irn_arity(irn);
		unit->nodes = xmalloc((arity+1) * sizeof(*unit->nodes));
		unit->costs = xmalloc((arity+1) * sizeof(*unit->costs));
		unit->nodes[0] = irn;

		/* fill */
410
		for (i=0; i<arity; ++i) {
411
412
			int o, arg_pos;
			ir_node *arg = get_irn_n(irn, i);
413

414
			assert(is_curr_reg_class(co, arg) && "Argument not in same register class.");
415
			if (arg == irn)
416
				continue;
417
			if (nodes_interfere(co->cenv, irn, arg)) {
Sebastian Hack's avatar
Sebastian Hack committed
418
				unit->inevitable_costs += co->get_costs(co, irn, arg, i);
419
420
421
422
				continue;
			}

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

425
426
427
428
429
430
431
432
			if (! arch_irn_is(co->aenv, arg, ignore)) {
				/* 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;
					}
Daniel Grund's avatar
Daniel Grund committed
433
				}
434

435
436
437
438
439
				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++;
Michael Beck's avatar
Michael Beck committed
440
				} else { /* arg has occurred before in same phi */
441
442
443
					/* increase costs for existing arg */
					unit->costs[arg_pos] += co->get_costs(co, irn, arg, i);
				}
444
			}
Daniel Grund's avatar
Daniel Grund committed
445
		}
446
		unit->nodes = xrealloc(unit->nodes, unit->node_count * sizeof(*unit->nodes));
Daniel Grund's avatar
Daniel Grund committed
447
		unit->costs = xrealloc(unit->costs, unit->node_count * sizeof(*unit->costs));
448
	} else
Daniel Grund's avatar
Daniel Grund committed
449

450
	/* Proj of a perm with corresponding arg */
451
	if (is_Perm_Proj(co->aenv, irn)) {
Daniel Grund's avatar
Daniel Grund committed
452
		assert(!nodes_interfere(co->cenv, irn, get_Perm_src(irn)));
453
454
455
456
		unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
		unit->costs = xmalloc(2 * sizeof(*unit->costs));
		unit->node_count = 2;
		unit->nodes[0] = irn;
Daniel Grund's avatar
Daniel Grund committed
457
		unit->nodes[1] = get_Perm_src(irn);
Sebastian Hack's avatar
Sebastian Hack committed
458
		unit->costs[1] = co->get_costs(co, irn, unit->nodes[1], -1);
Matthias Braun's avatar
Matthias Braun committed
459
460
461
462
463
464
	} else {
		const arch_register_req_t *req =
			arch_get_register_req(co->aenv, irn, -1);

		/* Src == Tgt of a 2-addr-code instruction */
		if (is_2addr_code(req)) {
465
			ir_node *other = get_irn_n(skip_Proj(irn), req->other_same[0]); /* TODO handle second should-be-same constraint */
466
467
			if (!arch_irn_is(co->aenv, other, ignore) &&
					!nodes_interfere(co->cenv, irn, other)) {
Matthias Braun's avatar
Matthias Braun committed
468
469
470
471
472
473
474
475
476
				unit->nodes = xmalloc(2 * sizeof(*unit->nodes));
				unit->costs = xmalloc(2 * sizeof(*unit->costs));
				unit->node_count = 2;
				unit->nodes[0] = irn;
				unit->nodes[1] = other;
				unit->costs[1] = co->get_costs(co, irn, other, -1);
			}
		} else {
			assert(0 && "This is not an optimizable node!");
477
		}
Matthias Braun's avatar
Matthias Braun committed
478
	}
479

480
	/* Insert the new unit at a position according to its costs */
481
	if (unit->node_count > 1) {
482
483
		int i;
		struct list_head *tmp;
484

485
486
487
488
489
		/* 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];
		}
490

491
492
493
494
495
496
497
		/* 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);
498
499
	} else {
		free(unit);
500
	}
501
502
}

Daniel Grund's avatar
Daniel Grund committed
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
#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;
	const arch_env_t *aenv = u1->co->aenv;

	/* Units with constraints come first */
	u1_has_constr = 0;
	for (i=0; i<u1->node_count; ++i) {
		arch_get_register_req(aenv, &req, u1->nodes[i], -1);
		if (arch_register_req_is(&req, limited)) {
			u1_has_constr = 1;
			break;
		}
	}

	u2_has_constr = 0;
	for (i=0; i<u2->node_count; ++i) {
		arch_get_register_req(aenv, &req, u2->nodes[i], -1);
		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
535
#if 0
Daniel Grund's avatar
Daniel Grund committed
536
537
538
539
	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
540
#endif
Daniel Grund's avatar
Daniel Grund committed
541
542
543
544
545
546
547
548
549
550

	/* 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
551
552
	int i, count = 0, costs;
	unit_t *ou, **ous;
Daniel Grund's avatar
Daniel Grund committed
553
554
555
556
557
558

	/* 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++;
	ous = alloca(count * sizeof(*ous));

Daniel Grund's avatar
Daniel Grund committed
559
560
	costs = co_get_max_copy_costs(co);

Daniel Grund's avatar
Daniel Grund committed
561
	i = 0;
Daniel Grund's avatar
Daniel Grund committed
562
	list_for_each_entry(unit_t, ou, &co->units, units)
Daniel Grund's avatar
Daniel Grund committed
563
564
		ous[i++] = ou;

Daniel Grund's avatar
Daniel Grund committed
565
566
567
568
569
570
	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
571
572
573

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

Daniel Grund's avatar
Daniel Grund committed
574
575
576
577
	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
578
579
580
	/* 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
581
582

	assert(costs == co_get_max_copy_costs(co));
Daniel Grund's avatar
Daniel Grund committed
583
584
585
}
#endif

Daniel Grund's avatar
Daniel Grund committed
586
void co_build_ou_structure(copy_opt_t *co) {
587
	DBG((dbg, LEVEL_1, "\tCollecting optimization units\n"));
588
	INIT_LIST_HEAD(&co->units);
589
	irg_walk_graph(co->irg, co_collect_units, NULL, co);
Daniel Grund's avatar
Daniel Grund committed
590
591
592
#ifdef QUICK_AND_DIRTY_HACK
	co_sort_units(co);
#endif
593
594
}

Daniel Grund's avatar
Daniel Grund committed
595
void co_free_ou_structure(copy_opt_t *co) {
Daniel Grund's avatar
Daniel Grund committed
596
	unit_t *curr, *tmp;
Daniel Grund's avatar
Daniel Grund committed
597
	ASSERT_OU_AVAIL(co);
Daniel Grund's avatar
Daniel Grund committed
598
	list_for_each_entry_safe(unit_t, curr, tmp, &co->units, units) {
Michael Beck's avatar
Michael Beck committed
599
		xfree(curr->nodes);
600
		xfree(curr->costs);
Michael Beck's avatar
Michael Beck committed
601
		xfree(curr);
602
	}
Daniel Grund's avatar
Daniel Grund committed
603
	co->units.next = NULL;
604
605
}

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

608
609
610
611
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
612
613
	ASSERT_OU_AVAIL(co);

614
615
616
617
618
619
620
621
622
623
624
625
	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
626
627
	ASSERT_OU_AVAIL(co);

628
629
630
631
632
	list_for_each_entry(unit_t, curr, &co->units, units)
		res += curr->inevitable_costs;
	return res;
}

Daniel Grund's avatar
Daniel Grund committed
633
int co_get_copy_costs(const copy_opt_t *co) {
634
635
	int i, res = 0;
	unit_t *curr;
636

Daniel Grund's avatar
Daniel Grund committed
637
638
	ASSERT_OU_AVAIL(co);

639
	list_for_each_entry(unit_t, curr, &co->units, units) {
640
		int root_col = get_irn_col(co, curr->nodes[0]);
Daniel Grund's avatar
Daniel Grund committed
641
		DBG((dbg, LEVEL_1, "  %3d costs for root %+F color %d\n", curr->inevitable_costs, curr->nodes[0], root_col));
642
		res += curr->inevitable_costs;
Daniel Grund's avatar
Daniel Grund committed
643
644
645
		for (i=1; i<curr->node_count; ++i) {
			int arg_col = get_irn_col(co, curr->nodes[i]);
			if (root_col != arg_col) {
Daniel Grund's avatar
Daniel Grund committed
646
				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
647
				res += curr->costs[i];
648
			}
Daniel Grund's avatar
Daniel Grund committed
649
		}
650
651
652
653
	}
	return res;
}

654
int co_get_lower_bound(const copy_opt_t *co) {
655
656
	int res = 0;
	unit_t *curr;
Daniel Grund's avatar
Daniel Grund committed
657
658
659

	ASSERT_OU_AVAIL(co);

660
	list_for_each_entry(unit_t, curr, &co->units, units)
661
		res += curr->inevitable_costs + curr->min_nodes_costs;
662
663
	return res;
}
Daniel Grund's avatar
Daniel Grund committed
664

665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
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;

				if(get_irn_col(co, an->irn) != get_irn_col(co, neigh->irn)) {
					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
699
700
701
702
703
704
705
706
707
708
709
/******************************************************************************
   _____                 _        _____ _
  / ____|               | |      / ____| |
 | |  __ _ __ __ _ _ __ | |__   | (___ | |_ ___  _ __ __ _  __ _  ___
 | | |_ | '__/ _` | '_ \| '_ \   \___ \| __/ _ \| '__/ _` |/ _` |/ _ \
 | |__| | | | (_| | |_) | | | |  ____) | || (_) | | | (_| | (_| |  __/
  \_____|_|  \__,_| .__/|_| |_| |_____/ \__\___/|_|  \__,_|\__, |\___|
                  | |                                       __/ |
                  |_|                                      |___/
 ******************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
710
711
712
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;
713
	(void) size;
Daniel Grund's avatar
Daniel Grund committed
714
715
716
717
718

	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
719
	affinity_node_t new_node, *node;
Christoph Mallon's avatar
Christoph Mallon committed
720
	neighb_t        *nbr;
721
	int             allocnew = 1;
Daniel Grund's avatar
Daniel Grund committed
722
723

	new_node.irn        = n1;
Daniel Grund's avatar
Daniel Grund committed
724
	new_node.degree     = 0;
Daniel Grund's avatar
Daniel Grund committed
725
	new_node.neighbours = NULL;
726
	node = set_insert(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn));
Daniel Grund's avatar
Daniel Grund committed
727
728
729
730
731
732
733
734
735

	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) {
736
		nbr        = obstack_alloc(&co->obst, sizeof(*nbr));
Daniel Grund's avatar
Daniel Grund committed
737
738
739
		nbr->irn   = n2;
		nbr->costs = 0;
		nbr->next  = node->neighbours;
740

Daniel Grund's avatar
Daniel Grund committed
741
		node->neighbours = nbr;
Daniel Grund's avatar
Daniel Grund committed
742
		node->degree++;
Daniel Grund's avatar
Daniel Grund committed
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
	}

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

static INLINE void add_edges(copy_opt_t *co, ir_node *n1, ir_node *n2, int costs) {
	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) {
	copy_opt_t *co = env;
	int pos, max;
759
	const arch_register_t *reg;
Daniel Grund's avatar
Daniel Grund committed
760

761
	if (!is_curr_reg_class(co, irn) || arch_irn_is(co->aenv, irn, ignore))
Daniel Grund's avatar
Daniel Grund committed
762
763
		return;

764
765
766
767
	reg = arch_get_irn_register(co->aenv, irn);
	if (arch_register_type_is(reg, ignore))
		return;

768
	if (is_Reg_Phi(irn)) { /* Phis */
Daniel Grund's avatar
Daniel Grund committed
769
770
		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
771
			add_edges(co, irn, arg, co->get_costs(co, irn, arg, pos));
Daniel Grund's avatar
Daniel Grund committed
772
		}
773
774
	}
	else if (is_Perm_Proj(co->aenv, irn)) { /* Perms */
Daniel Grund's avatar
Daniel Grund committed
775
		ir_node *arg = get_Perm_src(irn);
Sebastian Hack's avatar
Sebastian Hack committed
776
		add_edges(co, irn, arg, co->get_costs(co, irn, arg, 0));
Daniel Grund's avatar
Daniel Grund committed
777
	}
778
779
	else { /* 2-address code */
		const arch_register_req_t *req = arch_get_register_req(co->aenv, irn, -1);
Matthias Braun's avatar
Matthias Braun committed
780
		if (is_2addr_code(req)) {
781
782
783
784
785
786
787
788
789
790
			const int *i;
			for (i = req->other_same; i != ENDOF(req->other_same); ++i) {
				ir_node *other;

				if (*i == -1) break;

				other = get_irn_n(skip_Proj(irn), *i);
				if (! arch_irn_is(co->aenv, other, ignore))
					add_edges(co, irn, other, co->get_costs(co, irn, other, 0));
			}
Matthias Braun's avatar
Matthias Braun committed
791
792
		}
	}
Daniel Grund's avatar
Daniel Grund committed
793
794
795
796
}

void co_build_graph_structure(copy_opt_t *co) {
	obstack_init(&co->obst);
Daniel Grund's avatar
Daniel Grund committed
797
	co->nodes = new_set(compare_affinity_node_t, 32);
Daniel Grund's avatar
Daniel Grund committed
798
799
800
801
802

	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
803
804
	ASSERT_GS_AVAIL(co);

Daniel Grund's avatar
Daniel Grund committed
805
806
	del_set(co->nodes);
	obstack_free(&co->obst, NULL);
Daniel Grund's avatar
Daniel Grund committed
807
	co->nodes = NULL;
Daniel Grund's avatar
Daniel Grund committed
808
809
810
811
812
}

/* 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
813
814
815
	affinity_node_t new_node, *n;

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

817
	new_node.irn = irn;
818
	n = set_find(co->nodes, &new_node, sizeof(new_node), nodeset_hash(new_node.irn));
819
	if (n) {
Daniel Grund's avatar
Daniel Grund committed
820
		return (n->degree > 0);
821
822
	} else
		return 0;
Daniel Grund's avatar
Daniel Grund committed
823
}
Sebastian Hack's avatar
Sebastian Hack committed
824
825
826

void co_dump_appel_graph(const copy_opt_t *co, FILE *f)
{
Sebastian Hack's avatar
Sebastian Hack committed
827
828
	be_ifg_t *ifg  = co->cenv->ifg;
	int *color_map = alloca(co->cls->n_regs * sizeof(color_map[0]));
Sebastian Hack's avatar
Sebastian Hack committed
829
830
831

	ir_node *irn;
	void *it, *nit;
Sebastian Hack's avatar
Sebastian Hack committed
832
833
834
835
836
837
838
839
840
841
842
843
	int i, n, n_regs;

	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
844
845
846
847

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

Sebastian Hack's avatar
Sebastian Hack committed
848
	n = n_regs;
Sebastian Hack's avatar
Sebastian Hack committed
849
	be_ifg_foreach_node(ifg, it, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
850
851
		if(!arch_irn_is(co->aenv, irn, ignore))
			set_irn_link(irn, INT_TO_PTR(n++));
Sebastian Hack's avatar
Sebastian Hack committed
852
853
	}

Sebastian Hack's avatar
Sebastian Hack committed
854
	fprintf(f, "%d %d\n", n, n_regs);
Sebastian Hack's avatar
Sebastian Hack committed
855
856

	be_ifg_foreach_node(ifg, it, irn) {
Sebastian Hack's avatar
Sebastian Hack committed
857
858
859
860
		if(!arch_irn_is(co->aenv, irn, ignore)) {
			int idx            = PTR_TO_INT(get_irn_link(irn));
			affinity_node_t *a = get_affinity_info(co, irn);

Matthias Braun's avatar
Matthias Braun committed
861
			const arch_register_req_t *req;
Sebastian Hack's avatar
Sebastian Hack committed
862
863
			ir_node *adj;

Matthias Braun's avatar
Matthias Braun committed
864
865
866
867
			req = arch_get_register_req(co->aenv, irn, BE_OUT_POS(0));
			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
868
						fprintf(f, "%d %d -1\n", color_map[i], idx);
Matthias Braun's avatar
Matthias Braun committed
869
				}
Sebastian Hack's avatar
Sebastian Hack committed
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
			}


			be_ifg_foreach_neighbour(ifg, nit, irn, adj) {
				if(!arch_irn_is(co->aenv, adj, ignore)) {
					int adj_idx = PTR_TO_INT(get_irn_link(adj));
					if(idx < adj_idx)
						fprintf(f, "%d %d -1\n", idx, adj_idx);
				}
			}

			if(a) {
				neighb_t *n;

				co_gs_foreach_neighb(a, n) {
					if(!arch_irn_is(co->aenv, n->irn, ignore)) {
						int n_idx = PTR_TO_INT(get_irn_link(n->irn));
						if(idx < n_idx)
888
							fprintf(f, "%d %d %d\n", idx, n_idx, (int) n->costs);
Sebastian Hack's avatar
Sebastian Hack committed
889
890
891
892
893
894
895
896
					}
				}
			}
		}
	}
}

typedef struct _appel_clique_walker_t {
Michael Beck's avatar
Michael Beck committed
897
	ir_phase ph;
Sebastian Hack's avatar
Sebastian Hack committed
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
	const copy_opt_t *co;
	int curr_nr;
	int node_count;
	FILE *f;
	int dumb;
	int *color_map;
	struct obstack obst;
} appel_clique_walker_t;

typedef struct _appel_block_info_t {
	int *live_end_nr;
	int *live_in_nr;
	int *phi_nr;
	ir_node **live_end;
	ir_node **live_in;
	ir_node **phi;
	int n_live_end;
	int n_live_in;
	int n_phi;
} appel_block_info_t;

static int appel_aff_weight(const appel_clique_walker_t *env, ir_node *bl)
{
#if 0
	double freq = get_block_execfreq(env->co->cenv->execfreq, bl);
	int res = (int) freq;
	return res == 0 ? 1 : res;
#else
	ir_loop *loop = get_irn_loop(bl);
927
	(void) env;
Sebastian Hack's avatar
Sebastian Hack committed
928
929
930
931
932
933
934
935
	if(loop) {
		int d = get_loop_depth(loop);
		return 1 + d * d;
	}
	return 1;
#endif
}

Michael Beck's avatar
Michael Beck committed
936
static void *appel_clique_walker_irn_init(ir_phase *phase, ir_node *irn, void *old)
Sebastian Hack's avatar
Sebastian Hack committed
937
938
{
	appel_block_info_t *res = NULL;
939
	(void) old;
Sebastian Hack's avatar
Sebastian Hack committed
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971

	if(is_Block(irn)) {
		appel_clique_walker_t *d = (void *) phase;
		res = phase_alloc(phase, sizeof(res[0]));
		res->phi_nr      = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
		res->live_end_nr = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end_nr));
		res->live_in_nr  = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in_nr));
		res->live_end    = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_end));
		res->live_in     = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
		res->phi         = phase_alloc(phase, d->co->cls->n_regs * sizeof(res->live_in));
	}

	return res;
}

typedef struct _insn_list_t {
	be_insn_t *insn;
	struct list_head list;
} insn_list_t;

static int appel_get_live_end_nr(appel_clique_walker_t *env, ir_node *bl, ir_node *irn)
{
	appel_block_info_t *bli = phase_get_irn_data(&env->ph, bl);
	int i;

	for(i = 0; i < bli->n_live_end; ++i)
		if(bli->live_end[i] == irn)
			return bli->live_end_nr[i];

	return -1;
}

972
static int appel_dump_clique(appel_clique_walker_t *env, const ir_nodeset_t *live, ir_node *bl, int curr_nr, int start_nr)
Sebastian Hack's avatar
Sebastian Hack committed
973
974
975
976
977
{
	ir_node **live_arr = alloca(env->co->cls->n_regs * sizeof(live_arr[0]));
	ir_node *irn;
	int n_live;
	int j;
978
	ir_nodeset_iterator_t iter;
Sebastian Hack's avatar
Sebastian Hack committed
979
980

	n_live = 0;
981
	foreach_ir_nodeset(live, irn, iter)
Sebastian Hack's avatar
Sebastian Hack committed
982
983
984
985
986
987
988
989
990
991
992
993
994
		live_arr[n_live++] = irn;

	/* dump the live after clique */
	if(!env->dumb) {
		for(j = 0; j < n_live; ++j) {
			int k;

			for(k = j + 1; k < n_live; ++k) {
				fprintf(env->f, "%d %d -1 ", curr_nr + j, curr_nr + k);
			}
			fprintf(env->f, "\n");
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
995

Sebastian Hack's avatar
Sebastian Hack committed
996
997
998
999
	/* dump the affinities */
	for(j = 0; !env->dumb && j < n_live; ++j) {
		ir_node *irn = live_arr[j];
		int old_nr = PTR_TO_INT(get_irn_link(irn));
Sebastian Hack's avatar
Sebastian Hack committed
1000

For faster browsing, not all history is shown. View entire blame