Changes in directory llvm-www/ProjectsWithLLVM:
index.html updated: 1.39 -> 1.40 --- Log message: add puzzle solving project. --- Diffs of the changes: (+36 -0) index.html | 36 ++++++++++++++++++++++++++++++++++++ 1 files changed, 36 insertions(+) Index: llvm-www/ProjectsWithLLVM/index.html diff -u llvm-www/ProjectsWithLLVM/index.html:1.39 llvm-www/ProjectsWithLLVM/index.html:1.40 --- llvm-www/ProjectsWithLLVM/index.html:1.39 Tue Jul 31 19:03:33 2007 +++ llvm-www/ProjectsWithLLVM/index.html Sat Dec 8 18:26:42 2007 @@ -35,6 +35,7 @@ <div class="www_text"> <ul> +<li><a href="#puzzles">Register Allocation by Puzzle Solving</a></li> <li><a href="#faust">Faust Real-Time Signal Processing System</a></li> <li><a href="#adobe-hydra">Adobe "Hydra" Language</a></li> <li><a href="#Calysto">Calysto Static Checker</a></li> @@ -59,6 +60,41 @@ </div> <!--=========================================================================--> +<div class="www_subsection"> +<a name="puzzles">Register Allocation by Puzzle Solving</a> +</div> + +<div class="www_subsubsection"> +By Fernando Pereira and Jens Palsberg, UCLA. +</div> + +<div class="www_text"> +<p> +In this project, we have shown that register allocation can be viewed +as solving a collection of puzzles. +We model the register file as a puzzle board and +the program variables as puzzle pieces; +pre-coloring and register aliasing fit in naturally. +For architectures such as x86, SPARC V8, and StrongARM, +we can solve the puzzles in polynomial time, and we have augmented +the puzzle solver with a simple heuristic for spilling. +For SPEC CPU2000, our implementation is as fast as +the extended version of linear scan used by LLVM. +Our implementation produces Pentium code that is of similar quality to the +code produced by the slower, state-of-the-art iterated register coalescing +algorithm of George and Appel augmented with extensions by Smith, Ramsey, and +Holloway. +</p> + +<p> +<a href="http://compilers.cs.ucla.edu/fernando/projects/puzzles/";>Project + page</a> with a link to a tool that verifies the output of LLVM's register + allocator. +</p> + +</div> + +<!--=========================================================================--> <div class="www_subsection" id="faust"> Faust Real-Time Signal Processing System </div> _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
