beraextern.c 21.9 KB
Newer Older
1
2
3
4
5
6
/**
 * Author:      Daniel Grund
 * Date:		17.01.2006
 * Copyright:   (c) Universitaet Karlsruhe
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 *
Daniel Grund's avatar
Daniel Grund committed
7
8
 * Implementation of the RA-Interface for an external, (non-SSA) register allocator.
 *
Daniel Grund's avatar
Daniel Grund committed
9
10
11
12
13
 * The external register allocator is a program:
 *    PROG -i INPUTFILE -o OUTPUTFILE
 *
 *   1) Input file defines the interference graph
 *   2) Output file contains the instructions to perform
Daniel Grund's avatar
:wq    
Daniel Grund committed
14
 *
15

Daniel Grund's avatar
Daniel Grund committed
16
17
18
19

The input file format
----------------------

Daniel Grund's avatar
Daniel Grund committed
20
inputfile	::= regs nodes interf affinities .
Daniel Grund's avatar
Daniel Grund committed
21

Daniel Grund's avatar
Daniel Grund committed
22
regs		::= 'regs' regcount .						// Anzahl der register (0..regcount-1), die zur Verfuegung stehen
Daniel Grund's avatar
Daniel Grund committed
23

Daniel Grund's avatar
Daniel Grund committed
24
nodes		::= 'nodes' '{' node* '}' .					// All nodes in the graph
Daniel Grund's avatar
Daniel Grund committed
25

Daniel Grund's avatar
Daniel Grund committed
26
27
28
29
30
node		::= node-info
			  | node-info '<' reg-nr '>' .				// Reg-nr is present in case of constraints

node-info	::= node-nr spill-costs .

Daniel Grund's avatar
Daniel Grund committed
31
interf		::= 'interferences' '{' i-edge* '}' .		// Interference edges of the graph
Daniel Grund's avatar
Daniel Grund committed
32

Daniel Grund's avatar
Daniel Grund committed
33
i-edge		::= '(' node-nr ',' node-nr ')' .
Daniel Grund's avatar
Daniel Grund committed
34

Daniel Grund's avatar
Daniel Grund committed
35
affinities	::= 'affinities' '{' a-edge* '}' .			// Affinity edges of the graph
Daniel Grund's avatar
Daniel Grund committed
36

Daniel Grund's avatar
Daniel Grund committed
37
a-edge		::= '(' node-nr ',' node-nr ',' weight ')' .
Daniel Grund's avatar
Daniel Grund committed
38

Daniel Grund's avatar
Daniel Grund committed
39
40
41

weight, regcount, node-nr ::= int32 .
spill-costs ::= int32 .									// negative spill costs indicate unspillable
Daniel Grund's avatar
Daniel Grund committed
42
43
44
45

The output file format
-----------------------

Daniel Grund's avatar
Daniel Grund committed
46
outputfile	::= spills | allocs .
Daniel Grund's avatar
Daniel Grund committed
47

Daniel Grund's avatar
Daniel Grund committed
48
spills		::= 'spills' node-nr+ .
Daniel Grund's avatar
Daniel Grund committed
49

Daniel Grund's avatar
Daniel Grund committed
50
allocs		::= 'allocs' alloc* .
Daniel Grund's avatar
:wq    
Daniel Grund committed
51

Daniel Grund's avatar
Daniel Grund committed
52
alloc		::= node-nr reg-nr .
Daniel Grund's avatar
:wq    
Daniel Grund committed
53

Daniel Grund's avatar
Daniel Grund committed
54
55

******** End of file format docu ********/
Daniel Grund's avatar
Daniel Grund committed
56

57
58
59
60
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

Michael Beck's avatar
Michael Beck committed
61
62
63
64
65
#ifdef HAVE_MALLOC_H
 #include <malloc.h>
#endif
#ifdef HAVE_ALLOCA_H
 #include <alloca.h>
Daniel Grund's avatar
Daniel Grund committed
66
67
68
69
#endif

#include <stdio.h>
#include <stdlib.h>
Daniel Grund's avatar
Daniel Grund committed
70
#include <limits.h>
Daniel Grund's avatar
Daniel Grund committed
71
72
73
74
#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
#endif
Daniel Grund's avatar
Daniel Grund committed
75

Daniel Grund's avatar
Daniel Grund committed
76
#include "set.h"
77
#include "pset.h"
Daniel Grund's avatar
Daniel Grund committed
78
#include "pmap.h"
Daniel Grund's avatar
Daniel Grund committed
79
#include "bitset.h"
80

Daniel Grund's avatar
Daniel Grund committed
81
#include "irprintf_t.h"
82
83
84
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
Daniel Grund's avatar
Daniel Grund committed
85
#include "iredges_t.h"
Daniel Grund's avatar
Daniel Grund committed
86
#include "irdom_t.h"
87
88
89
#include "phiclass.h"

#include "beraextern.h"
Daniel Grund's avatar
Daniel Grund committed
90
#include "beabi.h"
91
92
#include "bearch.h"
#include "benode_t.h"
Daniel Grund's avatar
Daniel Grund committed
93
#include "beirgmod.h"
Daniel Grund's avatar
Daniel Grund committed
94
#include "besched_t.h"
95
#include "beutil.h"
Kimon Hoffmann's avatar
Kimon Hoffmann committed
96
#include "belive_t.h"
97
#include "beinsn_t.h"
98

99
#include "bessadestrsimple.h"
Daniel Grund's avatar
Daniel Grund committed
100

101
#define DBG_LEVEL 2
Daniel Grund's avatar
Daniel Grund committed
102

Daniel Grund's avatar
Daniel Grund committed
103
104
105
/**
 * Environment with all the needed stuff
 */
106
107
108
typedef struct _be_raext_env_t {
	arch_env_t *aenv;
	const arch_register_class_t *cls;
109
	be_irg_t *birg;
110
111
	ir_graph *irg;

Daniel Grund's avatar
Daniel Grund committed
112
	FILE *f;				/**< file handle used for out- and input file */
113
	set *vars;				/**< contains all be_var_info_t */
Daniel Grund's avatar
Daniel Grund committed
114
	int n_cls_vars;			/**< length of the array cls_vars */
115
	be_var_info_t **cls_vars;	/**< only the var_infos for current cls. needed for double iterating */
116
	DEBUG_ONLY(firm_dbg_module_t *dbg;)
117
118
} be_raext_env_t;

Daniel Grund's avatar
Daniel Grund committed
119
120
121
122
123
124
125
126
127
128
129
130
131


/******************************************************************************
    _    _      _
   | |  | |    | |
   | |__| | ___| |_ __   ___ _ __ ___
   |  __  |/ _ \ | '_ \ / _ \ '__/ __|
   | |  | |  __/ | |_) |  __/ |  \__ \
   |_|  |_|\___|_| .__/ \___|_|  |___/
                 | |
                 |_|
 *****************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
132
133
134
135

#define pset_foreach(pset, irn)  for(irn=pset_first(pset); irn; irn=pset_next(pset))
#define set_foreach(set, e)  for(e=set_first(set); e; e=set_next(set))

Daniel Grund's avatar
Daniel Grund committed
136
137
138
139
140
/**
 * Checks if _the_ result of the irn belongs to the
 * current register class (raenv->cls)
 * NOTE: Only the first result is checked.
 */
141
142
#define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)

Daniel Grund's avatar
Daniel Grund committed
143
144
static INLINE ir_node *get_first_non_phi(pset *s) {
	ir_node *irn;
Daniel Grund's avatar
Daniel Grund committed
145

Daniel Grund's avatar
Daniel Grund committed
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
	pset_foreach(s, irn)
		if (!is_Phi(irn)) {
			pset_break(s);
			return irn;
		}

	assert(0 && "There must be a non-phi-irn in this");
	return NULL;
}

static INLINE ir_node *get_first_phi(pset *s) {
	ir_node *irn;

	pset_foreach(s, irn)
		if (is_Phi(irn)) {
			pset_break(s);
			return irn;
		}
164

Daniel Grund's avatar
Daniel Grund committed
165
166
	assert(0 && "There must be a phi in this");
	return NULL;
167
168
}

169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
static int get_loop_weight(ir_node *irn) {
	int cost = 0;
	ir_loop *loop = get_irn_loop(get_nodes_block(irn));

	if (loop) {
		int d = get_loop_depth(loop);
		cost = d*d;
	}
	return cost+1;
}

#define get_const_weight(irn) (1)

#define get_spill_weight(irn)    get_loop_weight(irn)
#define get_reload_weight(irn)   get_loop_weight(irn)
#define get_affinity_weight(irn) get_loop_weight(irn)

186
187
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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
static void handle_constraints_insn(be_raext_env_t *env, be_insn_t *insn)
{
	ir_node *bl = get_nodes_block(insn->irn);
	int i;

	for(i = 0; i < insn->use_start; ++i) {
		be_operand_t *op = &insn->ops[i];

		if(op->has_constraints) {
			ir_node *cpy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
			sched_add_before(insn->next_insn, cpy);
			edges_reroute(op->carrier, cpy, env->irg);
		}
	}

	for(i = insn->use_start; i < insn->n_ops; ++i) {
		be_operand_t *op = &insn->ops[i];

		if(op->has_constraints) {
			ir_node *cpy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
			sched_add_before(insn->irn, cpy);
			set_irn_n(insn->irn, op->pos, cpy);
			be_set_constr_limited(cpy, BE_OUT_POS(0), &op->req);
		}
	}
}

static void handle_constraints_block(ir_node *bl, void *data)
{
	be_raext_env_t *raenv = data;
	int active            = bl != get_irg_start_block(raenv->irg);

	ir_node *irn;
	be_insn_env_t ie;
	struct obstack obst;

Sebastian Hack's avatar
Sebastian Hack committed
233
234
235
	ie.cls           = raenv->cls;
	ie.aenv          = raenv->aenv;
	ie.obst          = &obst;
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
	ie.ignore_colors = NULL;
	obstack_init(&obst);

	irn = sched_first(bl);
	while(!sched_is_end(irn)) {
		be_insn_t *insn = be_scan_insn(&ie, irn);

		if(insn->has_constraints)
			handle_constraints_insn(raenv, insn);

		if(be_is_Barrier(irn))
			active = !active;

		irn = insn->next_insn;
		obstack_free(&obst, insn);
	}
}
253
254

static void handle_constraints(be_raext_env_t *raenv) {
255
	irg_block_walk_graph(raenv->irg, NULL, handle_constraints_block, raenv);
256
257
}

Daniel Grund's avatar
Daniel Grund committed
258

Daniel Grund's avatar
Daniel Grund committed
259

Daniel Grund's avatar
Daniel Grund committed
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274

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


static void extract_vars_of_cls(be_raext_env_t *raenv) {
	int count = 0;
275
	be_var_info_t *vi;
Daniel Grund's avatar
Daniel Grund committed
276

Michael Beck's avatar
Michael Beck committed
277
	raenv->cls_vars = xmalloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars));
Daniel Grund's avatar
Daniel Grund committed
278
279
	assert(raenv->cls_vars);

Daniel Grund's avatar
Daniel Grund committed
280
	set_foreach(raenv->vars, vi)
Daniel Grund's avatar
Daniel Grund committed
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
		if (is_res_in_reg_class(get_first_non_phi(vi->values)))
			raenv->cls_vars[count++] = vi;

	raenv->cls_vars = realloc(raenv->cls_vars, count * sizeof(*raenv->cls_vars));
	assert(raenv->cls_vars);

	raenv->n_cls_vars = count;
}


/**
 * Check if node irn has a limited-constraint at position pos.
 * If yes, dump it to FILE raenv->f
 */
static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
	bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
	arch_register_req_t req;

	arch_get_register_req(raenv->aenv, &req, irn, pos);
	if (arch_register_req_is(&req, limited)) {
		int reg_nr;
		req.limited(req.limited_env, bs);
		reg_nr = bitset_next_set(bs, 0);
		fprintf(raenv->f, "<%d>", reg_nr);
		assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
	}
}

Daniel Grund's avatar
Daniel Grund committed
309
310
#define UNSPILLABLE -1

311
static INLINE int get_spill_costs(be_raext_env_t *raenv, be_var_info_t *vi) {
Daniel Grund's avatar
Daniel Grund committed
312
	ir_node *irn;
313
	int c_spills=0, c_reloads=0;
Daniel Grund's avatar
Daniel Grund committed
314
315

	pset_foreach(vi->values, irn) {
316
		if (arch_irn_is(raenv->aenv, irn, ignore) || be_is_Reload(irn)) {
Daniel Grund's avatar
Daniel Grund committed
317
			pset_break(vi->values);
Daniel Grund's avatar
Daniel Grund committed
318
			return UNSPILLABLE;
Daniel Grund's avatar
Daniel Grund committed
319
320
		}

Daniel Grund's avatar
Daniel Grund committed
321
322
323
324
325
		if (is_Phi(irn)) {
			/* number of reloads is the number of non-phi uses of all values of this var */
			const ir_edge_t *edge;
			foreach_out_edge(irn, edge)
				if (!is_Phi(edge->src))
326
					c_reloads += get_reload_weight(edge->src);
Daniel Grund's avatar
Daniel Grund committed
327
328
		} else {
			/* number of spills is the number of non-phi values for this var */
329
			c_spills += get_spill_weight(irn);
Daniel Grund's avatar
Daniel Grund committed
330
331
332
		}
	}

333
	return c_spills + c_reloads;
Daniel Grund's avatar
Daniel Grund committed
334
}
Daniel Grund's avatar
Daniel Grund committed
335
336
337
338
339
340
341
342

static void dump_nodes(be_raext_env_t *raenv) {
	FILE *f = raenv->f;
	int i;

	fprintf(f, "\nnodes {\n");

	for (i=0; i<raenv->n_cls_vars; ++i) {
343
		be_var_info_t *vi = raenv->cls_vars[i];
Daniel Grund's avatar
Daniel Grund committed
344
345
346
347

		if (vi->var_nr == SET_REMOVED)
			continue;

Daniel Grund's avatar
Daniel Grund committed
348
		fprintf(f, "%d %d", vi->var_nr, get_spill_costs(raenv, vi));
Daniel Grund's avatar
Daniel Grund committed
349
		dump_constraint(raenv, get_first_non_phi(vi->values), -1);
Daniel Grund's avatar
Daniel Grund committed
350
351
352
353
		fprintf(f, "\n");
	}

	fprintf(f, "}\n");
Daniel Grund's avatar
Daniel Grund committed
354
	fflush(f);
Daniel Grund's avatar
Daniel Grund committed
355
356
357
358
359
}


static void dump_interferences(be_raext_env_t *raenv) {
	int i,o;
360
	be_var_info_t *vi1, *vi2;
Daniel Grund's avatar
Daniel Grund committed
361
362
	ir_node *irn1, *irn2;
	FILE *f = raenv->f;
363
	be_lv_t *lv = raenv->birg->lv;
Daniel Grund's avatar
Daniel Grund committed
364
365
366
367
368
369

	fprintf(f, "\ninterferences {\n");

	for (i=0; i<raenv->n_cls_vars; ++i) {
		vi1 = raenv->cls_vars[i];

Daniel Grund's avatar
Daniel Grund committed
370
371
372
		if (vi1->var_nr == SET_REMOVED)
			continue;

Daniel Grund's avatar
Daniel Grund committed
373
374
375
		for (o=i+1; o<raenv->n_cls_vars; ++o) {
			vi2 = raenv->cls_vars[o];

Daniel Grund's avatar
Daniel Grund committed
376
377
378
			if (vi2->var_nr == SET_REMOVED)
				continue;

Daniel Grund's avatar
Daniel Grund committed
379
380
			pset_foreach(vi1->values, irn1)
				pset_foreach(vi2->values, irn2)
381
					if (values_interfere(lv, irn1, irn2)) {
Daniel Grund's avatar
Daniel Grund committed
382
383
						pset_break(vi1->values);
						pset_break(vi2->values);
Daniel Grund's avatar
Daniel Grund committed
384
						fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
Daniel Grund's avatar
Daniel Grund committed
385
						goto NextVar;
Daniel Grund's avatar
Daniel Grund committed
386
					}
Daniel Grund's avatar
Daniel Grund committed
387
388

NextVar: ;
Daniel Grund's avatar
Daniel Grund committed
389
390
391
392
393
394
395
		}
	}
	fprintf(f, "}\n");
}

static void dump_affinities_walker(ir_node *irn, void *env) {
	be_raext_env_t *raenv = env;
Daniel Grund's avatar
Daniel Grund committed
396
397
	arch_register_req_t req;
	int pos, max;
398
	be_var_info_t *vi1, *vi2;
Daniel Grund's avatar
Daniel Grund committed
399

400
	if (arch_get_irn_reg_class(raenv->aenv, irn, -1) != raenv->cls || arch_irn_is(raenv->aenv, irn, ignore))
Daniel Grund's avatar
Daniel Grund committed
401
402
		return;

403
	vi1 = be_get_var_info(irn);
Daniel Grund's avatar
Daniel Grund committed
404
405

	/* copies have affinities */
Christian Würdig's avatar
Christian Würdig committed
406
	if (arch_irn_class_is(raenv->aenv, irn, copy)) {
407
		ir_node *other = be_get_Copy_op(irn);
Daniel Grund's avatar
Daniel Grund committed
408

409
		if (! arch_irn_is(raenv->aenv, other, ignore)) {
410
			vi2 = be_get_var_info(other);
Daniel Grund's avatar
Daniel Grund committed
411

412
			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
Daniel Grund's avatar
Daniel Grund committed
413
		}
Daniel Grund's avatar
Daniel Grund committed
414
415
416
417
418
419
	}


	/* should_be_equal constraints are affinites */
	for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
		arch_get_register_req(raenv->aenv, &req, irn, pos);
Daniel Grund's avatar
Daniel Grund committed
420

421
		if (arch_register_req_is(&req, should_be_same) && arch_irn_is(raenv->aenv, req.other_same, ignore)) {
422
			vi2 = be_get_var_info(req.other_same);
Daniel Grund's avatar
Daniel Grund committed
423

424
			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
Daniel Grund's avatar
Daniel Grund committed
425
		}
Daniel Grund's avatar
Daniel Grund committed
426
427
428
429
430
	}
}


static void dump_affinities(be_raext_env_t *raenv) {
Kimon Hoffmann's avatar
Kimon Hoffmann committed
431
	fprintf(raenv->f, "\naffinities {\n");
Daniel Grund's avatar
Daniel Grund committed
432
433
434
435
436
437
438
439
440
441
442
443
444
	irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv);
	fprintf(raenv->f, "}\n");
}

/**
 * Dump all information needed by the external
 * register allocator to a single file.
 */
static void dump_to_file(be_raext_env_t *raenv, char *filename) {
	FILE *f;

	if (!(f = fopen(filename, "wt"))) {
		fprintf(stderr, "Could not open file %s for writing\n", filename);
Daniel Grund's avatar
Daniel Grund committed
445
		assert(0);
Daniel Grund's avatar
Daniel Grund committed
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
		exit(0xdeadbeef);
	}
	raenv->f = f;

	/* dump register info */
	fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));

	/* dump the interference graph */
	dump_nodes(raenv);
	dump_interferences(raenv);
	dump_affinities(raenv);

	fclose(f);
}

/******************************************************************************
    ______                     _
   |  ____|                   | |
   | |__  __  _____  ___ _   _| |_ ___
   |  __| \ \/ / _ \/ __| | | | __/ _ \
   | |____ >  <  __/ (__| |_| | ||  __/
   |______/_/\_\___|\___|\__,_|\__\___|
 *****************************************************************************/

/**
 * Execute the external register allocator specified in the
 * firm-option firm.be.ra.ext.callee
 */
static void execute(char *prog_to_call, char *out_file, char *result_file) {
	char cmd_line[1024];
	int ret_status;

Daniel Grund's avatar
Daniel Grund committed
478
	snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file);
479
	cmd_line[sizeof(cmd_line) - 1] = '\0';
Daniel Grund's avatar
Daniel Grund committed
480
481
482

	ret_status = system(cmd_line);
	assert(ret_status != -1 && "Invokation of external register allocator failed");
Daniel Grund's avatar
Daniel Grund committed
483
	assert(ret_status == 0 && "External register allocator is unhappy with sth.");
Daniel Grund's avatar
Daniel Grund committed
484
485
}

Daniel Grund's avatar
Daniel Grund committed
486
487
488
489
490
491
492
493
494
495
496
/******************************************************************************
                         _         _____                 _ _
       /\               | |       |  __ \               | | |
      /  \   _ __  _ __ | |_   _  | |__) |___  ___ _   _| | |_
     / /\ \ | '_ \| '_ \| | | | | |  _  // _ \/ __| | | | | __|
    / ____ \| |_) | |_) | | |_| | | | \ \  __/\__ \ |_| | | |_
   /_/    \_\ .__/| .__/|_|\__, | |_|  \_\___||___/\__,_|_|\__|
            | |   | |       __/ |
            |_|   |_|      |___/
 *****************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
497
498
499
500
/**
 * Spill a variable and add reloads before all uses.
 */
static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) {
501
	be_var_info_t *vi = be_var_find(raenv->vars, var_nr);
Daniel Grund's avatar
Daniel Grund committed
502
	ir_node *spill=NULL, *ctx, *irn;
503
	ir_mode *mode;
Daniel Grund's avatar
Daniel Grund committed
504
	const ir_edge_t *edge, *ne;
Daniel Grund's avatar
Daniel Grund committed
505
506
	pset *spills  = pset_new_ptr(4);	/* the spills of this variable */
	pset *reloads = pset_new_ptr(4);	/* the reloads of this variable */
507
508
	be_lv_t *lv = raenv->birg->lv;
	be_dom_front_info_t *dom_front = raenv->birg->dom_front;
Daniel Grund's avatar
Daniel Grund committed
509
	int new_size, n_spills, n_reloads;
Daniel Grund's avatar
Daniel Grund committed
510

Daniel Grund's avatar
Daniel Grund committed
511
512
	assert(vi && "Variable nr does not exist!");
	assert(pset_count(vi->values) && "There are no values associated to this variable");
Daniel Grund's avatar
Daniel Grund committed
513

Daniel Grund's avatar
Daniel Grund committed
514
515
516
517
518
519
520
521
522
	/* the spill context is set to an arbitrary node of the phi-class,
	 * or the node itself if it is not member of a phi class
	 */
	if (pset_count(vi->values) == 1)
		ctx = get_first_non_phi(vi->values);
	else
		ctx = get_first_phi(vi->values);

	DBG((raenv->dbg, LEVEL_2, "Spill context: %+F\n", ctx));
Daniel Grund's avatar
Daniel Grund committed
523

Daniel Grund's avatar
Daniel Grund committed
524
525
	/* for each value of this variable insert the spills */
	pset_foreach(vi->values, irn) {
Daniel Grund's avatar
Daniel Grund committed
526
527
		if (is_Phi(irn)) {
			sched_remove(irn);
Daniel Grund's avatar
Daniel Grund committed
528
			continue;
Daniel Grund's avatar
Daniel Grund committed
529
		}
Daniel Grund's avatar
Daniel Grund committed
530

Daniel Grund's avatar
Daniel Grund committed
531
		/* all ordinary nodes must be spilled */
Daniel Grund's avatar
Daniel Grund committed
532
		DBG((raenv->dbg, LEVEL_2, "  spilling %+F\n", irn));
Matthias Braun's avatar
Matthias Braun committed
533
		spill = be_spill(raenv->aenv, irn);
Daniel Grund's avatar
Daniel Grund committed
534
535
536

		/* remember the spill */
		pset_insert_ptr(spills, spill);
Daniel Grund's avatar
Daniel Grund committed
537
538
	}

Daniel Grund's avatar
Daniel Grund committed
539
	assert(spill && "There must be at least one non-phi-node");
540

541
	mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
542

Daniel Grund's avatar
Daniel Grund committed
543
544
	/* insert reloads and wire them arbitrary*/
	pset_foreach(vi->values, irn)
Daniel Grund's avatar
Daniel Grund committed
545
		foreach_out_edge_safe(irn, edge, ne) {
Daniel Grund's avatar
Daniel Grund committed
546
			ir_node *reload, *src = edge->src;
Daniel Grund's avatar
Daniel Grund committed
547
			if (is_Phi(src) || be_is_Spill(src))
Daniel Grund's avatar
Daniel Grund committed
548
				continue;
Daniel Grund's avatar
Daniel Grund committed
549

Daniel Grund's avatar
Daniel Grund committed
550
			/* all real uses must be reloaded */
Daniel Grund's avatar
Daniel Grund committed
551
			DBG((raenv->dbg, LEVEL_2, "  reloading before %+F\n", src));
552
553
			reload = be_reload(raenv->aenv, raenv->cls, edge->src, mode, spill);
			set_irn_n(edge->src, edge->pos, reload);
Daniel Grund's avatar
Daniel Grund committed
554

Daniel Grund's avatar
Daniel Grund committed
555
556
			/* remember the reload */
			pset_insert_ptr(reloads, reload);
Daniel Grund's avatar
Daniel Grund committed
557
558
		}

Daniel Grund's avatar
Daniel Grund committed
559
	/* correct the reload->spill pointers... */
560
	be_ssa_constr_set(dom_front, lv, spills);
Daniel Grund's avatar
Daniel Grund committed
561

Daniel Grund's avatar
Daniel Grund committed
562

Daniel Grund's avatar
Daniel Grund committed
563
564
565
566
567
568
569
	/****** correct the variable <--> values mapping: ******
	 *
	 *  - if we had a phi class it gets split into several new variables
	 *  - all reloads are new variables
	 */
	n_spills = pset_count(spills);
	n_reloads = pset_count(reloads);
Daniel Grund's avatar
Daniel Grund committed
570

Daniel Grund's avatar
Daniel Grund committed
571
572
573
574
	/* first make room for new pointers in the cls_var array */
	new_size = raenv->n_cls_vars + n_reloads + ((n_spills>1) ? n_spills : 0);
	raenv->cls_vars = realloc(raenv->cls_vars, (new_size) * sizeof(*raenv->cls_vars));
	assert(raenv->cls_vars && "Out of mem!?");
Daniel Grund's avatar
Daniel Grund committed
575

Daniel Grund's avatar
Daniel Grund committed
576
577
578
579
	/* if we had a real phi-class, we must... */
	if (pset_count(spills) > 1) {
		/* ...remove the old variable corresponding to the phi class */
		vi->var_nr = SET_REMOVED;
Daniel Grund's avatar
Daniel Grund committed
580

Daniel Grund's avatar
Daniel Grund committed
581
582
		/* ...add new vars for each non-phi-member */
		pset_foreach(spills, irn) {
583
			ir_node *spilled = get_irn_n(irn, be_pos_Spill_val);
584
			raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(spilled), spilled);
Daniel Grund's avatar
Daniel Grund committed
585
		}
Daniel Grund's avatar
Daniel Grund committed
586
587
588
	}

	/* add new variables for all reloads */
Daniel Grund's avatar
Daniel Grund committed
589
590
	pset_foreach(reloads, irn) {
		assert(get_irn_node_nr(irn) != 1089);
591
		raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(irn), irn);
Daniel Grund's avatar
Daniel Grund committed
592
	}
Daniel Grund's avatar
Daniel Grund committed
593

Daniel Grund's avatar
Daniel Grund committed
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
	del_pset(spills);
	del_pset(reloads);
}

#define INVALID_FILE_FORMAT assert(0 && "Invalid file format.")
#define BUFLEN 32
#define BUFCONV " %32s "

/**
 * Read in the actions performed by the external allocator.
 * Apply these transformations to the irg.
 * @return 1 if an allocation was read in. 0 otherwise.
 */
static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
	FILE *f;
	char buf[BUFLEN];
	int is_allocation = 0;

	if (!(f = fopen(filename, "rt"))) {
		fprintf(stderr, "Could not open file %s for reading\n", filename);
Daniel Grund's avatar
Daniel Grund committed
614
		assert(0);
Daniel Grund's avatar
Daniel Grund committed
615
		exit(0xdeadbeef);
Daniel Grund's avatar
Daniel Grund committed
616
	}
Daniel Grund's avatar
Daniel Grund committed
617
	raenv->f = f;
Daniel Grund's avatar
Daniel Grund committed
618

Daniel Grund's avatar
Daniel Grund committed
619
620
621
	/* read the action */
	if (fscanf(f, BUFCONV, buf) != 1)
		INVALID_FILE_FORMAT;
Daniel Grund's avatar
Daniel Grund committed
622

Daniel Grund's avatar
Daniel Grund committed
623
624
625
626
627
628
	/* do we spill */
	if (!strcmp(buf, "spills")) {
		int var_nr;
		while (fscanf(f, " %d ", &var_nr) == 1)
			var_add_spills_and_reloads(raenv, var_nr);
	} else
Daniel Grund's avatar
Daniel Grund committed
629

Daniel Grund's avatar
Daniel Grund committed
630
631
632
633
634
635
	/* or do we allocate */
	if (!strcmp(buf, "allocs")) {
		int var_nr, reg_nr;

		is_allocation = 1;
		while (fscanf(f, " %d %d ", &var_nr, &reg_nr) == 2) {
Daniel Grund's avatar
Daniel Grund committed
636
			ir_node *irn;
637
			pset *vals = be_get_var_values(raenv->vars, var_nr);
Daniel Grund's avatar
Daniel Grund committed
638

Daniel Grund's avatar
Daniel Grund committed
639
			assert(vals && "Variable nr does not exist!");
Daniel Grund's avatar
Daniel Grund committed
640
			pset_foreach(vals, irn)
Daniel Grund's avatar
Daniel Grund committed
641
				arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, reg_nr));
Daniel Grund's avatar
Daniel Grund committed
642
		}
Daniel Grund's avatar
Daniel Grund committed
643
644
	} else
		INVALID_FILE_FORMAT;
Daniel Grund's avatar
Daniel Grund committed
645
646
647
648
649
650

	if (!feof(f))
		INVALID_FILE_FORMAT;

	fclose(f);

Daniel Grund's avatar
Daniel Grund committed
651
	return is_allocation;
Daniel Grund's avatar
Daniel Grund committed
652
653
}

Daniel Grund's avatar
Daniel Grund committed
654
655
static void check_allocation(be_raext_env_t *raenv) {
	int i, o;
656
	be_lv_t *lv = raenv->birg->lv;
Daniel Grund's avatar
Daniel Grund committed
657
658

	for (i=0; i<raenv->n_cls_vars; ++i) {
659
		be_var_info_t *vi1 = raenv->cls_vars[i];
Daniel Grund's avatar
Daniel Grund committed
660
661
662
663
664

		if (vi1->var_nr == SET_REMOVED)
			continue;

		for (o=0; o<i; ++o) {
665
			be_var_info_t *vi2 = raenv->cls_vars[o];
Daniel Grund's avatar
Daniel Grund committed
666
667
668
669
670
671
672
			ir_node *irn1, *irn2;

			if (vi2->var_nr == SET_REMOVED)
				continue;

			pset_foreach(vi1->values, irn1)
				pset_foreach(vi2->values, irn2)
673
					if (values_interfere(lv, irn1, irn2) && arch_get_irn_register(raenv->aenv, irn1) == arch_get_irn_register(raenv->aenv, irn2)) {
Daniel Grund's avatar
Daniel Grund committed
674
						dump_ir_block_graph_sched(raenv->irg, "ERROR");
Sebastian Hack's avatar
Sebastian Hack committed
675
						ir_fprintf(stdout, "SSA values %+F and %+F interfere. They belong to variable %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr);
Daniel Grund's avatar
Daniel Grund committed
676
677
678
679
680
681
						assert(0 && "ERROR graph dumped");
					}
		}
	}
}

Daniel Grund's avatar
Daniel Grund committed
682
683
684
685
686
687
688
689
/******************************************************************************
    __  __       _
   |  \/  |     (_)
   | \  / | __ _ _ _ __
   | |\/| |/ _` | | '_ \
   | |  | | (_| | | | | |
   |_|  |_|\__,_|_|_| |_|
 *****************************************************************************/
Daniel Grund's avatar
Daniel Grund committed
690

Daniel Grund's avatar
Daniel Grund committed
691
692
693
/**
 * Default values for options
 */
Daniel Grund's avatar
Daniel Grund committed
694
static char callee[128] = "\"E:/user/kimohoff/public/register allocator\"";
Daniel Grund's avatar
Daniel Grund committed
695
//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
Daniel Grund's avatar
Daniel Grund committed
696
697


698
699
700
701
702
703
704
705
706
/**
 * Allocate registers with an external program using a text-file interface.
 *
 * Do some computations (SSA-destruction and mapping of values--vars)
 * Write file
 * Execute external program
 * Read in results and apply them
 *
 */
707
708
709
static be_ra_timer_t *be_ra_extern_main(be_irg_t *birg) {
	be_main_env_t *env = birg->main_env;
	ir_graph *irg = birg->irg;
Sebastian Hack's avatar
Sebastian Hack committed
710

Daniel Grund's avatar
Daniel Grund committed
711
 	be_raext_env_t raenv;
712
713
	int clsnr, clss;

714
715
	be_assure_dom_front(birg);
	be_assure_liveness(birg);
Daniel Grund's avatar
Daniel Grund committed
716
	edges_assure(irg);
Daniel Grund's avatar
Daniel Grund committed
717

Daniel Grund's avatar
Daniel Grund committed
718
	raenv.irg      = irg;
719
	raenv.birg     = birg;
Daniel Grund's avatar
Daniel Grund committed
720
	raenv.aenv     = env->arch_env;
Christian Würdig's avatar
Christian Würdig committed
721
	FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern");
Daniel Grund's avatar
Daniel Grund committed
722

723
	/* Insert copies for constraints */
Sebastian Hack's avatar
Sebastian Hack committed
724
725
726
727
728
	for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
		raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
		handle_constraints(&raenv);
	}

Christian Würdig's avatar
Christian Würdig committed
729
	be_dump(irg, "-extern-constr", dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
730

Daniel Grund's avatar
Daniel Grund committed
731
	/* SSA destruction respectively transformation into "Conventional SSA" */
732
	raenv.vars = be_ssa_destr_simple(irg, env->arch_env);
Christian Würdig's avatar
Christian Würdig committed
733
	be_dump(irg, "-extern-ssadestr", dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
734

Daniel Grund's avatar
Daniel Grund committed
735

736
737
	/* For all register classes */
	for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
Daniel Grund's avatar
Daniel Grund committed
738
		int done, round = 1;
Daniel Grund's avatar
Daniel Grund committed
739
		char out[256], in[256];
740
741
742

		raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);

Daniel Grund's avatar
Daniel Grund committed
743
		extract_vars_of_cls(&raenv);
744

Daniel Grund's avatar
Daniel Grund committed
745
746
747
748
		do {
			ir_snprintf(out, sizeof(out), "%F-%s-%d.ra", irg, raenv.cls->name, round);
			ir_snprintf(in, sizeof(in), "%F-%s-%d.ra.res", irg, raenv.cls->name, round);

Daniel Grund's avatar
Daniel Grund committed
749
750
			be_liveness(irg);

Daniel Grund's avatar
Daniel Grund committed
751
752
753
			dump_to_file(&raenv, out);
			execute(callee, out, in);
			done = read_and_apply_results(&raenv, in);
754
			be_abi_fix_stack_nodes(birg->abi, birg->lv);
Daniel Grund's avatar
Daniel Grund committed
755
756

			ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round);
Christian Würdig's avatar
Christian Würdig committed
757
			be_dump(irg, in, dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
758
759
760

			round++;
		} while (!done);
761

Daniel Grund's avatar
Daniel Grund committed
762
763
		check_allocation(&raenv);

Daniel Grund's avatar
Daniel Grund committed
764
		free(raenv.cls_vars);
765
	}
Daniel Grund's avatar
Daniel Grund committed
766

Christian Würdig's avatar
Christian Würdig committed
767
	be_dump(irg, "-extern-alloc", dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
768

Daniel Grund's avatar
Daniel Grund committed
769
	/* Clean up */
770
	free_ssa_destr_simple(raenv.vars);
771
772

	be_invalidate_liveness(birg);
773
774

	return NULL;
775
}
Daniel Grund's avatar
Daniel Grund committed
776
777
778
779
780
781
782
783
784
785
786
787
788
789

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

#ifdef WITH_LIBCORE

790

Kimon Hoffmann's avatar
Kimon Hoffmann committed
791
static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = {
792
	{ "simple",     (int (*)(void)) be_ssa_destr_simple }, /* TODO make (void*) casts nicer */
Daniel Grund's avatar
Daniel Grund committed
793
794
795
	{ NULL,      NULL }
};

Matthias Braun's avatar
Matthias Braun committed
796
797
static set* (*ssa_destr)(ir_graph*,const arch_env_t*) = be_ssa_destr_simple;

Kimon Hoffmann's avatar
Kimon Hoffmann committed
798
static lc_opt_enum_func_ptr_var_t ssa_destr_var = {
799
	 (int (**)(void)) &ssa_destr, ssa_destr_items
Daniel Grund's avatar
Daniel Grund committed
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
};

static const lc_opt_table_entry_t be_ra_extern_options[] = {
	LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var),
	LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)),
	{ NULL }
};

static void be_ra_extern_register_options(lc_opt_entry_t *root) {
	lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext");

	lc_opt_add_table(grp, be_ra_extern_options);
}

#endif /* WITH_LIBCORE */

const be_ra_t be_ra_external_allocator = {
#ifdef WITH_LIBCORE
	be_ra_extern_register_options,
#endif
	be_ra_extern_main
};