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