Testing a register allocator

Hi!

I developed a register allocator within LLVM and now I need to test its efficiency. Can I do this using llvm-test package?
Do llvm tests check all available regalloc options automatically? If not, then what modifications should I do to the test files?
It would be great if I could test my algo along with linearscan and compare the results.

Thanks.

Tony.

I developed a register allocator within LLVM and now I need to test its
efficiency. Can I do this using llvm-test package?
Do llvm tests check all available regalloc options automatically? If not,
then what modifications should I do to the test files?

You can use llvm-test to do this. It wont check all avaliable regalloc options though... you need to tell it to use something other than the default. If you wanted to use the nightly tester scripts, you can set the llc-beta option to use your register allocator. Otherwise, check out TEST.llc* to see how you can modify it to use your register allocator and generate reports.

-Tanya

Hi!

I developed a register allocator within LLVM and now I need to test its
efficiency. Can I do this using llvm-test package?
Do llvm tests check all available regalloc options automatically? If not,
then what modifications should I do to the test files?
It would be great if I could test my algo along with linearscan and compare
the results.

Thanks.

Tony.

Hey, Anton.

    In TEST.llc.Makefile, you can set the type of register allocator that
you want:
LLC_OPTS = -f -o=/dev/null -stats -time-passes -regalloc=linearscan

to compare against your, open "Makefile.program", and set
LLCBETAOPTION := -regalloc=your_allocator -fast

After that, you just have to type make TEST=nightly report.html
on project/llvm-test/

An '*' on the report means that your test failed. The report will give you
your compile time, and the running time of the compiled file.

Remember to check the test files from CVS.

Best,

Fernando

Hi again!

I’ve managed to run the llvm-test with the options Fernando told.

What I did was the following:

I changed llc regalloc option in TEST.llc.makefile to my allocator.
I changed LLCBETAOPTION in makefile.programs file for all architechtures to use my allocator.
I run make TEST=nightly report.html and got all tests under LLCBETA failed (‘*’ symbol). Though I know that my algorithm works. At least I succeeded to pass some files from the LLVM tests (oggenc.c, for example) through llvm-gcc -emit-llvm ; llc -regalloc=myregalloc; gcc -g commands and everything worked fine (even running of the compiled file).
So I guess that nightlytest compares output of tested programs with some prepared results and the output of llc with my regalloc is different from the expected. Is it right? Or did I do smth wrong?

BTW, how can I run all tests only on LLC to reduce the amount of time to wait until tests are finished, if it’s possible?

Thanks!

P.S. I’ve checked out LLVM before running the tests

BTW, how can I run all tests only on LLC to reduce the amount of time to
wait until tests are finished, if it's possible?

In my previous reply to your question, I suggested you look at TEST.llc.Makefile and TEST.llc.report in the test directory. Modifying those makefile/report files to use your register allocator will do what you want.

-Tanya

Tanya's right, if you want full control over what is being run, you should write your own test script. If you really really want to use the nightly tester script, you can pass DISABLE_CBE=1 DISABLE_JIT=1 on the make command line to disable those runs.

If the test output claims that llc-beta fails, then your register allocator is producing incorrect code. In a multisource directory, if you use 'make bugpoint-llc-beta' in some failing test directory, bugpoint will automatically reduce the failure to a smaller example for you.

-Chris

I was just wondering what existing work has been done on proving
programs type-safe using the LLVM framework? I've read the paper on
memory-safety for embedded systems, but that's not quite what I'm
looking for, as my application (which involves running untrusted code
within a trusted context) might fail if a pointer to one object became a
pointer to another of the same type.

Looking at the documentation, it seems a trivial check for type-safety
would be simply to ensure that the program didn't use any 'cast'
instructions, only used the memory allocation facilities of a trusted
garbage collector, and didn't contain any zero-length arrays (as these
might be used for unsafe pointer arithmetic). However I guess that in
the real world, these constraints would be almost impossible to program
to (e.g., my simple C++ test programs suggest that it's impossible to
write any non-trivial C++ program that doesn't generate a 'cast'), so
there must be circumstances that allow such constructs.

Has any work been done on this? If not, what pointers would you give
for places to start?

Thanks,

Jules

Here is one pointer: http://safecode.cs.uiuc.edu/

-Chris

Jules,

The link Chris forwarded (safecode.cs.uiuc.edu) describes the most relevant work so far. But that work aims to make ordinary C and C++ programs memory-safe, without using garbage collection or any other automatic memory management scheme, i.e., allowing dangling pointers but ensuring they are harmless. It also allows any casts that are legal in C.

If you want to enforce strict type safety with GC and without arbitrary casts, you should be able to build on top of SAFECode and provide a garbage collector. You'd have to define what pointer casts are legal and check for them. But SAFECode would give you several other checks you need including:
-- array bounds (just looking for 0-length arrays isn't enough)
-- uninitialized variables
-- many stdlib usage checks.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

Thanks for your replies.

This all looks extremely interesting, and I see now what I would need to do to go ahead with this.

I would plan on using a subset of C++ with a garbage collector as my target language, and would probably exclude existing standard libraries (my application would require a specific API be available, but not much else), except for those that would compile within such a language subset (e.g. C string manipulations, some parts of the C++ STL and boost, etc.).

I'm hoping this will be possible without compiler modifications, but fear it might not be. I don't know if the type information emitted by G++ is enough to enable all the checks I'll need.

Vikram Adve wrote:

If the test output claims that llc-beta fails, then your register
allocator is producing incorrect code. In a multisource directory, if you
use ‘make bugpoint-llc-beta’ in some failing test directory, bugpoint will
automatically reduce the failure to a smaller example for you.

Ok. My allocator failed on MultiSource/Applications/Burg test.
I run bugpoint and it gives me bugpoint-reduced-simplified.bc.
I run llc on this file with all LLVM register allocators and it gives the same result (under gdb):

Program received signal SIGSEGV, Segmentation fault.
0x00634572 in (anonymous namespace)::X86DAGToDAGISel::DeleteNode (
this=0x4c3b710, N=0x4c3e5c0)
at /llvm/obj/lib/Target/X86/X86GenDAGISel.inc:77
77 SDNode *Operand = I->Val;

SEGFAULT seems to come before register allocation pass is being run.

Thanks.

If the test output claims that llc-beta fails, then your register
allocator is producing incorrect code.

Ok, I run make TEST=llc report.html with default allocator, not mine.

Why LLCBETAOPTION for X86 is local, not linearscan?
I’ve got some tests having * in some columns (for example, in column with register spills count). Does it mean that the test failed?

Thanks.

Are you using LLVM CVS? If not, please update. If so, please run 'make bugpoint-llc' in that directory and file a bug. This is an instruction selector bug, not yours. We'll be happy to fix it if it's not already fixed in LLVM CVS.

-Chris

Ok, I run make TEST=llc report.html with default allocator, not mine.

Why LLCBETAOPTION for X86 is local, not linearscan?

We are testing it with the nightly test. To change it, modify the appropriate line (search for -regalloc=local) in llvm-test/Makefile.programs.

I've got some tests having * in some columns (for example, in column with
register spills count). Does it mean that the test failed?

I don't know, I don't think anyone has used the llc test with the local register allocator.

-Chris

Are you using LLVM CVS? If not, please update.

Yes, I’m using LLVM CVS. Updated a couple of hours ago.

If so, please run ‘make
bugpoint-llc’ in that directory and file a bug. This is an instruction
selector bug, not yours. We’ll be happy to fix it if it’s not already
fixed in LLVM CVS.

The test is running and I already have Segmentation Fault errors in Regression/C++ tests and UnitTests. But make bugpoint-llc doesn’t find any targets in tests’ obj directories.

I’ll wait until error in some Application test occurs and will file a bug then.

Interesting that these errors don’t occur under Linux with the same CVS version of LLVM (but using gcc 4.1.1 if this matters).

BTW, what’s the difference between llc and llc-beta?

Thanks

I didn’t find how to attach the bugpoint output with bugzilla so I’ll attach it (and stackdump, too) here.

The test bugpoint was run on is /MultiSource/Applications/sgefa

Though the same error appears almost for every test (UnitTests, Regression, etc).

See if this worth to be submitted as a bug.

I’ve updated from CVS about two hours ago.
I use cygwin with gcc 3.4.4 (cygming special), binutils 2.17.

Thanks.

llc.exe.zip (3.62 KB)

Hello Anton

Wed, 20 Sep 2006 15:17:16 +0400 you wrote:

See if this worth to be submitted as a bug.
I've updated from CVS about two hours ago.
I use cygwin with gcc 3.4.4 (cygming special), binutils 2.17.

I'll check it here. I have gcc 3.4.4 (mingw) cross-compiler installed,
so, I'll try to build LLVM with mingw and check, whether it'll fail.

Yes, I'm using LLVM CVS. Updated a couple of hours ago.
  If so, please run 'make

bugpoint-llc' in that directory and file a bug. This is an instruction
selector bug, not yours. We'll be happy to fix it if it's not already
fixed in LLVM CVS.

The test is running and I already have Segmentation Fault errors in
Regression/C++ tests and UnitTests. But make bugpoint-llc doesn't find any
targets in tests' obj directories.

Ah, in singlesource, try 'make Output/program.bugpoint-llc'.

I'll wait until error in some Application test occurs and will file a bug
then.

Interesting that these errors don't occur under Linux with the same CVS
version of LLVM (but using gcc 4.1.1 if this matters).

There are a lot of things that could trigger it. System header files vary widely across OS's (even across versions of one OS), and can sometimes trigger issues.

BTW, what's the difference between llc and llc-beta?

llc-beta is a "test platform" for new stuff, and is also used for performance comparisons between different sets of LLC options. On X86 right now, llc-beta uses the local (intra-basic-block) register allocator, which is used with llvm-gcc -O0.

-Chris

Hello Anton

Wed, 20 Sep 2006 15:17:16 +0400 you wrote:

I've updated from CVS about two hours ago.
I use cygwin with gcc 3.4.4 (cygming special), binutils 2.17.

Everything is ok here (llc.exe compiled with mingw edition of gcc). If
you want, I can send you compiled llc.exe.