beraextern.c 28.8 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

Daniel Grund's avatar
Daniel Grund committed
98
99
#define DBG_LEVEL 2

Daniel Grund's avatar
Daniel Grund committed
100
101
typedef struct _var_info_t var_info_t;

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

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

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


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

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

#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
135
136
137
138
139
/**
 * Checks if _the_ result of the irn belongs to the
 * current register class (raenv->cls)
 * NOTE: Only the first result is checked.
 */
140
141
#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
142
143
static INLINE ir_node *get_first_non_phi(pset *s) {
	ir_node *irn;
Daniel Grund's avatar
Daniel Grund committed
144

Daniel Grund's avatar
Daniel Grund committed
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
	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;
		}
163

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

168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
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)

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
/******************************************************************************
    _____                _            _____            _
   / ____|              | |          / ____|          (_)
  | |     ___  _ __  ___| |_ _ __   | |     ___  _ __  _  ___  ___
  | |    / _ \| '_ \/ __| __| '__|  | |    / _ \| '_ \| |/ _ \/ __|
  | |___| (_) | | | \__ \ |_| |     | |___| (_) | |_) | |  __/\__ \
   \_____\___/|_| |_|___/\__|_|      \_____\___/| .__/|_|\___||___/
                                                | |
                                                |_|
 *****************************************************************************/

static void handle_constraints_walker(ir_node *irn, void *env) {
	be_raext_env_t *raenv = env;
	arch_register_req_t req;
	int pos, max;

	/* handle output constraints
	 * user -> irn    becomes    user -> cpy -> irn
	 */
	arch_get_register_req(raenv->aenv, &req, irn, -1);
	if (arch_register_req_is(&req, limited)) {
		ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), irn);

		/* all users of the irn use the copy instead */
		sched_add_after(irn, cpy);
Daniel Grund's avatar
Daniel Grund committed
210
		edges_reroute(irn, cpy, raenv->irg);
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
	}


	/* handle input constraints by converting them into output constraints
	 * of copies of the former argument
	 * irn -> arg   becomes  irn -> copy -> arg
     */
	for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
		arch_get_register_req(raenv->aenv, &req, irn, pos);
		if (arch_register_req_is(&req, limited)) {
			ir_node *arg = get_irn_n(irn, pos);
			ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), arg);

			/* use the copy instead */
			sched_add_before(irn, cpy);
			set_irn_n(irn, pos, cpy);

			/* set an out constraint for the copy */
Daniel Grund's avatar
Daniel Grund committed
229
			be_set_constr_limited(cpy, -1, &req);
230
231
232
233
234
		}
	}
}

static void handle_constraints(be_raext_env_t *raenv) {
Daniel Grund's avatar
Daniel Grund committed
235
	irg_walk_graph(raenv->irg, NULL, handle_constraints_walker, raenv);
236
237
}

Daniel Grund's avatar
Daniel Grund committed
238

Daniel Grund's avatar
Daniel Grund committed
239
240
241
242
243
244
245
246
247
248
/******************************************************************************
     _____ _____              _____            _
    / ____/ ____|  /\        |  __ \          | |
   | (___| (___   /  \ ______| |  | | ___  ___| |_ _ __
    \___ \\___ \ / /\ \______| |  | |/ _ \/ __| __| '__|
    ____) |___) / ____ \     | |__| |  __/\__ \ |_| |
   |_____/_____/_/    \_\    |_____/ \___||___/\__|_|

 *****************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
249
250
#define mark_as_done(irn, pos)			set_irn_link(irn, INT_TO_PTR(pos+1))
#define has_been_done(irn, pos)			(PTR_TO_INT(get_irn_link(irn)) > pos)
251
252

/**
Daniel Grund's avatar
Daniel Grund committed
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
 * Insert a copy for the argument of @p start_phi found at position @p pos.
 * Also searches a phi-loop of arbitrary length to detect and resolve
 *   the class of phi-swap-problems. To search for a loop recursion is used.
 *
 * 1) Simplest case (phi with a non-phi arg):
 *     A single copy is inserted.
 *
 * 2) Phi chain (phi (with phi-arg)* with non=phi arg):
 *     Several copies are placed, each after returning from recursion.
 *
 * 3) Phi-loop:
 *     On detection a loop breaker is inserted, which is a copy of the start_phi.
 *     This copy then pretends beeing the argumnent of the last phi.
 *     Now case 2) can be used.
 *
 * The values of @p start_phi and @p pos never change during recursion.
 *
 * @p raenv      Environment with all the stuff needed
 * @p start_phi  Phi node to process
 * @p pos        Argument position to insert copy/copies for
 * @p curr_phi   Phi node currently processed during recursion. Equals start_phi on initial call
 *
 * @return NULL  If no copy is necessary
 *         NULL  If the phi has already been processed at this pos
 *               Link field is used to keep track of processed positions
 *         In all other cases the ir_node *copy which was placed is returned.
 */
static ir_node *insert_copies(be_raext_env_t *raenv, ir_node *start_phi, int pos, ir_node *curr_phi) {
	ir_node *arg = get_irn_n(curr_phi, pos);
	ir_node *arg_blk = get_nodes_block(arg);
	ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
	ir_node *curr_cpy, *last_cpy;

	assert(is_Phi(start_phi) && is_Phi(curr_phi));

	if (has_been_done(start_phi, pos))
		return NULL;

Daniel Grund's avatar
Daniel Grund committed
291
292
293
294
	/* In case this is a 'normal' phi we insert at the
	 * end of the pred block before cf nodes */
	last_cpy = sched_skip(pred_blk, 0, sched_skip_cf_predicator, raenv->aenv);
	last_cpy = sched_next(last_cpy);
Daniel Grund's avatar
Daniel Grund committed
295
296
297
298
299
300
301
302
303
304
305
306

	/* If we detect a loop stop recursion. */
	if (arg == start_phi) {
		ir_node *loop_breaker;
		if (start_phi == curr_phi) {
			/* Phi directly uses itself. No copy necessary */
			return NULL;
		}

		/* At least 2 phis are involved */
		/* Insert a loop breaking copy (an additional variable T) */
		loop_breaker = be_new_Copy(raenv->cls, raenv->irg, pred_blk, start_phi);
Daniel Grund's avatar
Daniel Grund committed
307
		sched_add_before(last_cpy, loop_breaker);
Daniel Grund's avatar
Daniel Grund committed
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334

		arg = loop_breaker;
	}

	/* If arg is a phi in the same block we have to continue search */
	if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
		last_cpy = insert_copies(raenv, start_phi, pos, arg);

	/* Insert copy of argument (may be the loop-breaker) */
	curr_cpy = be_new_Copy(raenv->cls, raenv->irg, pred_blk, arg);
	set_irn_n(curr_phi, pos, curr_cpy);
	mark_as_done(curr_phi, pos);
	sched_add_before(last_cpy, curr_cpy);
	return curr_cpy;
}


/**
 * Perform simple SSA-destruction with copies.
 * The order of processing _must_ be
 *  for all positions {
 *    for all phis {
 *      doit
 *    }
 *  }
 * else the magic to keep track of processed phi-positions will fail in
 * function 'insert_copies'
335
 */
Daniel Grund's avatar
Daniel Grund committed
336
static void ssa_destr_simple_walker(ir_node *blk, void *env) {
337
	be_raext_env_t *raenv = env;
Daniel Grund's avatar
Daniel Grund committed
338
	int pos, max;
339
340
	ir_node *phi;

Daniel Grund's avatar
Daniel Grund committed
341
342
	/* for all argument positions of the phis */
	for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
343

Daniel Grund's avatar
Daniel Grund committed
344
345
346
347
		/* for all phi nodes (which are scheduled first) */
		sched_foreach(blk, phi) {
			if (!is_Phi(phi))
				break;
348

349
			if (arch_irn_is(raenv->aenv, phi, ignore))
Daniel Grund's avatar
Daniel Grund committed
350
351
				continue;

Daniel Grund's avatar
Daniel Grund committed
352
353
			raenv->cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
			insert_copies(raenv, phi, pos, phi);
354
355
356
357
358
		}
	}
}


Daniel Grund's avatar
Daniel Grund committed
359
360
361
362
363
364
365
static void ssa_destr_simple(be_raext_env_t *raenv) {
	be_clear_links(raenv->irg);
	irg_block_walk_graph(raenv->irg, ssa_destr_simple_walker, NULL, raenv);
}


static void ssa_destr_rastello(be_raext_env_t *raenv) {
Daniel Grund's avatar
Daniel Grund committed
366
	assert(0 && "NYI");
Daniel Grund's avatar
Daniel Grund committed
367
368
	exit(0xDeadBeef);
	/*
Daniel Grund's avatar
Daniel Grund committed
369
	phi_class_compute(raenv->irg);
Daniel Grund's avatar
Daniel Grund committed
370
371
	irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
	*/
Daniel Grund's avatar
Daniel Grund committed
372
373
}

Daniel Grund's avatar
Daniel Grund committed
374
375
376
377
378
379
380
381
382
/******************************************************************************
   __      __   _       ___   __      __
   \ \    / /  | |     |__ \  \ \    / /
    \ \  / /_ _| |___     ) |  \ \  / /_ _ _ __ ___
     \ \/ / _` | / __|   / /    \ \/ / _` | '__/ __|
      \  / (_| | \__ \  / /_     \  / (_| | |  \__ \
       \/ \__,_|_|___/ |____|     \/ \__,_|_|  |___/
 *****************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
383
/**
Daniel Grund's avatar
Daniel Grund committed
384
 * This struct maps a variable (nr) to the values belonging to this variable
Daniel Grund's avatar
Daniel Grund committed
385
386
 */
struct _var_info_t {
Daniel Grund's avatar
Daniel Grund committed
387
	int var_nr;		/* the key */
Daniel Grund's avatar
Daniel Grund committed
388
389
390
	pset *values;	/* the ssa-values belonging to this variable */
};

Daniel Grund's avatar
Daniel Grund committed
391
392
#define SET_REMOVED -1

Daniel Grund's avatar
Daniel Grund committed
393
394
395
396
397
398
399
400
401
402
403
404
405
/**
 * The link field of an irn points to the var_info struct
 * representing the corresponding variable.
 */
#define set_var_info(irn, vi)				set_irn_link(irn, vi)
#define get_var_info(irn)					((var_info_t *)get_irn_link(irn))

#define HASH_VAR_NR(var_nr) var_nr

static int compare_var_infos(const void *e1, const void *e2, size_t size) {
	const var_info_t *v1 = e1;
	const var_info_t *v2 = e2;

Daniel Grund's avatar
Daniel Grund committed
406
407
408
	if (v1->var_nr == SET_REMOVED || v2->var_nr == SET_REMOVED)
		return 1;

Daniel Grund's avatar
Daniel Grund committed
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
	return v1->var_nr != v2->var_nr;
}

static INLINE var_info_t *var_find(set *vars, int var_nr) {
	var_info_t vi;
	vi.var_nr = var_nr;

	return set_find(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));
}

static INLINE var_info_t *var_find_or_insert(set *vars, int var_nr) {
	var_info_t vi, *found;
	memset(&vi, 0, sizeof(vi));
	vi.var_nr = var_nr;

	found = set_insert(vars, &vi, sizeof(vi), HASH_VAR_NR(var_nr));

Daniel Grund's avatar
Daniel Grund committed
426
	if (!found->values)
Daniel Grund's avatar
Daniel Grund committed
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
		found->values  = pset_new_ptr(1);

	return found;
}

/**
 * Adds a value to a variable. Sets all pointers accordingly.
 */
static INLINE var_info_t *var_add_value(be_raext_env_t *raenv, int var_nr, ir_node *irn) {
	var_info_t *vi = var_find_or_insert(raenv->vars, var_nr);

	/* var 2 value mapping */
	pset_insert_ptr(vi->values, irn);

	/* value 2 var mapping */
	set_var_info(irn, vi);

	return vi;
}

static INLINE pset *get_var_values(be_raext_env_t *raenv, int var_nr) {
	var_info_t *vi = var_find(raenv->vars, var_nr);
Daniel Grund's avatar
Daniel Grund committed
449
	assert(vi && "Variable does not exist");
Daniel Grund's avatar
Daniel Grund committed
450
451
452
	return vi->values;
}

453
454
455
456
457
458
459
/**
 * Define variables (numbers) for all SSA-values.
 * All values in a phi class get assigned the same variable name.
 * The link field maps values to the var-name
 */
static void values_to_vars(ir_node *irn, void *env) {
	be_raext_env_t *raenv = env;
Daniel Grund's avatar
Daniel Grund committed
460
	int nr;
461
462
	pset *vals;

Daniel Grund's avatar
Daniel Grund committed
463
464
465
	if(arch_get_irn_reg_class(raenv->aenv, irn, -1) == NULL)
		return;

466
467
	vals = get_phi_class(irn);

Daniel Grund's avatar
Daniel Grund committed
468
469
470
	if (vals) {
		nr = get_irn_node_nr(get_first_phi(vals));
	} else {
471
		/* not a phi class member, value == var */
Daniel Grund's avatar
Daniel Grund committed
472
		nr = get_irn_node_nr(irn);
473
474
475
476
		vals = pset_new_ptr(1);
		pset_insert_ptr(vals, irn);
	}

Daniel Grund's avatar
Daniel Grund committed
477
	/* values <--> var mapping */
Daniel Grund's avatar
Daniel Grund committed
478
479
	pset_foreach(vals, irn) {
		DBG((raenv->dbg, 0, "Var %d contains %+F\n", nr, irn));
Daniel Grund's avatar
Daniel Grund committed
480
		var_add_value(raenv, nr, irn);
Daniel Grund's avatar
Daniel Grund committed
481
	}
Daniel Grund's avatar
Daniel Grund committed
482
483
}

Daniel Grund's avatar
Daniel Grund committed
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498

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


static void extract_vars_of_cls(be_raext_env_t *raenv) {
	int count = 0;
Daniel Grund's avatar
Daniel Grund committed
499
	var_info_t *vi;
Daniel Grund's avatar
Daniel Grund committed
500

Michael Beck's avatar
Michael Beck committed
501
	raenv->cls_vars = xmalloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars));
Daniel Grund's avatar
Daniel Grund committed
502
503
	assert(raenv->cls_vars);

Daniel Grund's avatar
Daniel Grund committed
504
	set_foreach(raenv->vars, vi)
Daniel Grund's avatar
Daniel Grund committed
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
		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
533
534
#define UNSPILLABLE -1

Daniel Grund's avatar
Daniel Grund committed
535
static INLINE int get_spill_costs(be_raext_env_t *raenv, var_info_t *vi) {
Daniel Grund's avatar
Daniel Grund committed
536
	ir_node *irn;
537
	int c_spills=0, c_reloads=0;
Daniel Grund's avatar
Daniel Grund committed
538
539

	pset_foreach(vi->values, irn) {
540
		if (arch_irn_is(raenv->aenv, irn, ignore) || be_is_Reload(irn)) {
Daniel Grund's avatar
Daniel Grund committed
541
			pset_break(vi->values);
Daniel Grund's avatar
Daniel Grund committed
542
			return UNSPILLABLE;
Daniel Grund's avatar
Daniel Grund committed
543
544
		}

Daniel Grund's avatar
Daniel Grund committed
545
546
547
548
549
		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))
550
					c_reloads += get_reload_weight(edge->src);
Daniel Grund's avatar
Daniel Grund committed
551
552
		} else {
			/* number of spills is the number of non-phi values for this var */
553
			c_spills += get_spill_weight(irn);
Daniel Grund's avatar
Daniel Grund committed
554
555
556
		}
	}

557
	return c_spills + c_reloads;
Daniel Grund's avatar
Daniel Grund committed
558
}
Daniel Grund's avatar
Daniel Grund committed
559
560
561
562
563
564
565
566

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) {
Daniel Grund's avatar
Daniel Grund committed
567
568
569
570
571
		var_info_t *vi = raenv->cls_vars[i];

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

Daniel Grund's avatar
Daniel Grund committed
572
		fprintf(f, "%d %d", vi->var_nr, get_spill_costs(raenv, vi));
Daniel Grund's avatar
Daniel Grund committed
573
		dump_constraint(raenv, get_first_non_phi(vi->values), -1);
Daniel Grund's avatar
Daniel Grund committed
574
575
576
577
		fprintf(f, "\n");
	}

	fprintf(f, "}\n");
Daniel Grund's avatar
Daniel Grund committed
578
	fflush(f);
Daniel Grund's avatar
Daniel Grund committed
579
580
581
582
583
584
585
586
587
588
589
590
591
592
}


static void dump_interferences(be_raext_env_t *raenv) {
	int i,o;
	var_info_t *vi1, *vi2;
	ir_node *irn1, *irn2;
	FILE *f = raenv->f;

	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
593
594
595
		if (vi1->var_nr == SET_REMOVED)
			continue;

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

Daniel Grund's avatar
Daniel Grund committed
599
600
601
			if (vi2->var_nr == SET_REMOVED)
				continue;

Daniel Grund's avatar
Daniel Grund committed
602
603
604
605
606
			pset_foreach(vi1->values, irn1)
				pset_foreach(vi2->values, irn2)
					if (values_interfere(irn1, irn2)) {
						pset_break(vi1->values);
						pset_break(vi2->values);
Daniel Grund's avatar
Daniel Grund committed
607
						fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
Daniel Grund's avatar
Daniel Grund committed
608
						goto NextVar;
Daniel Grund's avatar
Daniel Grund committed
609
					}
Daniel Grund's avatar
Daniel Grund committed
610
611

NextVar: ;
Daniel Grund's avatar
Daniel Grund committed
612
613
614
615
616
617
618
		}
	}
	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
619
620
621
	arch_register_req_t req;
	int pos, max;
	var_info_t *vi1, *vi2;
Daniel Grund's avatar
Daniel Grund committed
622

623
	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
624
625
		return;

Daniel Grund's avatar
Daniel Grund committed
626
627
628
	vi1 = get_var_info(irn);

	/* copies have affinities */
Daniel Grund's avatar
Daniel Grund committed
629
	if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) {
630
		ir_node *other = get_irn_n(irn, be_pos_Copy_orig);
Daniel Grund's avatar
Daniel Grund committed
631

632
		if (! arch_irn_is(raenv->aenv, other, ignore)) {
Daniel Grund's avatar
Daniel Grund committed
633
			vi2 = get_var_info(other);
Daniel Grund's avatar
Daniel Grund committed
634

635
			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
Daniel Grund's avatar
Daniel Grund committed
636
		}
Daniel Grund's avatar
Daniel Grund committed
637
638
639
640
641
642
	}


	/* 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
643

644
		if (arch_register_req_is(&req, should_be_same) && arch_irn_is(raenv->aenv, req.other_same, ignore)) {
Sebastian Hack's avatar
Sebastian Hack committed
645
			vi2 = get_var_info(req.other_same);
Daniel Grund's avatar
Daniel Grund committed
646

647
			fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
Daniel Grund's avatar
Daniel Grund committed
648
		}
Daniel Grund's avatar
Daniel Grund committed
649
650
651
652
653
	}
}


static void dump_affinities(be_raext_env_t *raenv) {
Kimon Hoffmann's avatar
Kimon Hoffmann committed
654
	fprintf(raenv->f, "\naffinities {\n");
Daniel Grund's avatar
Daniel Grund committed
655
656
657
658
659
660
661
662
663
664
665
666
667
	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
668
		assert(0);
Daniel Grund's avatar
Daniel Grund committed
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
		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
701
	snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file);
Daniel Grund's avatar
Daniel Grund committed
702
703
704

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

Daniel Grund's avatar
Daniel Grund committed
708
709
710
711
712
713
714
715
716
717
718
/******************************************************************************
                         _         _____                 _ _
       /\               | |       |  __ \               | | |
      /  \   _ __  _ __ | |_   _  | |__) |___  ___ _   _| | |_
     / /\ \ | '_ \| '_ \| | | | | |  _  // _ \/ __| | | | | __|
    / ____ \| |_) | |_) | | |_| | | | \ \  __/\__ \ |_| | | |_
   /_/    \_\ .__/| .__/|_|\__, | |_|  \_\___||___/\__,_|_|\__|
            | |   | |       __/ |
            |_|   |_|      |___/
 *****************************************************************************/

Daniel Grund's avatar
Daniel Grund committed
719
720
721
722
723
724
/**
 * 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) {
	var_info_t *vi = var_find(raenv->vars, var_nr);
	ir_node *spill=NULL, *ctx, *irn;
725
	ir_mode *mode;
Daniel Grund's avatar
Daniel Grund committed
726
	const ir_edge_t *edge, *ne;
Daniel Grund's avatar
Daniel Grund committed
727
728
729
	pset *spills  = pset_new_ptr(4);	/* the spills of this variable */
	pset *reloads = pset_new_ptr(4);	/* the reloads of this variable */
	int new_size, n_spills, n_reloads;
Daniel Grund's avatar
Daniel Grund committed
730

Daniel Grund's avatar
Daniel Grund committed
731
732
	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
733

Daniel Grund's avatar
Daniel Grund committed
734
735
736
737
738
739
740
741
742
	/* 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
743

Daniel Grund's avatar
Daniel Grund committed
744
745
	/* for each value of this variable insert the spills */
	pset_foreach(vi->values, irn) {
Daniel Grund's avatar
Daniel Grund committed
746
747
		if (is_Phi(irn)) {
			sched_remove(irn);
Daniel Grund's avatar
Daniel Grund committed
748
			continue;
Daniel Grund's avatar
Daniel Grund committed
749
		}
Daniel Grund's avatar
Daniel Grund committed
750

Daniel Grund's avatar
Daniel Grund committed
751
		/* all ordinary nodes must be spilled */
Daniel Grund's avatar
Daniel Grund committed
752
753
		DBG((raenv->dbg, LEVEL_2, "  spilling %+F\n", irn));
		spill = be_spill(raenv->aenv, irn, ctx);
Daniel Grund's avatar
Daniel Grund committed
754
755
756

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

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

761
	mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
762

Daniel Grund's avatar
Daniel Grund committed
763
764
	/* insert reloads and wire them arbitrary*/
	pset_foreach(vi->values, irn)
Daniel Grund's avatar
Daniel Grund committed
765
		foreach_out_edge_safe(irn, edge, ne) {
Daniel Grund's avatar
Daniel Grund committed
766
			ir_node *reload, *src = edge->src;
Daniel Grund's avatar
Daniel Grund committed
767
			if (is_Phi(src) || be_is_Spill(src))
Daniel Grund's avatar
Daniel Grund committed
768
				continue;
Daniel Grund's avatar
Daniel Grund committed
769

Daniel Grund's avatar
Daniel Grund committed
770
			/* all real uses must be reloaded */
Daniel Grund's avatar
Daniel Grund committed
771
			DBG((raenv->dbg, LEVEL_2, "  reloading before %+F\n", src));
772
773
			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
774

Daniel Grund's avatar
Daniel Grund committed
775
776
			/* remember the reload */
			pset_insert_ptr(reloads, reload);
Daniel Grund's avatar
Daniel Grund committed
777
778
		}

Daniel Grund's avatar
Daniel Grund committed
779
	/* correct the reload->spill pointers... */
780
	be_ssa_constr_set(raenv->dom_info, spills);
Daniel Grund's avatar
Daniel Grund committed
781

Daniel Grund's avatar
Daniel Grund committed
782

Daniel Grund's avatar
Daniel Grund committed
783
784
785
786
787
788
789
	/****** 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
790

Daniel Grund's avatar
Daniel Grund committed
791
792
793
794
	/* 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
795

Daniel Grund's avatar
Daniel Grund committed
796
797
798
799
	/* 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
800

Daniel Grund's avatar
Daniel Grund committed
801
802
		/* ...add new vars for each non-phi-member */
		pset_foreach(spills, irn) {
803
			ir_node *spilled = get_irn_n(irn, be_pos_Spill_val);
Daniel Grund's avatar
Daniel Grund committed
804
			raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(spilled), spilled);
Daniel Grund's avatar
Daniel Grund committed
805
		}
Daniel Grund's avatar
Daniel Grund committed
806
807
808
	}

	/* add new variables for all reloads */
Daniel Grund's avatar
Daniel Grund committed
809
810
	pset_foreach(reloads, irn) {
		assert(get_irn_node_nr(irn) != 1089);
Daniel Grund's avatar
Daniel Grund committed
811
		raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(irn), irn);
Daniel Grund's avatar
Daniel Grund committed
812
	}
Daniel Grund's avatar
Daniel Grund committed
813

Daniel Grund's avatar
Daniel Grund committed
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
	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
834
		assert(0);
Daniel Grund's avatar
Daniel Grund committed
835
		exit(0xdeadbeef);
Daniel Grund's avatar
Daniel Grund committed
836
	}
Daniel Grund's avatar
Daniel Grund committed
837
	raenv->f = f;
Daniel Grund's avatar
Daniel Grund committed
838

Daniel Grund's avatar
Daniel Grund committed
839
840
841
	/* read the action */
	if (fscanf(f, BUFCONV, buf) != 1)
		INVALID_FILE_FORMAT;
Daniel Grund's avatar
Daniel Grund committed
842

Daniel Grund's avatar
Daniel Grund committed
843
844
845
846
847
848
	/* 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
849

Daniel Grund's avatar
Daniel Grund committed
850
851
852
853
854
855
	/* 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
856
			ir_node *irn;
Daniel Grund's avatar
Daniel Grund committed
857
			pset *vals = get_var_values(raenv, var_nr);
Daniel Grund's avatar
Daniel Grund committed
858

Daniel Grund's avatar
Daniel Grund committed
859
			assert(vals && "Variable nr does not exist!");
Daniel Grund's avatar
Daniel Grund committed
860
			pset_foreach(vals, irn)
Daniel Grund's avatar
Daniel Grund committed
861
				arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, reg_nr));
Daniel Grund's avatar
Daniel Grund committed
862
		}
Daniel Grund's avatar
Daniel Grund committed
863
864
	} else
		INVALID_FILE_FORMAT;
Daniel Grund's avatar
Daniel Grund committed
865
866
867
868
869
870

	if (!feof(f))
		INVALID_FILE_FORMAT;

	fclose(f);

Daniel Grund's avatar
Daniel Grund committed
871
	return is_allocation;
Daniel Grund's avatar
Daniel Grund committed
872
873
}

Daniel Grund's avatar
Daniel Grund committed
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
static void check_allocation(be_raext_env_t *raenv) {
	int i, o;

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

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

		for (o=0; o<i; ++o) {
			var_info_t *vi2 = raenv->cls_vars[o];
			ir_node *irn1, *irn2;

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

			pset_foreach(vi1->values, irn1)
				pset_foreach(vi2->values, irn2)
Daniel Grund's avatar
Daniel Grund committed
892
					if (values_interfere(irn1, irn2) && arch_get_irn_register(raenv->aenv, irn1) == arch_get_irn_register(raenv->aenv, irn2)) {
Daniel Grund's avatar
Daniel Grund committed
893
894
895
896
897
898
899
900
						dump_ir_block_graph_sched(raenv->irg, "ERROR");
						ir_fprintf(stdout, "SSA values %+F and %+F interfere. They belong to varible %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr);
						assert(0 && "ERROR graph dumped");
					}
		}
	}
}

Daniel Grund's avatar
Daniel Grund committed
901
902
903
904
905
906
907
908
/******************************************************************************
    __  __       _
   |  \/  |     (_)
   | \  / | __ _ _ _ __
   | |\/| |/ _` | | '_ \
   | |  | | (_| | | | | |
   |_|  |_|\__,_|_|_| |_|
 *****************************************************************************/
Daniel Grund's avatar
Daniel Grund committed
909

Daniel Grund's avatar
Daniel Grund committed
910
911
912
913
/**
 * Default values for options
 */
static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple;
Daniel Grund's avatar
Daniel Grund committed
914
static char callee[128] = "\"E:/user/kimohoff/public/register allocator\"";
Daniel Grund's avatar
Daniel Grund committed
915
//static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
Daniel Grund's avatar
Daniel Grund committed
916
917


918
919
920
921
922
923
924
925
926
/**
 * 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
 *
 */
Sebastian Hack's avatar
Sebastian Hack committed
927
928
929
930
static void be_ra_extern_main(const be_irg_t *bi) {
	be_main_env_t *env = bi->main_env;
	ir_graph *irg = bi->irg;

Daniel Grund's avatar
Daniel Grund committed
931
 	be_raext_env_t raenv;
932
	int clsnr, clss;
Daniel Grund's avatar
Daniel Grund committed
933
	var_info_t *vi;
934

Daniel Grund's avatar
Daniel Grund committed
935
	compute_doms(irg);
Daniel Grund's avatar
Daniel Grund committed
936
	edges_assure(irg);
Daniel Grund's avatar
Daniel Grund committed
937

Daniel Grund's avatar
Daniel Grund committed
938
939
940
941
	raenv.irg      = irg;
	raenv.aenv     = env->arch_env;
	raenv.dom_info = be_compute_dominance_frontiers(irg);
	raenv.vars     = new_set(compare_var_infos, 64);
Christian Würdig's avatar
Christian Würdig committed
942
	FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern");
Daniel Grund's avatar
Daniel Grund committed
943

944
945
	/* Insert copies for constraints */
	handle_constraints(&raenv);
Christian Würdig's avatar
Christian Würdig committed
946
	be_dump(irg, "-extern-constr", dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
947

Daniel Grund's avatar
Daniel Grund committed
948
	/* SSA destruction respectively transformation into "Conventional SSA" */
Daniel Grund's avatar
Daniel Grund committed
949
	ssa_destr(&raenv);
Christian Würdig's avatar
Christian Würdig committed
950
	be_dump(irg, "-extern-ssadestr", dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
951

Daniel Grund's avatar
Daniel Grund committed
952
	/* Mapping of SSA-Values <--> Variables */
Daniel Grund's avatar
Daniel Grund committed
953
	phi_class_compute(irg);
Daniel Grund's avatar
Daniel Grund committed
954
	be_clear_links(irg);
Daniel Grund's avatar
Daniel Grund committed
955
	irg_walk_graph(irg, values_to_vars, NULL, &raenv);
Daniel Grund's avatar
Daniel Grund committed
956

Daniel Grund's avatar
Daniel Grund committed
957

958
959
	/* 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
960
		int done, round = 1;
Daniel Grund's avatar
Daniel Grund committed
961
		char out[256], in[256];
962
963
964

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

Daniel Grund's avatar
Daniel Grund committed
965
		extract_vars_of_cls(&raenv);
966

Daniel Grund's avatar
Daniel Grund committed
967
968
969
970
		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
971
972
			be_liveness(irg);

Daniel Grund's avatar
Daniel Grund committed
973
974
975
			dump_to_file(&raenv, out);
			execute(callee, out, in);
			done = read_and_apply_results(&raenv, in);
Daniel Grund's avatar
Daniel Grund committed
976
			be_abi_fix_stack_nodes(bi->abi);
Daniel Grund's avatar
Daniel Grund committed
977
978

			ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round);
Christian Würdig's avatar
Christian Würdig committed
979
			be_dump(irg, in, dump_ir_block_graph_sched);
Daniel Grund's avatar
Daniel Grund committed
980
981
982

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

Daniel Grund's avatar
Daniel Grund committed
984
985
		check_allocation(&raenv);

Daniel Grund's avatar
Daniel Grund committed
986
		free(raenv.cls_vars);
987
	}
Daniel Grund's avatar
Daniel Grund committed
988

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

Daniel Grund's avatar
Daniel Grund committed
991
	/* Clean up */
Daniel Grund's avatar
Daniel Grund committed
992
993
	set_foreach(raenv.vars, vi)
		del_pset(vi->values);
Daniel Grund's avatar
Daniel Grund committed
994
995
	del_set(raenv.vars);
	be_free_dominance_frontiers(raenv.dom_info);
996
}
Daniel Grund's avatar
Daniel Grund committed
997
998
999
1000

/******************************************************************************
     ____        _   _
    / __ \      | | (_)