[LLVMdev] Puzzle solver on LLVM 2.1

Evan Cheng evan.cheng at apple.com
Thu Dec 13 23:41:19 PST 2007

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  


> best,
> Fernando
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

More information about the llvm-dev mailing list