Mentor

Slava Pestov

Skills required

• Understanding of compilers

Technical outline

Factor has a fairly advanced optimizing compiler, but improvements can be made to it. The suggestions below are roughly in order of difficulty. This is an open-ended project, and it would be unreasonable to expect a student to complete all of them.

• Implement unboxing of word-size integers. This will generalize the compiler.tree.modular-arithmetic pass to deal with backward propagation of bitwidths
• Make value numbering global, rather than local. Other than implementing the actual algorithm, the main challenge is adding support to the garbage collector for pointers into the middle of objects, relative to a base pointer. This is necessary because value numbering can create references to pointer arithmetic expressions between block boundaries, and GC checks are inserted at the start of each block.
• Make alias analysis global, rather than local. This would give us mutable tuple and array unboxing for loops.

References

The LLVM documentation and source is a good reference for these optimizations:

• http://llvm.org/docs/Passes.html#scalarrepl
• http://llvm.org/docs/AliasAnalysis.html

Papers about global value numbering:

• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.4915

Benefit to student

The student learns about compilers.

Benefit to community

Nearly all Factor programs would become faster with these compiler optimizations.