Pathological Register Allocation Test Generator

[Gregor N. Purdy]

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?
Regards,
-- Gregor
Gregor N. Purdy wrote:
Dan --
Something like this for the .imc generation?
Regards,
-- Gregor
----------------------- snip: gen-imc.pl --------------------------
#!/usr/bin/perl -w
use strict;
die "Usage: $0 <total_labels> <total_locals>\n"
  unless @ARGV == 2;
my ($total_labels, $total_locals) = @ARGV;
my $labels_so_far = 0;
my $locals_so_far = 0;
print ".sub __MAIN\n\n";
while ($labels_so_far < $total_labels or $locals_so_far < $total_locals) {
  my $action = qw(label local arithmetic control)[rand 4];
  if ($action eq 'label' and $labels_so_far < $total_labels) {
    printf "\n_L_%d:\n", ++$labels_so_far;
  }
  elsif ($action eq 'local' and $locals_so_far < $total_locals) {
    printf " .local int V_%d\n", ++$locals_so_far;
    printf "  V_%d = %d\n", $locals_so_far, int(rand()) + 1;
  }
  elsif ($action eq 'arithmetic' and $locals_so_far > 0) {
    my $result = 1 + rand $locals_so_far;
    my $arg1   = 1 + rand $locals_so_far;
    my $arg2   = 1 + rand $locals_so_far;
    my $op = qw( + - * )[rand 3];
    printf "  V_%d = V_%d %s V_%d\n", $result, $arg1, $op, $arg2;
  }
  elsif ($action eq 'control' and $locals_so_far > 0) {
    my $dest = 1 + rand $total_labels;
    my $arg1 = 1 + rand $locals_so_far;
    my $arg2 = 1 + rand $locals_so_far;
    my $op = qw( < <= == != >= > )[rand 6];
    printf "  if V_%d %s V_%d goto _L_%d\n", $arg1, $op, $arg2, $dest;
  }
}
print "\n";
print ".end\n";
print "\n";
exit 0;
----------------------------- snip --------------------------------
Dan Sugalski wrote:
At 6:50 AM -0700 8/30/04, Gregor N. Purdy wrote:
Dan --
I figured. We could probably write a code-generator that used a PRNG
to generate massive amounts of stereotypical code, spitting out C and
PIR...
That would be easy if it was a bunch of
 x = x + y
 z = 3 * x
lines that would approximate the structure of your large stuff. Is it
much more complicated than that?

Oh, yeah. :) Or, rather, no, if you factor in the second simple bit, 
the massive number of labels and comparisons. Add those into the mix 
and I think you'd have it.

-- Gregor
Dan Sugalski wrote:
At 6:46 AM -0700 8/27/04, Gregor N. Purdy wrote:
Dan --
I think it would be interesting to find out how, say, gcc
behaves on the pathological code structures you've run into.
Could your compiler spit out a structurally (although not
semantically! :) equivalent piece of C code that could be
used with a C compiler to see how we do vs. C compilers in
these cases?


That's a good question. While it's not impossible, I'd need to do a 
bunch of work on the compiler to get it to emit compilable C instead 
of PIR, and I don't think it's something I'll have time for anytime 
soon. :(


#!/usr/bin/perl -w
use strict;

die "Usage: $0 <total_labels> <total_locals>\n"
  unless @ARGV == 2;

my ($total_labels, $total_locals) = @ARGV;

my $labels_so_far = 0;
my $locals_so_far = 0;

open IMC, ">gen.imc";
open CPP, ">gen.cpp";

print IMC ".sub __MAIN\n\n";
print CPP "int main(int argc, char * arg[])\n{\n";

while ($labels_so_far < $total_labels or $locals_so_far < $total_locals) {
  my $action = qw(label local arithmetic control)[int(rand(4))];

  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 'local' 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 3];

    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));

    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;
  }
}

print IMC "\n";
print IMC ".end\n";
print IMC "\n";

print CPP "\n";
print CPP "  return 0;\n";
print CPP "}\n";

exit 0;