Puzzle solver on LLVM 2.1

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

Puzzle solver on LLVM 2.1

Fernando Magno Quintao Pereira

Dear guys,

     I've put the puzzle solver running on LLVM 2.1. Well, at least
partially, for it is failing three of SPEC2000 benchmarks. I will try to
debug it now. The results are not as good as before. I mean, the puzzle
solver is still the same, but the default allocator is producing very good
code now. Even though, the puzzle solver produces faster code for half the
benchmarks. It does not use instruction folding yet, nor
rematerialization. I am trying to make it more retargetable, so I've moved
all the target specific information to a single class called
X86PuzzleBoard. Also, as I could not compile the top of LLVM tree, I am
using my own algorithm to build the Machine Dominator Tree. It is a
quadratic algorithm that accounts for more than half the compilation time
of SPEC2000. I think it would be easy to add the LLVM dominator tree once
I can compile it (the compilation problem is due to gcc 3.3.3). My next
step will be:
1) debug the three benchmarks that are failing: gcc, vpr and vortex
2) add instruction folding

Just as an aside, I compared the puzzle solver with the BigBlockAllocator,
and the puzzle solver seems to be producing much fewer memory accesses for
big basic blocks. For instance, for a basic block with about 8000
instructions, the algorithms produce the following static code:

                    #mem accesses    #Moves
puzzle                       178        68
bigblock                     227        34
LLVM's default               276         4

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: Puzzle solver on LLVM 2.1

Evan Cheng-2

On Dec 13, 2007, at 1:10 PM, Fernando Magno Quintao Pereira wrote:

>
> Dear guys,
>
>      I've put the puzzle solver running on LLVM 2.1. Well, at least
> partially, for it is failing three of SPEC2000 benchmarks. I will  
> try to

Very nice.

> debug it now. The results are not as good as before. I mean, the  
> puzzle
> solver is still the same, but the default allocator is producing  
> very good
> code now. Even though, the puzzle solver produces faster code for  
> half the
> benchmarks. It does not use instruction folding yet, nor
> rematerialization. I am trying to make it more retargetable, so  
> I've moved
> all the target specific information to a single class called
> X86PuzzleBoard. Also, as I could not compile the top of LLVM tree,  
> I am
> using my own algorithm to build the Machine Dominator Tree. It is a

It would be interesting your result against tot since live interval  
splitting landed recently.

> quadratic algorithm that accounts for more than half the  
> compilation time
> of SPEC2000. I think it would be easy to add the LLVM dominator  
> tree once
> I can compile it (the compilation problem is due to gcc 3.3.3). My  
> next
> step will be:
> 1) debug the three benchmarks that are failing: gcc, vpr and vortex
> 2) add instruction folding
>
> Just as an aside, I compared the puzzle solver with the  
> BigBlockAllocator,
> and the puzzle solver seems to be producing much fewer memory  
> accesses for
> big basic blocks. For instance, for a basic block with about 8000
> instructions, the algorithms produce the following static code:
>
>                     #mem accesses    #Moves
> puzzle                       178        68
> bigblock                     227        34
> LLVM's default               276         4

Very cool! I look forward to seeing your allocator in the llvm  
repository.

Evan

>
> best,
>
> Fernando
> _______________________________________________
> 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