Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Design and implementation of an optimizing type-centric compiler for a high-level language
 
doctoral thesis

Design and implementation of an optimizing type-centric compiler for a high-level language

Petrashko, Dmytro  
2017

Production compilers for programming languages face multiple requirements. They should be correct, as we rely on them to produce code. They should be fast, in order to provide a good developer experience. They should also be easy to maintain and evolve. This thesis shows how an expressive high level type system can be used to simplify the development of a compiler and demonstrates this on a compiler for Scala. First, it shows how expressive types of high level languages can be used to build internal data structures that provide a statically checked API, ensuring that important properties hold at compile time. Second, we also show how high level language features can be used to abstract the components of a compiler. We demonstrate this by introducing a type-safe layer on top of the bytecode emission phase. This makes it possible to abstract away the implementation details of the compiler frontend and run the same bytecode emission phase in two different Scala compilers. Third, it presents MiniPhases, a novel way to organize transformation passes in a compiler. MiniPhases impose constraints on the organization of passes that are beneficial for maintainability, performance, and testability. We include a detailed performance evaluation of MiniPhases which indicates that their speedup is due to improved cache friendliness and to a lower rate of promotions of objects into the old generations of garbage collectors. Finally, we demonstrate how the expressive type system of the language being compiled can be used for static analysis. We present a novel call graph construction algorithm which uses the typing context for context sensitivity. The resulting algorithm is both substantially faster and more precise than existing alternatives. We demonstrate the applicability of this analysis by extending common subexpression elimination to idempotent expression elimination.

  • Files
  • Details
  • Metrics
Type
doctoral thesis
DOI
10.5075/epfl-thesis-7979
Author(s)
Petrashko, Dmytro  
Advisors
Odersky, Martin  
Jury

Prof. Michael Christoph Gastpar (président) ; Prof. Martin Odersky (directeur de thèse) ; Prof. Viktor Kuncak, Prof. O. Lhoták, Dr Cliff Click (rapporteurs)

Date Issued

2017

Publisher

EPFL

Publisher place

Lausanne

Public defense year

2017-12-11

Thesis number

7979

Total of pages

183

Subjects

compiler design

•

optimizing compiler

•

compiler performance

•

tree traversal fusion

•

cache locality

•

call graphs

•

parametric polymorphism

•

static analysis

•

Scala

EPFL units
LAMP1  
Faculty
IC  
School
IINFCOM  
Doctoral School
EDIC  
Available on Infoscience
December 4, 2017
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/142464
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés