Testing a register allocator

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

Testing a register allocator

Anton Vayvod
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.

--
"Nae king! Nae quin! Nae laird! Nae master! We willnae be fooled again!", Nac Mac Feegles (Terry Pratchett, "The Wee Free Men")

"Self improvement is masturbation. Self destruction is the answer.", Tyler Durden (Chuck Palahniuk, "The Fight Club")

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Tanya Lattner-2

> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Fernando Magno Quintao Pereira
In reply to this post by Anton Vayvod

> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Vayvod
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
 
On 9/2/06, Fernando Magno Quintao Pereira <[hidden email]> wrote:

> 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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Tanya Lattner-2

> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Chris Lattner
On Sun, 3 Sep 2006, Tanya M. Lattner wrote:
>> 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'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

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Current work on type-safety proving?

Jules-9
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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Current work on type-safety proving?

Chris Lattner
On Mon, 4 Sep 2006, Jules wrote:
> Has any work been done on this?  If not, what pointers would you give
> for places to start?

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

-Chris

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Current work on type-safety proving?

Vikram S. Adve-2
In reply to this post by Jules-9
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/


On Sep 4, 2006, at 9:04 AM, Jules wrote:

> 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
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Current work on type-safety proving?

Julian Hall-2
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:

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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Vayvod
In reply to this post by Chris Lattner
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.
 
--
Three things are certain:
Death, taxes, and lost data.
Guess which has occurred.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Vayvod
In reply to this post by Chris Lattner
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.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Chris Lattner
In reply to this post by Anton Vayvod
On Tue, 19 Sep 2006, Anton Vayvod wrote:
> 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.

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

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Chris Lattner
In reply to this post by Anton Vayvod
On Tue, 19 Sep 2006, Anton Vayvod wrote:
> 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

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Vayvod
In reply to this post by Chris Lattner

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

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Vayvod
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.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

llc.exe.zip (4K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Korobeynikov
In reply to this post by Anton Vayvod
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.

--
With best regards, Anton Korobeynikov.

Faculty of Mathematics & Mechanics, Saint Petersburg State University.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Chris Lattner
In reply to this post by Anton Vayvod
On Wed, 20 Sep 2006, Anton Vayvod wrote:

> 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

--
http://nondot.org/sabre/
http://llvm.org/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Testing a register allocator

Anton Korobeynikov
In reply to this post by Anton Vayvod
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.

--
With best regards, Anton Korobeynikov.

Faculty of Mathematics & Mechanics, Saint Petersburg State University.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev