generate_regalloc_if.pl 15.9 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/perl -w

# This script generates C code which emits assembler code for the
# assembler ir nodes. It takes a "emit" key from the node specification
# and substitutes lines starting with . with a corresponding fprintf().
# Creation: 2005/11/14
# $Id$

use strict;
use Data::Dumper;

my $specfile   = $ARGV[0];
my $target_dir = $ARGV[1];

our $arch;
our %reg_classes;
our %nodes;

# include spec file

my $return;

no strict "subs";
unless ($return = do $specfile) {
25
26
27
	warn "couldn't parse $specfile: $@" if $@;
	warn "couldn't do $specfile: $!"    unless defined $return;
	warn "couldn't run $specfile"       unless $return;
28
29
30
}
use strict "subs";

Christian Würdig's avatar
Christian Würdig committed
31
32
33
my $target_c   = $target_dir."/gen_".$arch."_regalloc_if.c";
my $target_h   = $target_dir."/gen_".$arch."_regalloc_if.h";
my $target_h_t = $target_dir."/gen_".$arch."_regalloc_if_t.h";
34
35
36
37
38
39
40
41
42
43
44

# helper function
my @rt = ("arch_register_type_none",
          "arch_register_type_write_invariant",
          "arch_register_type_caller_saved",
          "arch_register_type_callee_saved",
          "arch_register_type_ignore");

# stacks for output
my @obst_regtypes;     # stack for the register type variables
my @obst_regclasses;   # stack for the register class variables
Christian Würdig's avatar
Christian Würdig committed
45
46
my @obst_classdef;     # stack to define a name for a class index
my @obst_regdef;       # stack to define a name for a register index
47
48
49
my @obst_reginit;      # stack for the register type inits
my @obst_req;          # stack for the register requirements
my @obst_limit_func;   # stack for functions to return a subset of a register class
Christian Würdig's avatar
Christian Würdig committed
50
51
my @obst_defreq_head;  # stack for prototypes of default requirement function
my @obst_header_all;   # stack for some extern struct defs needed for bearch_$arch include
52
my @obst_projnum_map;  # stack for mapping register projnums to requirements
53
54

my $numregs;
Christian Würdig's avatar
Christian Würdig committed
55
my $class_ptr;
56
57
my $class_idx = 0;

Christian Würdig's avatar
Christian Würdig committed
58
59
my $tmp;

60
61
my %reg2class;

Christian Würdig's avatar
Christian Würdig committed
62
63
# there is a default NONE requirement
$tmp = "/* Default NONE register requirements */\n";
64
65
66
67
68
$tmp .= "const $arch\_register_req_t $arch\_default_req_none = {\n";
$tmp .= "  {\n";
$tmp .= "    arch_register_req_type_none,\n";
$tmp .= "    NULL,\n";
$tmp .= "    NULL,\n";
69
$tmp .= "    NULL\n";
70
$tmp .= "  },\n";
71
$tmp .= "  0\n";
Christian Würdig's avatar
Christian Würdig committed
72
73
74
75
$tmp .= "};\n\n";
push(@obst_req, $tmp);

push(@obst_header_all, "extern arch_register_class_t $arch\_reg_classes[N_CLASSES];\n\n");
76
push(@obst_header_all, "extern const $arch\_register_req_t $arch\_default_req_none;\n");
Christian Würdig's avatar
Christian Würdig committed
77
78
79

push(@obst_classdef, "#define N_CLASSES ".scalar(keys(%reg_classes))."\n");

80
81
my $global_projnum_idx = 0;

Christian Würdig's avatar
Christian Würdig committed
82
# generate register type and class variable, init function and default requirements
83
foreach my $class_name (keys(%reg_classes)) {
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
	my @class         = @{ $reg_classes{"$class_name"} };
	my $old_classname = $class_name;

	$class_name = $arch."_".$class_name;
	$numregs    = "N_".$class_name."_REGS";
	$class_ptr  = "&".$arch."_reg_classes[CLASS_".$class_name."]";

	push(@obst_regtypes, "#define $numregs ".($#class + 1)."\n");
	push(@obst_regtypes, "arch_register_t ".$class_name."_regs[$numregs];\n\n");

	push(@obst_classdef, "#define CLASS_$class_name $class_idx\n");
	push(@obst_regclasses, "{ \"$class_name\", $numregs, ".$class_name."_regs }");

	# there is a default NORMAL requirement for each class
	$tmp  = "/* Default NORMAL register requirements for class $class_name */\n";
	$tmp .= "const $arch\_register_req_t $arch\_default_req_$class_name = {\n";
	$tmp .= "  {\n";
	$tmp .= "    arch_register_req_type_normal,\n";
	$tmp .= "    $class_ptr,\n";
	$tmp .= "    NULL,\n";
104
	$tmp .= "    NULL\n";
105
	$tmp .= "  },\n";
106
	$tmp .= "  0\n";
107
108
109
	$tmp .= "};\n\n";
	push(@obst_req, $tmp);

110
	push(@obst_header_all, "\nextern const $arch\_register_req_t $arch\_default_req_$class_name;\n");
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

	my $idx = 0;
	push(@obst_reginit, "  /* Init of all registers in class '$class_name' */\n\n");
	foreach (@class) {
		# For each class we build for each of it's member registers a limit function
		# which limits the class to this particular register. We also build the
		# corresponding requirement structs.
		# We need those functions to set register requirements on demand in transformation
		# esp. for Call and RegParams where we can mix int and float parameters.

		my $limit_func_name = $arch."_limit_".$class_name."_".$_->{"name"};

		# push the function prototype
		$tmp = "int $limit_func_name(const ir_node *irn, int pos, bitset_t *bs)";
		push(@obst_defreq_head, $tmp.";\n");

		# push the function definition
		$tmp .= " {\n";
		$tmp .= "    bs = bitset_clear_all(bs);\n";
		$tmp .= "    bitset_set(bs, REG_".uc($_->{"name"}).");\n";  # REGISTER to index assignment is done some lines down
		$tmp .= "    return 1;\n";
		$tmp .= "}\n\n";
		push(@obst_limit_func, $tmp);

		# push the default requirement struct
		$tmp  = "const $arch\_register_req_t $arch\_default_req_$class_name\_".$_->{"name"}." = {\n";
		$tmp .= "  {\n";
		$tmp .= "    arch_register_req_type_limited,\n";
		$tmp .= "    $class_ptr,\n";
		$tmp .= "    $limit_func_name,\n";
141
		$tmp .= "    NULL\n";
142
143
144
145
146
147
148
149
150
151
152
153
		$tmp .= "  },\n";
		$tmp .= "  0\n";
		$tmp .= "};\n\n";
		push(@obst_req, $tmp);

		push(@obst_header_all, "extern const $arch\_register_req_t $arch\_default_req_$class_name\_".$_->{"name"}.";\n");

		$reg2class{$_->{"name"}} = { "class" => $old_classname, "index" => $idx }; # remember reg to class for later use
		push(@obst_regdef, "#define REG_".uc($_->{"name"})." $idx\n");
		push(@obst_reginit, "  ".$class_name."_regs[$idx].name      = \"".$_->{"name"}."\";\n");
		push(@obst_reginit, "  ".$class_name."_regs[$idx].reg_class = $class_ptr;\n");
		push(@obst_reginit, "  ".$class_name."_regs[$idx].index     = $idx;\n");
154
155
156
157
158
159
160
161
		push(@obst_reginit, "  ".$class_name."_regs[$idx].type      = ".$rt[$_->{"type"}].";\n");
		if ($_->{"type"} == 2) {
			# this is a caller saved register
			push(@obst_reginit, "  ia32_set_reg_projnum(&".$class_name."_regs[$idx], $global_projnum_idx, isa->reg_projnum_map);\n");
			push(@obst_projnum_map, "&$arch\_default_req_$class_name\_".$_->{"name"});
			$global_projnum_idx++;
		}
		push(@obst_reginit, "\n");
162
163
164
165
		$idx++;
	}

	$class_idx++;
166
167
}

168
169
170
push(@obst_regdef, "\n#define N_CALLER_SAVE_REGS ".scalar(@obst_projnum_map)."\n");

push(@obst_header_all, "\nextern const $arch\_register_req_t *$arch\_projnum_reg_req_map[N_CALLER_SAVE_REGS];\n\n");
Christian Würdig's avatar
Christian Würdig committed
171
172
push(@obst_header_all, "\n/* node specific requirements */\n");

173
174
# generate node-register constraints
foreach my $op (keys(%nodes)) {
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
	my %n = %{ $nodes{"$op"} };

	next if (!exists($n{"reg_req"}));

	$op = $arch."_".$op;

	push(@obst_req, "/* IN requirements for '$op' */\n");
	# check for argument requirements
	if (exists($n{"reg_req"}{"in"})) {
		generate_requirements(\%n, $op, "in");
	}

	push(@obst_req, "/* OUT requirements for '$op' */\n");
	# check for result requirements
	if (exists($n{"reg_req"}{"out"})) {
		generate_requirements(\%n, $op, "out");
	}
192
193
194
195
}



Christian Würdig's avatar
Christian Würdig committed
196
197
# generate header _t (internal usage) file
open(OUT, ">$target_h_t") || die("Could not open $target_h_t, reason: $!\n");
198
199
200

my $creation_time = localtime(time());

Christian Würdig's avatar
Christian Würdig committed
201
$tmp = uc($arch);
202
203

print OUT<<EOF;
Christian Würdig's avatar
Christian Würdig committed
204
205
#ifndef _GEN_$tmp\_REGALLOC_IF_T_H_
#define _GEN_$tmp\_REGALLOC_IF_T_H_
206
207

/**
Christian Würdig's avatar
Christian Würdig committed
208
 * Generated register classes from spec.
209
210
211
212
213
214
215
 *
 * DO NOT EDIT THIS FILE, your changes will be lost.
 * Edit $specfile instead.
 * created by: $0 $specfile $target_dir
 * date:       $creation_time
 */

Christian Würdig's avatar
Christian Würdig committed
216
#include "../bearch.h"
217
#include "$arch\_nodes_attr.h"
Christian Würdig's avatar
Christian Würdig committed
218

219
220
EOF

Christian Würdig's avatar
Christian Würdig committed
221
222
223
224
225
226
227
print OUT @obst_regdef, "\n";

print OUT @obst_classdef, "\n";

print OUT @obst_regtypes, "\n";

print OUT @obst_defreq_head, "\n";
228

229
print OUT "void ".$arch."_register_init(void *isa_ptr);\n\n";
230

Christian Würdig's avatar
Christian Würdig committed
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
print OUT "\n#endif /* _GEN_$tmp\_REGALLOC_IF_T_H_ */\n";



# generate header (external usage) file
open(OUT, ">$target_h") || die("Could not open $target_h, reason: $!\n");

$creation_time = localtime(time());

print OUT<<EOF;
#ifndef _GEN_$tmp\_REGALLOC_IF_H_
#define _GEN_$tmp\_REGALLOC_IF_H_

/**
 * Contains additional external requirements defs for external includes.
 *
 * DO NOT EDIT THIS FILE, your changes will be lost.
 * Edit $specfile instead.
 * created by: $0 $specfile $target_dir
 * date:       $creation_time
 */

#include "gen_$arch\_regalloc_if_t.h"

EOF

print OUT @obst_header_all;

259
260
print OUT "\n#endif /* _GEN_$tmp\_REGALLOC_IF_H_ */\n";

Christian Würdig's avatar
Christian Würdig committed
261
262
close(OUT);

263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281


# generate c inline file
open(OUT, ">$target_c") || die("Could not open $target_c, reason: $!\n");

$creation_time = localtime(time());

print OUT<<EOF;
/**
 * The generated interface for the register allocator.
 * Contains register classes and types and register constraints
 * for all nodes where constraints were given in spec.
 *
 * DO NOT EDIT THIS FILE, your changes will be lost.
 * Edit $specfile instead.
 * created by: $0 $specfile $target_dir
 * date:       $creation_time
 */

282
283
284
#include "gen_$arch\_regalloc_if.h"
#include "bearch_ia32_t.h"   /* we need this to put the caller saved registers into the isa set */
#include "ia32_map_regs.h"
285
286
287
288
289

EOF

print OUT "arch_register_class_t $arch\_reg_classes[] = {\n  ".join(",\n  ", @obst_regclasses)."\n};\n\n";

290
291
292
293
print OUT "const $arch\_register_req_t *$arch\_projnum_reg_req_map[] = {\n  ".join(",\n  ", @obst_projnum_map)."\n};\n\n";

print OUT "void ".$arch."_register_init(void *isa_ptr) {\n";
print OUT "  ia32_isa_t *isa = (ia32_isa_t *)isa_ptr;\n\n";
294
295
296
297
298
299
300
301
print OUT @obst_reginit;
print OUT "}\n\n";

print OUT @obst_limit_func;
print OUT @obst_req;

close(OUT);

302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
###
# Remember the register class for each index in the given requirements.
# We need this information for requirements like "in_sX" or "out_dX"
# @return array of classes corresponding to the requirement for each index
###
sub build_inout_idx_class {
	my $n     = shift;
	my $op    = shift;
	my $inout = shift;
	my @idx_class;

	if (exists($n->{"reg_req"}{"$inout"})) {
		my @reqs = @{ $n->{"reg_req"}{"$inout"} };

		for (my $idx = 0; $idx <= $#reqs; $idx++) {
			my $class = undef;

			if ($reqs[$idx] eq "none") {
				$class = "none";
			}
			elsif (is_reg_class($reqs[$idx])) {
				$class = $reqs[$idx];
			}
			else {
				my @regs = split(/ /, $reqs[$idx]);
GET_CLASS:		foreach my $reg (@regs) {
					if ($reg =~ /!?(in|out)\_r\d+/) {
						$class = "UNKNOWN_CLASS";
					}
					else {
						$class = get_reg_class($reg);
						if (!defined $class) {
							die("Could not get ".uc($inout)." register class for '$op' pos $idx (reg $reg) ... exiting.\n");
						}
						else {
							last GET_CLASS;
						} # !defined class
					} # if (reg =~ ...
				} # foreach
			} # if

			push(@idx_class, $class);
		} # for
	} # if

	return @idx_class;
}
349

350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
###
# Generates the requirements for the given description
###
sub generate_requirements {
	my $n     = shift;
	my $op    = shift;
	my $inout = shift;

	# get classes for the complementary direction
	my $outin     = ($inout eq "in") ? "out" : "in";

	my @reqs = @{ $n->{"reg_req"}{"$inout"} };

	for (my $idx = 0; $idx <= $#reqs; $idx++) {
		my $class = undef;

		my $tmp2 = "const $arch\_register_req_t _".$op."_reg_req_$inout\_$idx = ";
		my $tmp  = "const $arch\_register_req_t *".$op."_reg_req_$inout\_$idx = ";

		push(@obst_header_all, "extern const $arch\_register_req_t *".$op."_reg_req_$inout\_$idx;\n");

		if ($reqs[$idx] eq "none") {
			$tmp .= "&$arch\_default_req_none;\n";
		}
		elsif (is_reg_class($reqs[$idx])) {
			$tmp .= "&$arch\_default_req_".$arch."_".$reqs[$idx].";\n";
		}
		else {
			my @req_type_mask;
			my ($class, $has_limit, $pos, $same) = build_subset_class_func($n, $op, $idx, (($inout eq "in") ? 1 : 0), $reqs[$idx]);
			if (!defined($class)) {
				die("Could not build subset for ".uc($inout)." requirements '$op' pos $idx ... exiting.\n");
			}
			if ($has_limit) {
				push(@req_type_mask, "arch_register_req_type_limited");
			}
			if (defined($pos)) {
				push(@req_type_mask, "arch_register_req_type_should_be_".($same ? "same" : "different"));
			}
			$tmp  .= "&_".$op."_reg_req_$inout\_$idx;\n";
			$tmp2 .= " {\n";
			$tmp2 .= "  {\n";
			$tmp2 .= "    ".join(" | ", @req_type_mask).",\n";
			$tmp2 .= "    &$arch\_reg_classes[CLASS_$arch\_".$class."],\n";
394
			$tmp2 .= "    ".($has_limit ? "limit_reg_".$op."_$inout\_".$idx : "NULL").",\n";
395
396
397
398
399
400
401
402
403
404
405
			$tmp2 .= "    NULL\n";
			$tmp2 .= "  },\n";
			$tmp2 .= "  ".(defined($pos) ? $pos : "0")."\n};\n";

			$tmp   = $tmp2.$tmp;
		}

		push(@obst_req, $tmp."\n");
	}

}
406
407
408
409
410
411

###
# Determines whether $name is a specified register class or not.
# @return 1 if name is register class, 0 otherwise
###
sub is_reg_class {
412
413
414
	my $name = shift;
	return 1 if exists($reg_classes{"$name"});
	return 0;
415
416
417
418
419
420
421
}

###
# Returns the register class for a given register.
# @return class or undef
###
sub get_reg_class {
422
423
424
	my $reg = shift;
	return $reg2class{"$reg"}{"class"} if (exists($reg2class{"$reg"}));
	return undef;
425
426
427
428
429
430
431
}

###
# Returns the index of a given register within it's register class.
# @return index or undef
###
sub get_reg_index {
432
433
434
	my $reg = shift;
	return $reg2class{"$reg"}{"index"} if (exists($reg2class{"$reg"}));
	return undef;
435
436
437
438
439
}

###
# Generates the function for a given $op and a given IN-index
# which returns a subset of possible register from a register class
440
441
# @return classname from which the subset is derived or undef and
#         pos which corresponds to in/out reference position or undef
442
443
###
sub build_subset_class_func {
444
445
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
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
	my $neg   = undef;
	my $class = undef;
	my $temp;
	my $has_limit = 0;

	# build function header
	my $n    = shift;
	my $op   = shift;
	my $idx  = shift;
	my $in   = shift;
	my $pos  = undef;
	my $same = 1;

	my @temp_obst;

	my $outin = $in ? "out" : "in";
	my @regs  = split(/ /, shift);

	my @idx_class = build_inout_idx_class($n, $op, $outin);

	# set/unset registers
CHECK_REQS: foreach (@regs) {
		if (/(!)?$outin\_r(\d+)/) {
			if (defined($pos)) {
				print STDERR "Multiple in/out references in one requirement not allowed.\n";
				return (undef, undef, undef, undef);
			}
			$same  = 0 if ($1);
			$class = $idx_class[$2 - 1];
			$pos   = $in ? -$2 : $2 - 1;
			next CHECK_REQS;
		}

		# check for negate
		if (substr($_, 0, 1) eq "!") {
			if (defined($neg) && $neg == 0) {
				# we have seen a positiv constraint as first one but this one is negative
				# this doesn't make sense
				print STDERR "Mixed positive and negative constraints for the same slot are not allowed.\n";
				return (undef, undef, undef, undef);
			}

			if (!defined($neg)) {
				$has_limit = 1;
				push(@temp_obst, "  bs = bitset_set_all(bs);     /* allow all register (negative constraints given) */\n");
			}

			$_   = substr($_, 1); # skip '!'
			$neg = 1;
		}
		else {
			if (defined($neg) && $neg == 1) {
				# we have seen a negative constraint as first one but this one is positive
				# this doesn't make sense
				print STDERR "Mixed positive and negative constraints for the same slot are not allowed.\n";
				return (undef, undef, undef, undef);
			}

			if (!defined($neg)) {
				$has_limit = 1;
				push(@temp_obst, "  bs = bitset_clear_all(bs);   /* disallow all register (positive constraints given) */\n");
			}
			$neg = 0;
		}

		# check if register belongs to one of the given classes
		$temp = get_reg_class($_);
		if (!defined($temp)) {
			print STDERR "Unknown register '$_'!\n";
			return (undef, undef, undef, undef);
		}

		# set class
		if (!defined($class)) {
			$class = $temp;
		}
		elsif ($class ne $temp) {
			# all registers must belong to the same class
			print STDERR "Registerclass mismatch. '$_' is not member of class '$class'.\n";
			return (undef, undef, undef, undef);
		}

		if ($neg == 1) {
			$has_limit = 1;
			push(@temp_obst, "  bitset_clear(bs, ".get_reg_index($_).");         /* disallow $_ */\n");
		}
		else {
			$has_limit = 1;
			push(@temp_obst, "  bitset_set(bs, ".get_reg_index($_).");           /* allow $_ */\n");
		}
	}

	if ($has_limit == 1) {
		push(@obst_limit_func, "/* limit the possible registers for ".($in ? "IN" : "OUT")." $idx at op $op */\n");
		push(@obst_limit_func, "int limit_reg_".$op."_".($in ? "in" : "out")."_".$idx."(const ir_node *irn, int pos, bitset_t *bs) {\n");
		push(@obst_limit_func, @temp_obst);
		push(@obst_limit_func, "\n  return ".($neg ? scalar(@{ $reg_classes{"$class"} }) - scalar(@regs) : scalar(@regs)).";\n");
		push(@obst_limit_func, "}\n\n");
	}

	return ($class, $has_limit, $pos, $same);
545
}