Front Page All Articles Recent Changes Random Article

Contents

Concatenative language

  • ACL
  • Ait
  • Aocla
  • Breeze
  • Callisto
  • Cat
  • Cognate
  • colorForth
  • Concata
  • CoSy
  • Deque
  • DSSP
  • dt
  • Elymas
  • Enchilada
  • ETAC
  • F
  • Factor
  • Fiveth
  • Forth
  • Fourth
  • Freelang
  • Gershwin
  • hex
  • iNet
  • Joy
  • Joy of Postfix App
  • kcats
  • Kitten
  • lang5
  • Listack
  • LSE64
  • Lviv
  • Meow5
  • min
  • Mirth
  • mjoy
  • Mlatu
  • Ode
  • OForth
  • Om
  • Onyx
  • Plorth
  • Popr
  • Porth
  • PostScript
  • Prowl
  • Quest32
  • Quackery
  • r3
  • Raven
  • Retro
  • RPL
  • SPL
  • Staapl
  • Stabel
  • Tal
  • Titan
  • Trith
  • Uiua
  • Worst
  • xs
  • XY
  • 5th
  • 8th

Concatenative topics

  • Compilers
  • Interpreters
  • Type systems
  • Object systems
  • Quotations
  • Variables
  • Garbage collection
  • Example programs

Concatenative meta

  • People
  • Communities

Other languages

  • APL
  • C++
  • Erlang
  • FP trivia
  • Haskell
  • Io
  • Java
  • JavaScript
  • Lisp
  • ML
  • Oberon
  • RPL
  • Self
  • Slate
  • Smalltalk

Meta

  • Search
  • Farkup wiki format
  • Etiquette
  • Sandbox

Factor/GSoC/2010/More advanced compiler optimizations

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.

This revision created on Sun, 28 Feb 2010 04:54:53 by slava

Latest Revisions Edit

All content is © 2008-2024 by its respective authors. By adding content to this wiki, you agree to release it under the BSD license.