beschedrss.c 64.4 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
 * @file
 * @brief       Implementation of a register saturating list scheduler.
 * @author      Christian Wuerdig
 * @date        29.08.2006
 * @version     $Id$
 *
27
28
29
30
 * Implementation of a register saturating list scheduler
 * as described in: Sid-Ahmed-Ali Touati
 * Register Saturation in Superscalar and VLIW Codes
 */
31
#include "config.h"
32

33
34
#include "beschedrss.h"

35
36
37
38
39
40
41
42
43
44
45
#include <limits.h>

#include "obst.h"
#include "debug.h"

#include "irgraph_t.h"
#include "irnode_t.h"
#include "iredges_t.h"
#include "ircons_t.h"
#include "irphase_t.h"
#include "irgwalk.h"
Christian Würdig's avatar
Christian Würdig committed
46
#include "irdump.h"
47
48
49
#include "irtools.h"
#include "irbitset.h"
#include "irprintf.h"
50
#include "irnodeset.h"
51
52
53
#include "bipartite.h"
#include "hungarian.h"
#include "plist.h"
54
#include "array_t.h"
55

56
#include "heights.h"
57
58

#include "beabi.h"
59
#include "bemodule.h"
60
#include "benode.h"
61
62
63
#include "besched.h"
#include "beirg.h"
#include "belive.h"
64

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


Christian Würdig's avatar
Christian Würdig committed
69
#define ARR_LEN_SAFE(arr) ((arr) != NULL ? ARR_LEN((arr)) : 0)
70
71

#define HASH_RSS_EDGE(edge) ((get_irn_node_nr((edge)->src) << 16) | (get_irn_node_nr((edge)->tgt) & 0xFFFF))
72
#define BSEARCH_IRN_ARR(val, arr) \
Christian Würdig's avatar
Christian Würdig committed
73
	bsearch(&(val), (arr), ARR_LEN_SAFE((arr)), sizeof((arr)[0]), cmp_irn_idx)
74

Christian Würdig's avatar
Christian Würdig committed
75
#define BLOCK_IDX_MAP(rss, irn) bsearch_for_index(get_irn_idx((irn)), (rss)->idx_map, ARR_LEN_SAFE((rss)->idx_map), 1)
76

Christian Würdig's avatar
Christian Würdig committed
77
/* the rss options */
78
typedef struct rss_opts_t {
Christian Würdig's avatar
Christian Würdig committed
79
80
81
	int dump_flags;
} rss_opts_t;

82
/* Represents a child with associated costs */
83
typedef struct child {
84
85
86
87
88
	ir_node *irn;
	float   cost;
} child_t;

/* We need edges for several purposes. */
89
typedef struct rss_edge {
90
91
92
93
94
95
	ir_node *src;
	ir_node *tgt;
	void    *next;
} rss_edge_t;

/* Represents a connected bipartite component. */
96
typedef struct cbc {
Matthias Braun's avatar
Matthias Braun committed
97
98
	ir_nodeset_t parents;       /**< = S  a set of value producers */
	ir_nodeset_t children;      /**< = T  a set of value consumers */
99
100
101
102
103
	pset    *kill_edges;    /**< = E  a set of edges (t in T, s in S) such as each s in S gets killed by at least one t in T */
	int     nr;             /**< a deterministic index for set insertion (used as hash) */
} cbc_t;

/* Represents a disjoint value DAG. */
104
typedef struct dvg {
Matthias Braun's avatar
Matthias Braun committed
105
	ir_nodeset_t nodes;
106
107
108
109
	pset    *edges;
} dvg_t;

/* Represents a chain of nodes. */
110
typedef struct chain {
111
112
113
114
	plist_t *elements;   /**< List of chain elements */
	int     nr;          /**< a deterministic index for set insertion (used as hash) */
} chain_t;

115
typedef struct rss_irn {
116
	plist_t  *consumer_list;    /**< List of consumers */
117
	const ir_node **consumer;   /**< Sorted consumer array (needed for faster access) */
118
119

	plist_t  *parent_list;      /**< List of parents */
120
	plist_t  *pkiller_list;     /**< List of potential killers */
121
122

	plist_t  *descendant_list;  /**< List of descendants */
123
	const ir_node **descendants;      /**< Sorted descendant array (needed for faster access) */
124

125
126
	const ir_node  *killer;     /**< The selected unique killer */
	const ir_node  *irn;        /**< The corresponding firm node to this rss_irn */
127
128
129

	chain_t  *chain;            /**< The chain, this node is associated to */

130
	unsigned desc_walk;         /**< visited flag for collecting descendants */
131
	unsigned kill_count;        /**< number of nodes killed by this one */
132

133
134
	unsigned live_out : 1;      /**< irn has consumers outside of it's block */
	unsigned visited  : 1;      /**< visited flag for bipartite decomposition */
135
	unsigned havecons : 1;      /**< visited flag collect consumer */
136
137
138
139
	unsigned handled  : 1;      /**< flag indicating whether or not the list structures have been build */
	unsigned dumped   : 1;      /**< flag indication whether or not this node was dumped */
} rss_irn_t;

Christian Würdig's avatar
Christian Würdig committed
140
/* Represents a serialization edge with associated costs. */
141
typedef struct serialization {
Christian Würdig's avatar
Christian Würdig committed
142
143
144
145
146
	rss_irn_t  *u;       /* the top node */
	rss_irn_t  *v;       /* the node about to be serialized after u */
	rss_edge_t *edge;    /* the edge selected for the serialization */
	int        omega1;   /* estimated: available regs - RS reduction */
	int        omega2;   /* increase in critical path length */
Christian Würdig's avatar
Christian Würdig committed
147
	int        new_killer;
Christian Würdig's avatar
Christian Würdig committed
148
149
} serialization_t;

150
typedef struct rss {
Michael Beck's avatar
Michael Beck committed
151
	ir_phase          ph;              /**< Phase to hold some data */
152
	ir_heights_t     *h;              /**< The current height object */
153
154
155
156
157
158
	ir_graph         *irg;            /**< The irg to preprocess */
	plist_t          *nodes;          /**< The list of interesting nodes */
	const arch_env_t *arch_env;       /**< The architecture environment */
	be_abi_irg_t     *abi;            /**< The abi for this irg */
	pset             *cbc_set;        /**< A set of connected bipartite components */
	ir_node          *block;          /**< The current block in progress. */
159
160
	int              *idx_map;        /**< Mapping irn indices to per block indices */
	unsigned         max_height;      /**< maximum height in the current block */
Christian Würdig's avatar
Christian Würdig committed
161
	rss_opts_t       *opts;           /**< The options */
162
	be_lv_t          *liveness;       /**< The liveness information for this irg */
163
	ir_nodeset_t      live_block;     /**< Values alive at end of block */
164
165
166
167
168
169
170
171
172
173
	const arch_register_class_t *cls; /**< The current register class */
	DEBUG_ONLY(firm_dbg_module_t *dbg);
} rss_t;

#define get_rss_irn(rss, irn)  (phase_get_or_set_irn_data(&rss->ph, irn))

/**
 * We need some special nodes:
 * a source and a sink for all live-in and live-out values of a block
 */
174
enum {
175
176
177
178
179
	iro_rss_Source,
	iro_rss_Sink,
	iro_rss_last
};

180
181
182
183
184
185
/** The opcode of the rss_Source node once allocated. */
static ir_op *op_rss_Source;
/** The opcode of the rss_Sink node once allocated. */
static ir_op *op_rss_Sink;

/** The rss_Source node of the current graph. */
186
static ir_node *_source = NULL;
187
/** The rss_Sink node of the current graph. */
188
189
190
191
192
static ir_node *_sink   = NULL;

#define is_Source(irn) ((irn) == _source)
#define is_Sink(irn)   ((irn) == _sink)

Christian Würdig's avatar
Christian Würdig committed
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
enum {
	RSS_DUMP_NONE  = 0,
	RSS_DUMP_CBC   = 1 << 0,
	RSS_DUMP_PKG   = 1 << 1,
	RSS_DUMP_KILL  = 1 << 2,
	RSS_DUMP_DVG   = 1 << 3,
	RSS_DUMP_MAXAC = 1 << 4,
	RSS_DUMP_ALL   = (RSS_DUMP_MAXAC << 1) - 1,
};

static rss_opts_t rss_options = {
	RSS_DUMP_NONE,
};

static const lc_opt_enum_int_items_t dump_items[] = {
	{ "none",  RSS_DUMP_NONE  },
	{ "cbc",   RSS_DUMP_CBC   },
	{ "pkg",   RSS_DUMP_PKG   },
	{ "kill",  RSS_DUMP_KILL  },
	{ "dvg",   RSS_DUMP_DVG   },
	{ "maxac", RSS_DUMP_MAXAC },
	{ "all",   RSS_DUMP_ALL   },
	{ NULL, 0 }
};

static lc_opt_enum_int_var_t dump_var = {
	&rss_options.dump_flags, dump_items
};

static const lc_opt_table_entry_t rss_option_table[] = {
223
	LC_OPT_ENT_ENUM_MASK("dump", "dump phases", &dump_var),
224
	LC_OPT_LAST
Christian Würdig's avatar
Christian Würdig committed
225
226
};

Christian Würdig's avatar
Christian Würdig committed
227
228
229
230
231
232
233
234
235
236
237
/******************************************************************************
 *  _          _                    __                  _   _
 * | |        | |                  / _|                | | (_)
 * | |__   ___| |_ __   ___ _ __  | |_ _   _ _ __   ___| |_ _  ___  _ __  ___
 * | '_ \ / _ \ | '_ \ / _ \ '__| |  _| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
 * | | | |  __/ | |_) |  __/ |    | | | |_| | | | | (__| |_| | (_) | | | \__ \
 * |_| |_|\___|_| .__/ \___|_|    |_|  \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
 *            | |
 *            |_|
 ******************************************************************************/

238
/**
239
 * Acquire opcodes if needed and create source and sink nodes.
240
 */
241
242
static void init_rss_special_nodes(ir_graph *irg)
{
243
244
245
246
247
248
249
250
251
252
	ir_node *block;

	if (op_rss_Source == NULL) {
		int iro_rss_base = get_next_ir_opcodes(iro_rss_last);
		op_rss_Source = new_ir_op(iro_rss_base + iro_rss_Source, "rss_Source", op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
		op_rss_Sink   = new_ir_op(iro_rss_base + iro_rss_Sink,   "rss_Sink",   op_pin_state_pinned, irop_flag_none, oparity_zero, 0, 0, NULL);
	}
	block   = get_irg_start_block(irg);
	_source = new_ir_node(NULL, irg, block, op_rss_Source, mode_ANY, 0, NULL);
	_sink   = new_ir_node(NULL, irg, block, op_rss_Sink, mode_ANY, 0, NULL);
253
254
}

255
256
static int cmp_int(const void *a, const void *b)
{
257
258
259
260
261
262
	const int *i1 = a;
	const int *i2 = b;

	return QSORT_CMP(*i1, *i2);
}

263
264
static int cmp_child_costs(const void *a, const void *b)
{
265
266
267
268
269
270
	const child_t *c1 = a;
	const child_t *c2 = b;

	return QSORT_CMP(c1->cost, c2->cost);
}

271
272
static int cmp_irn_idx(const void *a, const void *b)
{
273
274
275
276
277
278
	const ir_node *n1 = *(ir_node **)a;
	const ir_node *n2 = *(ir_node **)b;

	return QSORT_CMP(get_irn_idx(n1), get_irn_idx(n2));
}

279
280
static int cmp_rss_edges(const void *a, const void *b)
{
281
282
283
284
285
286
	const rss_edge_t *e1 = a;
	const rss_edge_t *e2 = b;

	return (e1->src != e2->src) || (e1->tgt != e2->tgt);
}

287
288
static int bsearch_for_index(int key, int *arr, size_t len, int force)
{
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
	int left = 0;
	int right = len;

	while (right >= left) {
		int idx = (left + right) / 2;

		if (key < arr[idx])
			right = idx - 1;
		else if (key > arr[idx])
			left = idx + 1;
		else
			return idx;
	}

	if (force)
		assert(0 && "Something is wrong, key not found.");
	return -1;
}

308
309
static const ir_node **build_sorted_array_from_list(plist_t *irn_list, struct obstack *obst)
{
310
	plist_element_t *el;
311
312
	int             i   = 0;
	int             len = plist_count(irn_list);
313
	const ir_node   **arr = (const ir_node**)NEW_ARR_D(ir_node*, obst, len);
314
315
316
317
318
319
320

	/* copy the list into the array */
	foreach_plist(irn_list, el) {
		arr[i++] = plist_element_get_value(el);
	}

	/* sort the array by node index */
321
322
	/* HACK cast for MSVC */
	qsort((void*)arr, len, sizeof(arr[0]), cmp_irn_idx);
323
324
325
326

	return arr;
}

Christian Würdig's avatar
Christian Würdig committed
327
328
329
330
331
332
333
334
335
336
337
338
/*****************************************************
 *      _      _                       _
 *     | |    | |                     (_)
 *   __| | ___| |__  _   _  __ _  __ _ _ _ __   __ _
 *  / _` |/ _ \ '_ \| | | |/ _` |/ _` | | '_ \ / _` |
 * | (_| |  __/ |_) | |_| | (_| | (_| | | | | | (_| |
 *  \__,_|\___|_.__/ \__,_|\__, |\__, |_|_| |_|\__, |
 *                          __/ | __/ |         __/ |
 *                         |___/ |___/         |___/
 *
 *****************************************************/

Matthias Braun's avatar
Matthias Braun committed
339
#ifdef DEBUG_libfirm
340
341
static void dump_nodeset(ir_nodeset_t *ns, const char *prefix)
{
Matthias Braun's avatar
Matthias Braun committed
342
	ir_nodeset_iterator_t iter;
Christian Würdig's avatar
Christian Würdig committed
343
	ir_node *irn;
Matthias Braun's avatar
Matthias Braun committed
344
345

	ir_nodeset_iterator_init(&iter, ns);
346
	while ( (irn = ir_nodeset_iterator_next(&iter)) != NULL ) {
Christian Würdig's avatar
Christian Würdig committed
347
		ir_fprintf(stderr, "%s%+F\n", prefix, irn);
Christian Würdig's avatar
Christian Würdig committed
348
349
	}
}
Matthias Braun's avatar
Matthias Braun committed
350
#endif
Christian Würdig's avatar
Christian Würdig committed
351

352
353
static void build_file_name(rss_t *rss, const char *suffix, size_t suf_len, char *buf, size_t len)
{
354
355
356
357
	const char *irg_name;

	memset(buf, 0, len);
	irg_name = get_entity_name(get_irg_entity(rss->irg));
Christian Würdig's avatar
Christian Würdig committed
358
	snprintf(buf, len - suf_len, "%s-%s-block-%ld",
359
360
361
362
363
		irg_name, arch_register_class_name(rss->cls), get_irn_node_nr(rss->block));
	strcat(buf, suffix);
}

/* Dumps all collected bipartite components of current irg as vcg. */
364
365
static void debug_vcg_dump_bipartite(rss_t *rss)
{
366
367
368
369
370
371
372
373
374
375
376
377
378
379
	cbc_t *cbc;
	FILE  *f;
	char  file_name[256];
	static const char suffix[] = "-RSS-CBC.vcg";

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"connected bipartite component graph of %+F\"\n", rss->irg);
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	foreach_pset(rss->cbc_set, cbc) {
Matthias Braun's avatar
Matthias Braun committed
380
		ir_nodeset_iterator_t iter;
381
382
383
384
		ir_node    *n;
		rss_edge_t *ke;

		fprintf(f, "graph: { titel: \"cbc %d\" label: \"cbc %d\" status:clustered color:yellow\n", cbc->nr, cbc->nr);
Matthias Braun's avatar
Matthias Braun committed
385
		foreach_ir_nodeset(&cbc->parents, n, iter) {
386
387
			ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
		}
Matthias Braun's avatar
Matthias Braun committed
388
		foreach_ir_nodeset(&cbc->children, n, iter) {
389
390
391
392
393
394
395
396
397
398
399
400
401
			ir_fprintf(f, "node: { title: \"n%d_%d\" label: \"%+F\" }\n", get_irn_node_nr(n), cbc->nr, n);
		}
		foreach_pset(cbc->kill_edges, ke) {
			ir_fprintf(f, "edge: { sourcename: \"n%d_%d\" targetname: \"n%d_%d\" }\n",
				get_irn_node_nr(ke->src), cbc->nr, get_irn_node_nr(ke->tgt), cbc->nr);
		}
		fprintf(f, "}\n\n");
	}
	fprintf(f, "}\n");
	fclose(f);
}

/* Dump the computed killing function as vcg. */
402
403
static void debug_vcg_dump_kill(rss_t *rss)
{
Christian Würdig's avatar
Christian Würdig committed
404
405
	FILE            *f;
	char            file_name[256];
406
	plist_element_t *el;
Christian Würdig's avatar
Christian Würdig committed
407
	static const char suffix[] = "-RSS-KILL.vcg";
408
409
410
411
412
413
414
415
416

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"computed kill graph of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

Christian Würdig's avatar
Christian Würdig committed
417
418
419
420
421
422
423
	{
		/* reset dump_flag */
		ir_node *irn;
		foreach_phase_irn(&rss->ph, irn) {
			rss_irn_t *node = get_rss_irn(rss, irn);
			node->dumped = 0;
		}
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
	}

	/* dump all nodes and their killers */
	foreach_plist(rss->nodes, el) {
		ir_node   *irn     = plist_element_get_value(el);
		rss_irn_t *rirn    = get_rss_irn(rss, irn);
		rss_irn_t *pk_rirn = get_rss_irn(rss, rirn->killer);

		if (! rirn->dumped) {
			ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
			rirn->dumped = 1;
		}

		if (! pk_rirn->dumped) {
			ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(rirn->killer), rirn->killer);
			pk_rirn->dumped = 1;
		}

		ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
			get_irn_node_nr(rirn->killer), get_irn_node_nr(irn));
	}

	fprintf(f, "}\n");
	fclose(f);
}

/* Dumps the potential killing DAG (PKG) as vcg. */
451
452
static void debug_vcg_dump_pkg(rss_t *rss, ir_nodeset_t *max_ac, int iteration)
{
Christian Würdig's avatar
Christian Würdig committed
453
454
	FILE              *f;
	char              file_name[256];
455
	char              suffix[32];
Christian Würdig's avatar
Christian Würdig committed
456
457
458
459
460
	static const char suffix1[] = "-RSS-PKG.vcg";
	static const char suffix2[] = "-RSS-PKG-MAXAC.vcg";
	plist_element_t   *el;

	if (! max_ac) {
461
		snprintf(suffix, sizeof(suffix), "%s", suffix1);
Christian Würdig's avatar
Christian Würdig committed
462
463
	}
	else {
464
		snprintf(suffix, sizeof(suffix), "-%02d%s", iteration, suffix2);
Christian Würdig's avatar
Christian Würdig committed
465
	}
466

Christian Würdig's avatar
Christian Würdig committed
467
	build_file_name(rss, suffix, strlen(suffix) + 1, file_name, sizeof(file_name));
468
469
470
471
472
473
474
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"potential killing DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

Christian Würdig's avatar
Christian Würdig committed
475
476
477
478
479
480
481
482
483
	{
		/* reset dump_flag */
		ir_node *irn;
		foreach_phase_irn(&rss->ph, irn) {
			rss_irn_t *node = get_rss_irn(rss, irn);
			node->dumped = 0;
		}
	}

484
485
486
	foreach_plist(rss->nodes, el) {
		ir_node   *irn  = plist_element_get_value(el);
		rss_irn_t *rirn = get_rss_irn(rss, irn);
Christian Würdig's avatar
Christian Würdig committed
487
		char      *c1   = "";
488
489
		plist_element_t *k_el;

Christian Würdig's avatar
Christian Würdig committed
490
		/* dump selected saturating values in yellow */
Matthias Braun's avatar
Matthias Braun committed
491
		if (max_ac && ir_nodeset_contains(max_ac, irn))
Christian Würdig's avatar
Christian Würdig committed
492
493
			c1 = "color:yellow";

Christian Würdig's avatar
Christian Würdig committed
494
495
496
497
498
499
500
		if (! rirn->dumped) {
			if (rirn->chain)
				ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F   c%d\" %s }\n", get_irn_node_nr(irn), irn, rirn->chain->nr, c1);
			else
				ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(irn), irn, c1);
			rirn->dumped = 1;
		}
501
502
503
504

		foreach_plist(rirn->pkiller_list, k_el) {
			ir_node   *pkiller = plist_element_get_value(k_el);
			rss_irn_t *pk_rirn = get_rss_irn(rss, pkiller);
Christian Würdig's avatar
Christian Würdig committed
505
506
			char      *c2      = "";

Matthias Braun's avatar
Matthias Braun committed
507
			if (max_ac && ir_nodeset_contains(max_ac, pkiller))
Christian Würdig's avatar
Christian Würdig committed
508
				c2 = "color:yellow";
509
510

			if (! pk_rirn->dumped) {
Christian Würdig's avatar
Christian Würdig committed
511
512
513
514
				if (pk_rirn->chain)
					ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F   c%d\" %s }\n", get_irn_node_nr(pkiller), pkiller, pk_rirn->chain->nr, c2);
				else
					ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" %s }\n", get_irn_node_nr(pkiller), pkiller, c2);
515
516
517
518
519
520
521
522
523
524
525
				pk_rirn->dumped = 1;
			}
			ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
				get_irn_node_nr(pkiller), get_irn_node_nr(irn));
		}
	}
	fprintf(f, "}\n");
	fclose(f);
}

/* Dumps the disjoint value DAG (DVG) as vcg. */
526
527
static void debug_vcg_dump_dvg(rss_t *rss, dvg_t *dvg)
{
528
529
530
	static const char suffix[] = "-RSS-DVG.vcg";
	FILE       *f;
	char       file_name[256];
Matthias Braun's avatar
Matthias Braun committed
531
	ir_nodeset_iterator_t iter;
532
533
534
535
536
537
538
539
540
541
542
543
	ir_node    *irn;
	rss_edge_t *edge;

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	/* dump all nodes */
Matthias Braun's avatar
Matthias Braun committed
544
	foreach_ir_nodeset(&dvg->nodes, irn, iter) {
545
546
547
548
549
550
551
552
553
554
555
556
557
		ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
	}

	/* dump all edges */
	foreach_pset(dvg->edges, edge) {
		ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
			get_irn_node_nr(edge->src), get_irn_node_nr(edge->tgt));
	}

	fprintf(f, "}\n");
	fclose(f);
}

Christian Würdig's avatar
Christian Würdig committed
558
#if 0
559
/* Dumps the PKG(DVG). */
560
561
static void debug_vcg_dump_dvg_pkiller(rss_t *rss, dvg_t *dvg)
{
562
563
564
	static const char suffix[] = "-RSS-DVG-PKG.vcg";
	FILE       *f;
	char       file_name[256];
Matthias Braun's avatar
Matthias Braun committed
565
	ir_nodeset_iterator_t iter;
566
567
568
569
570
571
572
573
574
575
576
	ir_node    *irn;

	build_file_name(rss, suffix, sizeof(suffix), file_name, sizeof(file_name));
	f = fopen(file_name, "w");

	ir_fprintf(f, "graph: { title: \"PKG of disjoint value DAG of %+F, block %d\"\n", rss->irg, get_irn_node_nr(rss->block));
	fprintf(f, "display_edge_labels: no\n");
	fprintf(f, "layoutalgorithm: mindepth\n");
	fprintf(f, "manhattan_edges: yes\n\n");

	/* dump all nodes */
Matthias Braun's avatar
Matthias Braun committed
577
	foreach_ir_nodeset(&dvg->nodes, irn, iter) {
578
579
580
581
		ir_fprintf(f, "node: { title: \"n%d\" label: \"%+F\" }\n", get_irn_node_nr(irn), irn);
	}

	/* dump all edges */
Matthias Braun's avatar
Matthias Braun committed
582
	foreach_ir_nodeset(&dvg->nodes, irn, iter) {
583
584
585
586
587
588
589
590
591
592
593
594
		rss_irn_t       *node = get_rss_irn(rss, irn);
		plist_element_t *el;

		foreach_plist(node->dvg_pkiller_list, el) {
			ir_fprintf(f, "edge: { sourcename: \"n%d\" targetname: \"n%d\" }\n",
				get_irn_node_nr(plist_element_get_value(el)), get_irn_node_nr(irn));
		}
	}

	fprintf(f, "}\n");
	fclose(f);
}
Christian Würdig's avatar
Christian Würdig committed
595
#endif /* if 0 */
596
597
598
599

/**
 * In case there is no rss information for irn, initialize it.
 */
600
static void *init_rss_irn(ir_phase *ph, const ir_node *irn)
601
{
602
	rss_irn_t *res = phase_alloc(ph, sizeof(res[0]));
603

604
605
	res->descendant_list = plist_obstack_new(phase_obst(ph));
	res->descendants     = NULL;
606

607
608
	res->consumer_list   = plist_obstack_new(phase_obst(ph));
	res->consumer        = NULL;
609

610
	res->pkiller_list    = plist_obstack_new(phase_obst(ph));
611

612
	res->parent_list     = plist_obstack_new(phase_obst(ph));
613

614
615
616
	res->killer          = NULL;
	res->irn             = irn;
	res->chain           = NULL;
617

618
619
620
621
622
623
624
	res->kill_count      = 0;
	res->desc_walk       = 0;
	res->live_out        = 0;
	res->visited         = 0;
	res->handled         = 0;
	res->dumped          = 0;
	res->havecons        = 0;
625
626
627
628
629
630
631

	return res;
}

/**
 * Collect all nodes data dependent on current node.
 */
632
633
static void collect_descendants(rss_t *rss, rss_irn_t *rirn, ir_node *irn, int *got_sink, unsigned cur_desc_walk)
{
634
	const ir_edge_t *edge;
635
636
637
638
639
	rss_irn_t       *cur_node = get_rss_irn(rss, irn);
	ir_node         *block    = rss->block;
	ir_edge_kind_t  ekind[2]  = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
	int             i;

640
641
642
	if (cur_node->desc_walk >= cur_desc_walk)
		return;
	cur_node->desc_walk = cur_desc_walk;
643

644
645
	/* Stop at Barriers */
	if (be_is_Barrier(irn))
646
		return;
647

Christian Würdig's avatar
Christian Würdig committed
648
649
650
651
	/* loop over normal and dependency edges */
	for (i = 0; i < 2; ++i) {
		foreach_out_edge_kind(irn, edge, ekind[i]) {
			ir_node *user = get_edge_src_irn(edge);
652

Christian Würdig's avatar
Christian Würdig committed
653
			/* skip ignore nodes as they do not really contribute to register pressure */
654
			if (arch_irn_is_ignore(user))
Christian Würdig's avatar
Christian Würdig committed
655
				continue;
656

657
658
659
660
661
			/*
				(a) mode_X means Jump            -> out_edge
				(b) Phi as user of a normal node -> out-edge
			*/
			if (get_irn_mode(user) == mode_X || is_Phi(user)) {
662
				if (! *got_sink)
663
					goto force_sink;
664
665
666
				else
					continue;
			}
667

668
			if (is_Proj(user)) {
669
				//if (arch_get_irn_reg_class_out(user) == rss->cls)
670
					collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
Christian Würdig's avatar
Christian Würdig committed
671
			}
672
673
674
675
676
677
678
			else {
				/* check if user lives in block and is not a control flow node */
				if (get_nodes_block(user) == block) {
					if (! plist_has_value(rirn->descendant_list, user)) {
						plist_insert_back(rirn->descendant_list, user);
						DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", user));
					}
679
					collect_descendants(rss, rirn, user, got_sink, cur_desc_walk);
680
681
				}
				else if (! *got_sink) {
682
force_sink:
683
684
685
686
687
					/* user lives out of block: add sink as descendant if not already done */
					plist_insert_back(rirn->descendant_list, _sink);
					*got_sink = 1;
					DBG((rss->dbg, LEVEL_2, "\t\tdescendant %+F\n", _sink));
				}
688
689
690
691
692
693
694
695
			}
		}
	}
}

/**
 * Handles a single consumer.
 */
696
697
static void collect_single_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *consumer, int *got_sink)
{
698
	ir_node *block = rss->block;
699

700
	assert(! is_Proj(consumer) && "Cannot handle Projs");
Christian Würdig's avatar
Christian Würdig committed
701

702
	if (! is_Phi(consumer) && ! is_Block(consumer) && get_nodes_block(consumer) == block) {
703
		if (!arch_irn_is_ignore(consumer) &&
704
				!plist_has_value(rss_irn->consumer_list, consumer)) {
705
			plist_insert_back(rss_irn->consumer_list, consumer);
Christian Würdig's avatar
Christian Würdig committed
706
			DBG((rss->dbg, LEVEL_2, "\t\tconsumer %+F\n", consumer));
707
708
709
710
		}
	}
	else {
		rss_irn->live_out = 1;
Christian Würdig's avatar
Christian Würdig committed
711
		DBG((rss->dbg, LEVEL_2, "\t\tlive out %+F", consumer));
712
		if (! *got_sink) {
713
			plist_insert_back(rss_irn->consumer_list, _sink);
714
			*got_sink = 1;
Christian Würdig's avatar
Christian Würdig committed
715
			DB((rss->dbg, LEVEL_2, ", %+F added instead", _sink));
716
		}
Christian Würdig's avatar
Christian Würdig committed
717
		DB((rss->dbg, LEVEL_2, "\n"));
718
719
720
721
722
723
	}
}

/**
 * Collect all nodes consuming the value(s) produced by current node.
 */
724
725
static void collect_consumer(rss_t *rss, rss_irn_t *rss_irn, ir_node *irn, int *got_sink)
{
726
	const ir_edge_t *edge;
Christian Würdig's avatar
Christian Würdig committed
727
	int             i;
728
729
730
731
732
733
	ir_edge_kind_t  ekind[2]  = { EDGE_KIND_NORMAL, EDGE_KIND_DEP };
	rss_irn_t       *cur_node = get_rss_irn(rss, irn);

	if (cur_node->havecons)
		return;
	cur_node->havecons = 1;
Christian Würdig's avatar
Christian Würdig committed
734
735
736
737

	for (i = 0; i < 2; ++i) {
		foreach_out_edge_kind(irn, edge, ekind[i]) {
			ir_node *consumer = get_edge_src_irn(edge);
738
739

			if (is_Proj(consumer)) {
740
				//if (arch_get_irn_reg_class_out(consumer) == rss->cls)
741
742
743
744
					collect_consumer(rss, rss_irn, consumer, got_sink);
			}
			else
				collect_single_consumer(rss, rss_irn, consumer, got_sink);
Christian Würdig's avatar
Christian Würdig committed
745
		}
746
747
748
749
750
751
	}
}

/**
 * Collects all consumer and descendant of a irn.
 */
752
753
static void collect_node_info(rss_t *rss, ir_node *irn)
{
754
755
756
	static unsigned cur_desc_walk = 0;
	rss_irn_t       *rss_irn      = get_rss_irn(rss, irn);
	int             got_sink;
757

758
	assert(! is_Proj(irn) && "Cannot handle Projs.");
759
760
761

	/* check if node info is already available */
	if (rss_irn->handled)
762
		return;
763

Christian Würdig's avatar
Christian Würdig committed
764
	DBG((rss->dbg, LEVEL_1, "\tcomputing consumers of %+F:\n", irn));
765
766

	/* collect all consumer */
767
768
	got_sink = 0;
	collect_consumer(rss, rss_irn, irn, &got_sink);
769
770
771
772

	/* build sorted consumer array */
	rss_irn->consumer = build_sorted_array_from_list(rss_irn->consumer_list, phase_obst(&rss->ph));

Christian Würdig's avatar
Christian Würdig committed
773
	DBG((rss->dbg, LEVEL_1, "\tcompute descendants of %+F:\n", irn));
774
775
776

	/* collect descendants */
	got_sink = 0;
777
	collect_descendants(rss, rss_irn, irn, &got_sink, ++cur_desc_walk);
778
779
780
781
782
783
784
785
786

	/* build sorted descendant array */
	rss_irn->descendants = build_sorted_array_from_list(rss_irn->descendant_list, phase_obst(&rss->ph));

	rss_irn->handled = 1;
}

/**
 * Checks if v is a potential killer of u.
787
 * v is in pkill(u) iff descendants(v) cut consumer(u) is v
788
789
790
791
792
793
 *
 * @param rss   The rss object
 * @param v      The node to check for killer
 * @param u      The potentially killed value
 * @return 1 if v is in pkill(u), 0 otherwise
 */
794
795
static int is_potential_killer(rss_t *rss, rss_irn_t *v, rss_irn_t *u)
{
796
	plist_t *list;
797
	const ir_node **arr;
798
	plist_element_t *el;
799
	(void) rss;
800
801
802
803
804
805
806
807
808
809
810
811
812

	/* as we loop over the list: loop over the shorter one */
	if (plist_count(v->descendant_list) > plist_count(u->consumer_list)) {
		list = u->consumer_list;
		arr  = v->descendants;
	}
	else {
		list = v->descendant_list;
		arr  = u->consumer;
	}

	/* for each list element: try to find element in array */
	foreach_plist(list, el) {
813
814
815
816
		ir_node *irn   = plist_element_get_value(el);
		ir_node *match = BSEARCH_IRN_ARR(irn, arr);

		if (match && match != irn)
817
818
819
820
821
822
			return 0;
	}

	return 1;
}

Christian Würdig's avatar
Christian Würdig committed
823
824
825
/**
 * Update descendants, consumer and pkiller list for the given irn.
 */
826
827
static void update_node_info(rss_t *rss, ir_node *irn, ir_node *pk_irn)
{
Christian Würdig's avatar
Christian Würdig committed
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
	rss_irn_t *node    = get_rss_irn(rss, irn);
	rss_irn_t *pkiller = get_rss_irn(rss, pk_irn);

	/* add consumer and rebuild the consumer array */
	if (! plist_has_value(node->consumer_list, pk_irn)) {
		plist_insert_back(node->consumer_list, pk_irn);
		node->consumer = build_sorted_array_from_list(node->consumer_list, phase_obst(&rss->ph));
	}

	/* add pk_irn as descendant, add it's descendants to irn's and rebuild array */
	if (! plist_has_value(node->descendant_list, pk_irn)) {
		plist_element_t *el;

		plist_insert_back(node->descendant_list, pk_irn);

		foreach_plist(pkiller->descendant_list, el) {
			ir_node *desc = plist_element_get_value(el);

			if (! plist_has_value(node->descendant_list, desc))
				plist_insert_back(node->descendant_list, desc);
		}

		node->descendants = build_sorted_array_from_list(node->descendant_list, phase_obst(&rss->ph));
	}

}

855
856
857
/**
 * Compute the potential killing set PK.
 */
858
859
static void compute_pkill_set(rss_t *rss)
{
860
861
862
863
864
865
	plist_element_t *u_el, *v_el;

	foreach_plist(rss->nodes, u_el) {
		ir_node   *u_irn = plist_element_get_value(u_el);
		rss_irn_t *u     = get_rss_irn(rss, u_irn);

Christian Würdig's avatar
Christian Würdig committed
866
		DBG((rss->dbg, LEVEL_1, "\tcomputing potential killers of %+F:\n", u_irn));
867
868
869
870
871
872
873
874
875
876

		/* check each consumer if it is a potential killer  */
		foreach_plist(u->consumer_list, v_el) {
			ir_node   *v_irn = plist_element_get_value(v_el);
			rss_irn_t *v     = get_rss_irn(rss, v_irn);

			/* check, if v is a potential killer of u */
			if (is_potential_killer(rss, v, u)) {
				if (! plist_has_value(u->pkiller_list, v_irn))
					plist_insert_back(u->pkiller_list, v_irn);
877
				v->kill_count++;
Christian Würdig's avatar
Christian Würdig committed
878
				DBG((rss->dbg, LEVEL_2, "\t\tpotential killer %+F\n", v_irn));
879
880
881
882
883
884
			}
		}

		u->killer = _sink;
	}

Christian Würdig's avatar
Christian Würdig committed
885
886
	if (rss->opts->dump_flags & RSS_DUMP_PKG)
		debug_vcg_dump_pkg(rss, NULL, 0);
887
888
889
890
891
}

/**
 * Build set of killing edges (from values to their potential killers)
 */
892
893
static void build_kill_edges(rss_t *rss, pset *epk)
{
894
895
896
897
898
899
	plist_element_t *el, *k_el;

	foreach_plist(rss->nodes, el) {
		ir_node    *irn  = plist_element_get_value(el);
		rss_irn_t *rirn = get_rss_irn(rss, irn);

Christian Würdig's avatar
Christian Würdig committed
900
901
		DBG((rss->dbg, LEVEL_3, "\t\tbuilding kill edges for %+F:\n", irn));

902
903
		foreach_plist(rirn->pkiller_list, k_el) {
			ir_node    *pkiller = plist_element_get_value(k_el);
904
			rss_edge_t *ke      = OALLOC(phase_obst(&rss->ph), rss_edge_t);
905
906
907
908
909

			ke->src  = irn;
			ke->tgt  = pkiller;
			ke->next = NULL;

Christian Würdig's avatar
Christian Würdig committed
910
911
			DBG((rss->dbg, LEVEL_3, "\t\t\ttarget %+F\n", pkiller));

912
913
914
915
916
			pset_insert(epk, ke, HASH_RSS_EDGE(ke));
		}
	}
}

Matthias Braun's avatar
Matthias Braun committed
917
#ifdef DEBUG_libfirm
918
/* print the given cbc for debugging purpose */
919
920
static void debug_print_cbc(firm_dbg_module_t *mod, cbc_t *cbc)
{
Matthias Braun's avatar
Matthias Braun committed
921
	ir_nodeset_iterator_t iter;
922
923
924
	ir_node    *n;
	rss_edge_t *ke;

Christian Würdig's avatar
Christian Würdig committed
925
	DBG((mod, LEVEL_3, "\t\tS = set of parents:\n"));
Matthias Braun's avatar
Matthias Braun committed
926
	foreach_ir_nodeset(&cbc->parents, n, iter) {
Christian Würdig's avatar
Christian Würdig committed
927
		DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
928
	}
Christian Würdig's avatar
Christian Würdig committed
929
	DBG((mod, LEVEL_3, "\t\tT = set of children:\n"));
Matthias Braun's avatar
Matthias Braun committed
930
	foreach_ir_nodeset(&cbc->children, n, iter) {
Christian Würdig's avatar
Christian Würdig committed
931
		DBG((mod, LEVEL_3, "\t\t\t%+F\n", n));
932
	}
Christian Würdig's avatar
Christian Würdig committed
933
	DBG((mod, LEVEL_3, "\t\tE = Edges from producers to consumers\n"));
934
	foreach_pset(cbc->kill_edges, ke) {
Christian Würdig's avatar
Christian Würdig committed
935
		DBG((mod, LEVEL_3, "\t\t\t%+F -> %+F\n", ke->src, ke->tgt));
936
937
	}
}
Matthias Braun's avatar
Matthias Braun committed
938
#endif
939
940
941
942
943
944

/**
 * Construct the bipartite decomposition.
 * Sid-Ahmed-Ali Touati, Phd Thesis
 * Register Pressure in Instruction Level Parallelism, p. 71
 */
945
946
static void compute_bipartite_decomposition(rss_t *rss)
{
947
948
949
950
951
	pset *epk    = new_pset(cmp_rss_edges, 10);
	int  cur_num = 0;

	plist_element_t *el;

Christian Würdig's avatar
Christian Würdig committed
952
	DBG((rss->dbg, LEVEL_1, "\tcomputing bipartite decomposition:\n"));
953
954
955
956
957
958
959
960

	build_kill_edges(rss, epk);

	foreach_plist(rss->nodes, el) {
		ir_node   *u_irn   = plist_element_get_value(el);
		rss_irn_t *u       = get_rss_irn(rss, u_irn);
		int       p_change = 1;
		int       c_change = 1;
Christian Würdig's avatar
Christian Würdig committed
961
		int       vrfy_ok  = 1;
962
963
964
965
966
967

		cbc_t           *cbc;
		plist_element_t *el2;
		rss_edge_t      *k_edge;
		rss_edge_t      *kedge_root = NULL;
		ir_node         *t_irn, *s_irn;
Matthias Braun's avatar
Matthias Braun committed
968
		ir_nodeset_iterator_t iter;
969
970
971
972

		if (u->visited || u_irn == _sink)
			continue;

Christian Würdig's avatar
Christian Würdig committed
973
		DBG((rss->dbg, LEVEL_2, "\t\t%+F choosen:\n", u_irn));
974

975
		cbc     = OALLOC(phase_obst(&rss->ph), cbc_t);
976
977
978
		cbc->nr = cur_num++;

		/* initialize S_cb */
Matthias Braun's avatar
Matthias Braun committed
979
980
		ir_nodeset_init_size(&cbc->parents, 5);
		ir_nodeset_insert(&cbc->parents, u_irn);
Christian Würdig's avatar
Christian Würdig committed
981
		DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to parents (init)\n", u_irn));
982
983
984
985
986
987
988

		/* E_cb = empty */
		cbc->kill_edges = new_pset(cmp_rss_edges, 5);

		/* each parent gets killed by at least one value from children */

		/* T_cb = PK_successors(u) */
Matthias Braun's avatar
Matthias Braun committed
989
		ir_nodeset_init_size(&cbc->children, 5);
990
		foreach_plist(u->pkiller_list, el2) {
Matthias Braun's avatar
Matthias Braun committed
991
			ir_nodeset_insert(&cbc->children, plist_element_get_value(el2));
Christian Würdig's avatar
Christian Würdig committed
992
			DBG((rss->dbg, LEVEL_3, "\t\t\t%+F added to children (init)\n", plist_element_get_value(el2)));
993
994
995
996
997
998
999
1000
		}

		/*
			Now: insert the parents of all children into the parent set
			and insert the children of all parents into the children set
			until the sets don't change any more
		*/
		while (p_change || c_change) {