News Archives

[Colloquium] Colloquium by faculty candidate

March 11, 2010

Watch Colloquium: 

Quicktime file (474 MB)
AVI file (466 MB)


  • Date: Thursday, March 11, 2010 
  • Time: 11 am — 12:15 pm 
  • Place: Mechanical Engineering, Room 218

Joao Dias
Department of Electrical Engineering and Computer Science Tufts University

Abstract: In programming languages, a new idea may help programmers express algorithms more easily or may guarantee that programs behave better. To evaluate such an idea, you need to see how programmers use it in practice, so you need an implementation which is good enough that programmers will actually use it. Historically, while programmers may be forgiving at first, eventually they demand compilers that generate native machine code of high quality. Such compilers are difficult to build. The goal of my research is to develop new ways of building high-quality compilers cheaply.

In building a high-quality compiler, one of the big costs is finding the services of a person who is expert in *both* the compiler *and* the target machine. The main consequence of my work is that such an expert is no longer needed: from a formal description of the semantics of a target machine, I can *generate* a translator that chooses target-machine instructions. Generating translators for such machines as x86, PowerPC, and ARM takes just minutes. These results rest on three technical contributions:

- I proved that the problem is undecidable in general, so any attack must involve heuristic search. - I developed a new search algorithm that, unlike prior work, explores *only* computations that can be implemented on the target machine. - I developed a new pruning heuristic that enables my algorithm to explore long sequences of instructions without allowing search times to explode.