[LLVMdev] 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