Hello All,
This is my first post to the parrot list, but I hope that many will
follow. Thanks to all of you for working so dilligently on building
this wonderful new toy for all us geeks to play with!
I am currently working on a fix to the large subroutine register
allocation bug, aka, "massive spilling not yet implemented". The
problem, is that the register allocation code is complex, and I'm not
all that familiar with it, or even with working with compilers at the
coding level.
I am comming at the problem as a former graph theorist, who was a
consultant to a compiler project (at UC Davis, in the late 90's where
some of the work was applied toward what is the current Intel
compiler). I talked a lot, and learned a lot, but didn't actually
contribute any coding to the project. I also spent a lot of time
coding graph coloring heuristics with C++.
I expect to produce a patch soon, that will make register allocation
better. To that end, I felt it was important to come up with some
metrics. The first attached program (gen3.pl), which is based on Greg
Purdy's gen-pra.pl, gathers data on compilation performance for
varying numbers of variables and compares this to GCC. Mine also uses
gnuplot to make pretty pictures. If everything is installed okay on
your system, a graph will pop up displaying runtime results. I'm
using Debian Linux, so it was pretty easy to set up.
The second program, gen4.pl, is a randomized, automated, blackbox
tester. It works similar to the above, but the corresponding parrot
and GCC outputs are compared.
And now, for the philosophical note ...
One of the biggest wins of RISC over CISC was not that RISC was
smaller, but that architects looked at actual code that would run on
their machines. They removed an instruction from the instruction set
if it wasn't used that frequently. They considered wheather to
implement features in the hardware, or the compiler, and they tested
each, to find the optimum balance. This approach may be helpful in
building parrot as well, and it's what I've tried to do, in a very
modest way, in my scripts. Thanks to Gregg Purdy for getting the ball
rolling in this general direction.
Thanks,
Bill Coffman
On Mon, 11 Oct 2004 09:54:31 -0400, Dan Sugalski <[EMAIL PROTECTED]> wrote:
> At 4:58 PM -0700 10/2/04, Gregor N. Purdy wrote:
> >Dan et al. --
> >
> >I made a new version of the script that creates gen.cpp and gen.imc
> >(attached). You can run it like this:
> >
> > perl gen-pra.pl 1000 10000
> >
> >(for 1000 labels and 10000 variables) and it will create equivalent
> >gen.imc and gen.cpp files. You can test-compile them with these
> >commands:
> >
> > g++ -c gen.cpp
> >
> >and
> >
> > imcc -o x.x gen.imc
> >
> >on my system, the g++ compiler does eventually finish, but the imcc
> >compiler is eventually killed.
> >
> >Maybe this could be used to drive out the underlying problems that
> >are keeping parrot from compiling Dan's really large subs?
>
> Mmmm, degenerate behaviour! Cool, and thanks. Should help judge how
> we're doing with the nastier code.
> --
> Dan
>
> --------------------------------------it's like this-------------------
> Dan Sugalski even samurai
> [EMAIL PROTECTED] have teddy bears and even
> teddy bears get drunk
>
#!/usr/bin/perl -w
use strict;
die "Usage: $0 <starting_num_variables> <ending_num_variables>\n" unless @ARGV == 2;
my ($start,$stop) = @ARGV;
open COMP, ">compile.dat" or die "$!";
print COMP "#vars gcc imc\n";
for (my $vars=$start;$vars<=$stop;$vars++) {
my ($total_locals) = $vars;
my $total_labels = int ($total_locals / 2);
my $labels_so_far = 1;
my $locals_so_far = 0;
open IMC, ">gen.imc";
open CPP, ">gen.cpp";
print IMC ".sub __MAIN\n\n";
printf IMC "\n_L_%d:\n", 1;
print CPP "#include <stdio.h>\n\n";
print CPP "int main(int argc, char * arg[])\n{\n";
printf CPP "\n_L_%d:\n", 1;
my %action_table = qw(l label v variable a arithmetic c control p print);
my @actions = (('l')x2, ('v')x4, ('a')x9, ('c')x3, ('p')x0);
while ($labels_so_far < $total_labels or $locals_so_far < $total_locals) {
my $action = $action_table{$actions[rand @actions]};
if ($action eq 'label' and $labels_so_far < $total_labels) {
my $this_label = ++$labels_so_far;
printf IMC "\n_L_%d:\n", $this_label;
printf CPP "\n_L_%d:\n", $this_label;
}
elsif ($action eq 'variable' and $locals_so_far < $total_locals) {
my $this_local = ++$locals_so_far;
my $this_value = int(rand(99)) + 1;
printf IMC " .local int V_%d\n", $this_local;
printf IMC " V_%d = %d\n", $this_local, $this_value;
printf CPP " int V_%d;\n", $this_local;
printf CPP " V_%d = %d;\n", $this_local, $this_value;
}
elsif ($action eq 'arithmetic' and $locals_so_far > 0) {
my $result = 1 + int(rand($locals_so_far));
my $arg1 = 1 + int(rand($locals_so_far));
my $arg2 = 1 + int(rand($locals_so_far));
next if $arg1 == $arg2;
my $op = qw( + - )[rand 2];
printf IMC " V_%d = V_%d %s V_%d\n", $result, $arg1, $op, $arg2;
printf CPP " V_%d = V_%d %s V_%d;\n", $result, $arg1, $op, $arg2;
}
elsif ($action eq 'control' and $locals_so_far > 0) {
my $dest = 1 + int(rand($total_labels));
my $arg1 = 1 + int(rand($locals_so_far));
my $arg2 = 1 + int(rand($locals_so_far));
next if $arg1 == $arg2;
my $op = qw( < <= == != >= > )[rand 6];
printf IMC " if V_%d %s V_%d goto _L_%d\n", $arg1, $op, $arg2, $dest;
printf CPP " if (V_%d %s V_%d) goto _L_%d;\n", $arg1, $op, $arg2, $dest;
}
elsif ($action eq 'print') {
for (my $j=0; $j<$locals_so_far; $j++) {
printf IMC " print \" \"\n";
printf IMC " print V_%d\n", $j+1;
printf CPP " printf(\" \");\n";
printf CPP " printf(\"%%d\", V_%d);\n", $j+1;
}
printf IMC " print \"\\n\"\n";
printf CPP " printf(\"\\n\");\n";
}
}
print IMC "\n";
print IMC "end\n";
print IMC ".end\n";
print IMC "\n";
print CPP "\n";
print CPP " return 0;\n";
print CPP "}\n";
my ($gcc) = map {m/user\s*(.*)/?$1:()} `sh -c "time -p g++ -O gen.cpp" 2>&1`;
my ($imc) = map {m/user\s*(.*)/?$1:()} `sh -c "time -p ../parrot -o x.x gen.imc" 2>&1`;
print COMP "$vars $gcc $imc\n";
}
close COMP;
if (`which gnuplot`) {
my $plot = <<EOT
#Uncomment next two, to create a png file.
#set terminal png
#set out "compile.png"
set title "Compile times for variable count -- GCC vs. Parrot"
set logscale y
plot "compile.dat" using 1:2 title 'g++ -O' with linespoints, \\
"compile.dat" using 1:3 title 'parrot -o' with linespoints
#Okay to comment below if only creating png.
pause -1 "Press return to continue"
#reset
EOT
;
open PLOT, ">compile.plot" or die "failed writing compile.plot, $!";
print PLOT $plot;
close PLOT;
system "gnuplot compile.plot";
}
exit 0;
#!/usr/bin/perl -w
use strict;
die "Usage: $0 <num_variables>\n" unless @ARGV == 1;
my $start = shift;
open COMP, ">compile.dat" or die "$!";
print COMP "#vars gcc imc\n";
for (my $vars=$start;$vars<=111;$vars++) {
my ($total_locals) = $vars;
my $total_labels = int ($total_locals / 2);
my $labels_so_far = 1;
my $locals_so_far = 0;
open IMC, ">gen.imc";
open CPP, ">gen.cpp";
print IMC ".sub __MAIN\n\n";
printf IMC "\n_L_%d:\n", 0;
print CPP "#include <stdio.h>\n\n";
print CPP "int main(int argc, char * arg[])\n{\n";
printf CPP "\n_L_%d:\n", 0;
my %action_table = qw(l label v variable a arithmetic c control p print);
my @actions = (('l')x10, ('v')x1, ('a')x30, ('c')x3, ('p')x4);
while ($locals_so_far < $total_locals) {
my $this_local = ++$locals_so_far;
my $this_value = int(rand(99)) + 1;
printf IMC " .local int V_%d\n", $this_local;
printf IMC " V_%d = %d\n", $this_local, $this_value;
printf CPP " int V_%d;\n", $this_local;
printf CPP " V_%d = %d;\n", $this_local, $this_value;
}
printf IMC "\n_L_%d:\n", 1;
printf CPP "\n_L_%d:\n", 1;
while ($labels_so_far < $total_labels) {
my $action = $action_table{$actions[rand @actions]};
if ($action eq 'label' and $labels_so_far < $total_labels) {
my $this_label = ++$labels_so_far;
printf IMC "\n_L_%d:\n", $this_label;
printf CPP "\n_L_%d:\n", $this_label;
}
elsif ($action eq 'variable' and $locals_so_far < $total_locals) {
my $this_local = ++$locals_so_far;
my $this_value = int(rand(99)) + 1;
printf IMC " .local int V_%d\n", $this_local;
printf IMC " V_%d = %d\n", $this_local, $this_value;
printf CPP " int V_%d;\n", $this_local;
printf CPP " V_%d = %d;\n", $this_local, $this_value;
}
elsif ($action eq 'arithmetic' and $locals_so_far > 0) {
my $result = 1 + int(rand($locals_so_far));
my $arg1 = 1 + int(rand($locals_so_far));
my $arg2 = 1 + int(rand($locals_so_far));
my $op = qw( + - )[rand 2];
printf IMC " V_%d = V_%d %s V_%d\n", $result, $arg1, $op, $arg2;
printf CPP " V_%d = V_%d %s V_%d;\n", $result, $arg1, $op, $arg2;
}
elsif ($action eq 'control' and $locals_so_far > 0) {
my $dest = 1 + int(rand($total_labels));
my $arg1 = 1 + int(rand($locals_so_far));
my $arg2 = 1 + int(rand($locals_so_far));
next if $arg1 == $arg2;
my $op = qw( < <= == != >= > )[rand 6];
printf IMC " if V_%d %s V_%d goto _L_%d\n", $arg1, $op, $arg2, $dest;
printf CPP " if (V_%d %s V_%d) goto _L_%d;\n", $arg1, $op, $arg2, $dest;
}
elsif ($action eq 'print') {
for (my $j=0; $j<$locals_so_far; $j++) {
printf IMC " print \" \"\n";
printf IMC " print V_%d\n", $j+1;
printf CPP " printf(\" \");\n";
printf CPP " printf(\"%%d\", V_%d);\n", $j+1;
}
printf IMC " print \"\\n\"\n";
printf CPP " printf(\"\\n\");\n";
}
}
print IMC "\n";
print IMC "end\n";
print IMC ".end\n";
print IMC "\n";
print CPP "\n";
print CPP " return 0;\n";
print CPP "}\n";
my ($gcc) = map {m/user\s*(.*)/?$1:()} `sh -c "time -p g++ -O6 gen.cpp" 2>&1`;
my ($imc) = map {m/user\s*(.*)/?$1:()} `sh -c "time -p ../parrot -o x.pasm gen.imc" 2>&1`;
print COMP "$vars $gcc $imc\n";
if ((my $child=fork)==0) {
exec "./a.out |head -1000 > a.dat";
} else {
sleep 1;
#print "child $child killed\n" if
system "killall a.out 2>/dev/null" if kill 'TERM', $child;
}
#print "okay\n";
if ((my $child=fork)==0) {
exec "../parrot x.pasm |head -1000 > x.dat";
} else {
sleep 1;
#print "child $child killed\n" if kill 'TERM', $child;
system "killall parrot 2>/dev/null" if kill 'TERM', $child;
}
#system "ls -l a.dat x.dat";
my $s1 = -s "a.dat";
my $s2 = -s "x.dat";
if ($s1 < $s2) {
rename "x.dat", "x2.dat" or die;
system "head -c $s1 x2.dat > x.dat";
unlink "x2.dat" or die;
$s2 = -s "x.dat";
}
if ($s1 > $s2) {
rename "a.dat", "a2.dat" or die;
system "head -c $s2 a2.dat > a.dat";
unlink "a2.dat" or die;
$s1 = -s "a.dat";
}
print "$vars $gcc $imc (size==$s1)\n";
die "huh? $s1 != $s2" if $s1 != $s2;
#system "wc -l a.dat x.dat";
my @diff = `diff a.dat x.dat`;
die "different" if @diff;
}
close COMP;
if (`which gnuplot`) {
my $plot = <<EOT
#Uncomment next two, to create a png file.
#set terminal png
#set out "compile.png"
set title "Compile times for variable count -- GCC vs. Parrot"
set logscale y
plot "compile.dat" using 1:2 title 'g++ -O6' with linespoints, \\
"compile.dat" using 1:3 title 'parrot -o' with linespoints
#Okay to comment below if only creating png.
pause -1 "Press return to continue"
#reset
EOT
;
open PLOT, ">compile.plot" or die "failed writing compile.plot, $!";
print PLOT $plot;
close PLOT;
system "gnuplot compile.plot";
}
exit 0;
