beschedmris.c 12.5 KB
Newer Older
1
2
3
4
5
6
7
8
/**
 * Implements a list scheduler for the MRIS algorithm in:
 * Govindarajan, Yang, Amaral, Zhang, Gao
 * Minimum Register Instruction Sequencing to Reduce Register Spills
 * in out-of-order issue superscalar architectures
 * @author Sebastian Hack
 * @date   04.04.2006
 */
Michael Beck's avatar
Michael Beck committed
9
10
11
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
12
13
14

#include <limits.h>

15
#include "obst.h"
16
17
18
19
20
21
#include "debug.h"

#include "irgraph_t.h"
#include "irnode_t.h"
#include "iredges_t.h"
#include "ircons_t.h"
Sebastian Hack's avatar
Merged    
Sebastian Hack committed
22
#include "irphase_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
23
#include "irdump_t.h"
24
25
#include "irgwalk.h"
#include "irtools.h"
Sebastian Hack's avatar
Sebastian Hack committed
26
#include "irbitset.h"
27

Sebastian Hack's avatar
Sebastian Hack committed
28
29
#include "height.h"

30
31
32
33
34
#include "benode_t.h"
#include "besched_t.h"
#include "beschedmris.h"

struct _mris_env_t {
Sebastian Hack's avatar
Merged    
Sebastian Hack committed
35
	phase_t            ph;
Sebastian Hack's avatar
Sebastian Hack committed
36
	heights_t         *heights;
37
38
39
40
41
42
	const arch_env_t  *aenv;
	ir_graph          *irg;
	ir_node           *bl;
	int               visited;
	struct list_head  lineage_head;
	struct obstack    obst;
Sebastian Hack's avatar
Sebastian Hack committed
43
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
44
45
46
47
48
49
50
51
52
53
54
55
};

typedef struct _mris_irn_t {
	int visited;
	ir_node *lineage_start;
	ir_node *lineage_next;
	ir_node *lineage_end;
	struct list_head lineage_list;
} mris_irn_t;

#define to_appear(env, irn) (to_appear_in_schedule(irn) && get_nodes_block(irn) == env->bl)

Sebastian Hack's avatar
Merged    
Sebastian Hack committed
56
#define get_mris_irn(env, irn)   ((mris_irn_t *) phase_get_or_set_irn_data(&env->ph, irn))
57
58
#define foreach_lineage(env, pos, tmp) list_for_each_entry_safe(mris_irn_t, pos, tmp, &(env)->lineage_head, lineage_list)

Christoph Mallon's avatar
Christoph Mallon committed
59
static void *mris_irn_data_init(phase_t *ph, ir_node *irn, void *data)
60
{
Sebastian Hack's avatar
Sebastian Hack committed
61
	mris_irn_t *mi = data ? data : phase_alloc(ph, sizeof(mi[0]));
Sebastian Hack's avatar
Sebastian Hack committed
62
	memset(mi, 0, sizeof(mi[0]));
Sebastian Hack's avatar
Merged    
Sebastian Hack committed
63
	INIT_LIST_HEAD(&mi->lineage_list);
Sebastian Hack's avatar
Sebastian Hack committed
64
	return mi;
65
66
}

Sebastian Hack's avatar
Sebastian Hack committed
67
#if 0
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
static int compute_height(mris_env_t *env, ir_node *irn, unsigned long visited)
{
	mris_irn_t *mi = get_mris_irn(env, irn);

	if(get_irn_visited(irn) >= visited) {
		DBG((env->dbg, LEVEL_3, "\theight of %+F = %d\n", irn, mi->height));
		return mi->height;
	}

	else {
		const ir_edge_t *edge;

		set_irn_visited(irn, visited);
		mi->height  = 0;

		foreach_out_edge(irn, edge) {
			ir_node *dep = get_edge_src_irn(edge);

			if(!is_Block(dep) && get_nodes_block(dep) == env->bl) {
				int dep_height = compute_height(env, dep, visited);
				mi->height     = MAX(mi->height, dep_height);
			}
		}

		mi->height++;
		DBG((env->dbg, LEVEL_3, "\tsetting height of %+F = %d\n", irn, mi->height));
	}

	return mi->height;
}

static void compute_heights(mris_env_t *env)
{
	const ir_edge_t *edge;
	unsigned long visited;

	visited = get_irg_visited(env->irg) + 1;
	set_irg_visited(env->irg, visited);

	foreach_out_edge(env->bl, edge) {
		ir_node *dep = get_edge_src_irn(edge);
		if(to_appear(env, dep))
			compute_height(env, dep, visited);
	}
}
Sebastian Hack's avatar
Sebastian Hack committed
113
#endif
114

Sebastian Hack's avatar
Sebastian Hack committed
115
#define valid_node(env, dep) (to_appear(env, dep) && !be_is_Keep(dep))
116

Sebastian Hack's avatar
Sebastian Hack committed
117
static void grow_all_descendands(mris_env_t *env, ir_node *irn, bitset_t *visited)
118
119
120
{
	const ir_edge_t *edge;

Sebastian Hack's avatar
Sebastian Hack committed
121
	// assert(get_irn_mode(irn) != mode_T);
122
123
124

	foreach_out_edge(irn, edge) {
		ir_node *desc = get_edge_src_irn(edge);
Sebastian Hack's avatar
Sebastian Hack committed
125
		if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
126
			obstack_ptr_grow(&env->obst, desc);
Sebastian Hack's avatar
Sebastian Hack committed
127
			bitset_add_irn(visited, desc);
128
129
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
130
131
132

	foreach_out_edge_kind(irn, edge, EDGE_KIND_DEP) {
		ir_node *desc = get_edge_src_irn(edge);
Sebastian Hack's avatar
Sebastian Hack committed
133
		if(valid_node(env, desc) && !bitset_contains_irn(visited, desc)) {
Sebastian Hack's avatar
Sebastian Hack committed
134
			obstack_ptr_grow(&env->obst, desc);
Sebastian Hack's avatar
Sebastian Hack committed
135
			bitset_add_irn(visited, desc);
Sebastian Hack's avatar
Sebastian Hack committed
136
137
		}
	}
138
139
140
141
}

static ir_node **all_descendants(mris_env_t *env, ir_node *irn)
{
Sebastian Hack's avatar
Sebastian Hack committed
142
	bitset_t *visited = bitset_irg_malloc(env->irg);
143

Sebastian Hack's avatar
Sebastian Hack committed
144
	grow_all_descendands(env, irn, visited);
145

Sebastian Hack's avatar
Sebastian Hack committed
146
#if 0
147
	if(get_irn_mode(irn) == mode_T) {
Matthias Braun's avatar
Matthias Braun committed
148
		const ir_edge_t *edge;
149
150
151
152
153
154
155
156
157
		foreach_out_edge(irn, edge) {
			ir_node *desc = get_edge_src_irn(edge);
			assert(is_Proj(desc) && get_irn_mode(desc) != mode_T);
			grow_all_descendands(env, desc, visited);
		}
	}

	else
		grow_all_descendands(env, irn, visited);
Sebastian Hack's avatar
Sebastian Hack committed
158
159
#endif
	bitset_free(visited);
160
161
162
163
164
165
	obstack_ptr_grow(&env->obst, NULL);
	return obstack_finish(&env->obst);
}

static ir_node *put_lowest_in_front(mris_env_t *env, ir_node **in)
{
Sebastian Hack's avatar
Sebastian Hack committed
166
167
	int lowest_index       = 0;
	unsigned lowest_height = INT_MAX;
168
169
170
	int i;

	for(i = 0; in[i]; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
171
172
173
		unsigned height = get_irn_height(env->heights, in[i]);
		if(height < lowest_height) {
			lowest_height = height;
174
175
176
177
178
179
180
181
182
183
184
185
186
			lowest_index  = i;
		}
	}

	if(i > 0) {
		ir_node *tmp     = in[0];
		in[0]            = in[lowest_index];
		in[lowest_index] = tmp;
	}

	return in[0];
}

Sebastian Hack's avatar
Sebastian Hack committed
187
#if 0
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
static void reaches_walker(mris_env_t *env, ir_node *irn, ir_node *tgt, int *found, unsigned long visited)
{
	if(get_irn_visited(irn) < visited && get_nodes_block(irn) == env->bl) {

		set_irn_visited(irn, visited);

		if(irn == tgt)
			*found = 1;
		else {
			int i, n;

			for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
				ir_node *op = get_irn_n(irn, i);
				if(!*found)
					reaches_walker(env, op, tgt, found, visited);
			}
		}
	}
}

static int reaches(mris_env_t *env, ir_node *src, ir_node *tgt)
{
	int found = 0;
	unsigned long visited = get_irg_visited(env->irg) + 1;

	set_irg_visited(env->irg, visited);
	reaches_walker(env, src, tgt, &found, visited);
	return found;
}
Sebastian Hack's avatar
Sebastian Hack committed
217
#endif
218
219
220
221
222
223

static INLINE ir_node *skip_Projs(ir_node *irn)
{
	return is_Proj(irn) ? skip_Projs(get_Proj_pred(irn)) : irn;
}

Matthias Braun's avatar
Matthias Braun committed
224
#if 0
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
static void replace_tuple_by_repr_proj(mris_env_t *env, ir_node **in)
{
	int i;

	for(i = 0; in[i]; ++i) {
		if(get_irn_mode(in[i]) == mode_T) {
			const ir_edge_t *edge;
			ir_node *proj  = NULL;
			ir_node *first = NULL;

			foreach_out_edge(in[i], edge) {
				ir_node *desc = get_edge_src_irn(edge);

				first = first ? first : desc;
				if(get_irn_mode(desc) == mode_M) {
					proj = desc;
					break;
				}
			}

			proj = proj ? proj : first;
			assert(proj);
			in[i] = proj;
		}
	}
}
Matthias Braun's avatar
Matthias Braun committed
251
#endif
252
253
254

static void lineage_formation(mris_env_t *env)
{
Matthias Braun's avatar
Matthias Braun committed
255
	DEBUG_ONLY(firm_dbg_module_t *dbg = env->dbg);
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
	nodeset *nodes         = new_nodeset(128);

	const ir_edge_t *edge;

	foreach_out_edge(env->bl, edge) {
		ir_node *irn = get_edge_src_irn(edge);
		if(to_appear(env, irn))
			nodeset_insert(nodes, irn);
	}

	while(nodeset_count(nodes) > 0) {
		mris_irn_t *mi;
		ir_node *irn;
		ir_node *highest_node = NULL;
		ir_node *lowest_desc  = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
271
272
		ir_node *start;
		mris_irn_t *start_mi;
273
274
275

		ir_node **in;
		int recompute_height  = 0;
Sebastian Hack's avatar
Sebastian Hack committed
276
		unsigned  curr_height = 0;
277
278
279

		/* search the highest node which is not yet in a lineage. */
		for(irn = nodeset_first(nodes); irn; irn = nodeset_next(nodes)) {
Sebastian Hack's avatar
Sebastian Hack committed
280
281
			unsigned height = get_irn_height(env->heights, irn);
			if(height > curr_height) {
282
				highest_node = irn;
Sebastian Hack's avatar
Sebastian Hack committed
283
				curr_height  = height;
284
285
286
287
			}
		}

		assert(highest_node);
Sebastian Hack's avatar
Sebastian Hack committed
288
		DBG((dbg, LEVEL_2, "highest node is %+F height %d\n", highest_node, get_irn_height(env->heights, highest_node)));
289

Sebastian Hack's avatar
Sebastian Hack committed
290
291
292
		start = highest_node;
		mi = start_mi = get_mris_irn(env, highest_node);

293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
		/* start a lineage beginning with highest_node. */
		mi->lineage_start = highest_node;
		mi->lineage_next  = NULL;
		mi->lineage_end   = NULL;
		list_add(&mi->lineage_list, &env->lineage_head);
		nodeset_remove(nodes, highest_node);

		/*
			put all descendants in an array.
			we also move the lowest descendant in front, so that the other nodes
			are easily accessible as an array, too.
		*/
		in          = all_descendants(env, highest_node);
		lowest_desc = put_lowest_in_front(env, in);

		/* as long as the current highest node has still descendants */
		while(lowest_desc) {
			mris_irn_t *lowest_mi  = get_mris_irn(env, lowest_desc);
			mris_irn_t *highest_mi = get_mris_irn(env, highest_node);
			int highest_is_tuple   = get_irn_mode(highest_node) == mode_T;

			int n_desc;

Sebastian Hack's avatar
Sebastian Hack committed
316
			DBG((dbg, LEVEL_2, "\tlowest descendant %+F height %d\n", lowest_desc, get_irn_height(env->heights, lowest_desc)));
317
318

			/* count the number of all descendants which are not the lowest descendant */
Sebastian Hack's avatar
Sebastian Hack committed
319
			for(n_desc = 0; in[n_desc]; ++n_desc);
320
321
322
323
324
325

			/*
			we insert a CopyKeep node to express the artificial dependencies from the lowest
			descendant to all other descendants.
			*/
			if(n_desc > 1 && !be_is_Keep(lowest_desc)) {
Sebastian Hack's avatar
Sebastian Hack committed
326
				ir_node *op;
327
328
				int i, n;

Sebastian Hack's avatar
Sebastian Hack committed
329
				for(i = 0, n = get_irn_ins_or_deps(lowest_desc); i < n; ++i) {
330
331
					ir_node *cmp;

Sebastian Hack's avatar
Sebastian Hack committed
332
					op  = get_irn_in_or_dep(lowest_desc, i);
333
334
					cmp = highest_is_tuple ? skip_Projs(op) : op;

Sebastian Hack's avatar
Sebastian Hack committed
335
336
					// if(cmp == highest_node)
					if(op == highest_node)
337
338
339
340
341
						break;
				}

				assert(i < n && "could not find operand");

Sebastian Hack's avatar
Sebastian Hack committed
342
343
344
				//replace_tuple_by_repr_proj(env, &in[1]);
				if(!is_Proj(lowest_desc))
					add_irn_dep(lowest_desc, in[1]);
345
346
347
348
349
			}
			obstack_free(&env->obst, in);

			/* if the current lowest node is not yet in a lineage, add it to the current one. */
			if(!lowest_mi->lineage_start) {
Sebastian Hack's avatar
Sebastian Hack committed
350
351
352
353
354
				/* mark the current lowest node as the last one in the lineage. */
				highest_mi->lineage_next = lowest_desc;
				start_mi->lineage_end    = lowest_desc;

				lowest_mi->lineage_start = start;
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
				nodeset_remove(nodes, lowest_desc);
			}

			/* else we cannot extend this lineage, so break. */
			else
				break;

			highest_node = lowest_desc;
			highest_mi   = lowest_mi;

			/* recompute the descendants array and the new lowest descendant. */
			in          = all_descendants(env, highest_node);
			lowest_desc = put_lowest_in_front(env, in);
		}

		/* recompute the heights if desired. */
		if(recompute_height)
Sebastian Hack's avatar
Sebastian Hack committed
372
			heights_recompute(env->heights);
373
374
375
376
377
378
	}
}

static int fuse_two_lineages(mris_env_t *env, mris_irn_t *u, mris_irn_t *v)
{
	mris_irn_t *mi;
Sebastian Hack's avatar
Sebastian Hack committed
379
	ir_node *irn, *last;
380
381
382
383
384
385
386
387
388
389
	ir_node *u_end   = u->lineage_end;
	ir_node *v_start = v->lineage_start;
	ir_node *start   = skip_Projs(v_start);

	if(be_is_Keep(start))
		return 0;

	/* set lineage end of nodes in u to end of v. */
	irn = last = u->lineage_start;
	mi         = get_mris_irn(env, irn);
Sebastian Hack's avatar
Sebastian Hack committed
390
	while(irn && irn != u_end) {
391
392
393
394
395
396
397
		mi = get_mris_irn(env, irn);
		mi->lineage_end = v->lineage_end;
		last = irn;
		irn = mi->lineage_next;
	}

	/* insert a CopyKeep to make lineage v dependent on u. */
Sebastian Hack's avatar
Sebastian Hack committed
398
399
	if(get_irn_ins_or_deps(start) == 0)
		return 0;
400

Sebastian Hack's avatar
Sebastian Hack committed
401
402
403
404
405
	if(get_irn_mode(last) == mode_T) {
		const ir_edge_t *edge;
		foreach_out_edge(last, edge) {
			last = get_edge_src_irn(edge);
			break;
406
407
408
409
		}
	}

	/* irn now points to the last node in lineage u; mi has the info for the node _before_ the terminator of the lineage. */
Sebastian Hack's avatar
Sebastian Hack committed
410
411
412
413
	mi->lineage_next       = v_start;

	/* add a dependency from the first node in v's lineage to the last in u's */
	add_irn_dep(u_end, v_start);
414
415
416

	/* set lineage start of nodes in v to start of u. */
	irn = v->lineage_start;
Sebastian Hack's avatar
Sebastian Hack committed
417
	while(irn && irn != v->lineage_end) {
418
419
420
421
422
		mris_irn_t *mi = get_mris_irn(env, irn);
		mi->lineage_start = u->lineage_start;
		irn = mi->lineage_next;
	}

Sebastian Hack's avatar
Sebastian Hack committed
423
424
	heights_recompute(env->heights);

425
426
427
428
429
430
431
432
433
434
435
436
437
	mi = get_mris_irn(env, v_start);
	list_del(&mi->lineage_list);

	return 1;
}

static void fuse_lineages(mris_env_t *env)
{
	mris_irn_t *u, *v, *tmp1, *tmp2;

again:
	foreach_lineage(env, u, tmp1) {
		foreach_lineage(env, v, tmp2) {
Sebastian Hack's avatar
Sebastian Hack committed
438
439
440
441
442
443
444
445
446
			if(u != v && u->lineage_start && v->lineage_start && u->lineage_end && v->lineage_end
				&& get_nodes_block(u->lineage_start) == get_nodes_block(v->lineage_start)) {
				int uv = heights_reachable_in_block(env->heights, u->lineage_start, v->lineage_end);
				int vu = heights_reachable_in_block(env->heights, v->lineage_start, u->lineage_end);

				if(uv && !vu) {
					if(fuse_two_lineages(env, u, v))
						goto again;
				}
447
448
449
450
451
			}
		}
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
452
453
static mris_env_t *dump_env = NULL;

454
455
456
457
458
static void block_walker(ir_node *bl, void *data)
{
	mris_env_t *env = data;
	env->bl = bl;
	lineage_formation(env);
Sebastian Hack's avatar
Sebastian Hack committed
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
	fuse_lineages(env);
}

static int mris_edge_hook(FILE *F, ir_node *irn)
{
	mris_irn_t *mi = get_mris_irn(dump_env, irn);

	if(mi->lineage_next) {
		fprintf(F, "edge:{sourcename:\"");
		PRINT_NODEID(mi->lineage_next);
		fprintf(F, "\" targetname:\"");
		PRINT_NODEID(irn);
		fprintf(F, "\" color:lilac}\n");
	}
	return 1;
474
475
}

Sebastian Hack's avatar
Sebastian Hack committed
476
477
478
479
480
481
482
483
484
void dump_ir_block_graph_mris(mris_env_t *env, const char *suffix) {
	DUMP_NODE_EDGE_FUNC old = get_dump_node_edge_hook();

	dump_consts_local(0);
	set_dump_node_edge_hook(mris_edge_hook);
	dump_env = env;
	dump_ir_block_graph(env->irg, suffix);
	set_dump_node_edge_hook(old);
}
485
486
487
488
489

mris_env_t *be_sched_mris_preprocess(const be_irg_t *birg)
{
	mris_env_t *env = xmalloc(sizeof(env[0]));

Sebastian Hack's avatar
Sebastian Hack committed
490
	phase_init(&env->ph, "mris", birg->irg, 2 * PHASE_DEFAULT_GROWTH, mris_irn_data_init);
491
492
493
	env->aenv     = birg->main_env->arch_env;
	env->irg      = birg->irg;
	env->visited  = 0;
Sebastian Hack's avatar
Sebastian Hack committed
494
	env->heights  = heights_new(birg->irg);
495
496
497
498
499
500
	INIT_LIST_HEAD(&env->lineage_head);
	FIRM_DBG_REGISTER(env->dbg, "firm.be.sched.mris");
	obstack_init(&env->obst);
	irg_walk_graph(env->irg, firm_clear_link, NULL, NULL);
	irg_block_walk_graph(birg->irg, block_walker, NULL, env);
	obstack_free(&env->obst, NULL);
Sebastian Hack's avatar
Oops    
Sebastian Hack committed
501
	// dump_ir_block_graph_mris(env, "-mris");
502
503
504
505
506
	return env;
}

void be_sched_mris_free(mris_env_t *env)
{
Sebastian Hack's avatar
Merged    
Sebastian Hack committed
507
	phase_free(&env->ph);
Sebastian Hack's avatar
Sebastian Hack committed
508
	heights_free(env->heights);
509
510
	free(env);
}