skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · thesis defenses · 2007-2008 · 

Thesis Defense - Von Dincklage

ECOT 831

Algorithmic Optimizations
Daniel Von Dincklage
Computer Science PhD Candidate

Compilers and programming environments use program analyses to determine the safety of code transformations. Unfortunately, these program analyses are often too conservative. As a result, the compiler or programming environment will consider many program transformations as unsound.

This especially affects aggressive or large-scale program transformations: As such transformations have more complex requirements for their soundness, they are affected disproportionately. In practice, this conservativeness causes almost any complex program analysis to be rejected.

One reason for this needless conservativeness of optimizations is that they attempt to preserve the entire semantics of the program as defined by the programming language, even if those semantics were never intended by the programmer. This limitation can be avoided if the user adds annotations to the program that specify his intended semantics. Such annotations will relax the semantics of the program and thereby cause program analyses to have better results. In turn, less code transformations will be rejected.

However, specifying the intended semantics is a tedious task: First, programs are large. To fully annotate all parts of it, a programmer will require a lot of time. Second, there are many annotations a programmer could place. To fully annotate even a single line of a program, a programmer has to specify numerous different properties. These two issues force the programmer to place many annotations that do not affect the intended transformations: A small subset of the intended semantics is sufficient to improve the results of most analyses. Specifying the entire intended semantics therefore is wasteful and not practical.

We present an approach that makes it feasible to specify the intended semantics of a program. Our system guides the user into specifying those parts of the intended semantics that aid the analyses results most. With the help of this guidance, a user can avoid providing specifications about the parts of the intended semantics that are irrelevant for the analyses, and thereby reduce the effort he needs to invest.

We use our system to apply large-scale and aggressive program optimizations. We call these optimizations algorithmic optimizations. Using a specification of the optimizations, our system determines why the optimizations fail to apply. It then identifies which failure causes are the most important ones and estimates the likelihood of whether the user will be able to affect each failure cause by specifying his intended semantics. Using this data as guidance, the user then can add specifications and subsequently apply the optimizations safely.

Committee: Amer Diwan, Associate Professor (Chair)
Kenneth Anderson, Associate Professor
Daniel Connors, Department of Electrical and Computer Engineering
Clayton Lewis, Professor
Manish Vachharajani, Department of Electrical and Computer Engineering

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:40)