Subject: DSLs for optimizations
From: Sorin Lerner (lerns@cs.washington.edu)
Date: Tue Mar 13 2001 - 23:41:59 PST
Here's an outline of the topics that I want to discuss regarding DSLs
for optimizations. Please look at it before coming to the meeting on
Thursday so that we can have a meaningful discussion. Also, if there is
a topic that you would like to see covered which is not on the list,
please let me know.
Sorin
Topic: What would a Domain Specific Language for optimizations allow
us to do?
(*) indicates a topic that I beleive would be a significant contribution.
1) Improvements from compiler writer's perspective
1.1) Ease of writing analyses
Problem: what about debugging? This is especially important if
the language is very abstract.
1.2) Better tools
We can have tools for processing optimizations, such as:
Optimization transformers: transform one optimization into
another. For example, I have an optimization that runs over the
CFG & DFG, and I want to transform into an optimization that
runs over the PDG & DFG.
Optimization generators (wishful thinking...): generate
optimizations from scratch. For example, given a few
transformation examples, the optimization generator could
somehow search the space of optimizations until it finds a
correct one (assuming we can automatically prove optimizations
correct) that matches the sample transformations.
1.3) Verifiability (*)
Termination (finite lattice & monotonic flow functions)
Correctness
Is this feasible? What is required to prove correctness? At
the very least we need the concrete semantics and the
abstraction function. Anything else? How much work is
required on the programmer side?
Issue: level of abstraction of the language. Higher level of
abstraction (eg: model checking, or a language that specifies
path properties) will help us prove things, but might make
writing analyses harder.
2) Improvements from user's perspective
2.1) Extensible compilers
Compilers are hard to modify, so if you're not happy with the
generated code, there's not much you can do. However, if we can
make optimizations short and easy to write, users can add their
own optimizations.
This might also subsume Metal [Engler et. al. 2001]. Metal is a
domain specific language for defining analyses that check
program properties (eg: that a variable is always defined before
used, that return values from system calls are checked for error
codes, that interrupts are always reenabled at the end of an
ISR, etc.)
2.2) Improving compiler speed
Common computation elimination: Identify computations that are
common to several optimizations, and do these computations only
once when the analyses are composed. Craig has an example where
this would have helped some Vortex analyses.
Also, can we use the data dependence information to parallelize the
compiler?
2.3) Improving quality of generated code (*)
Optimization ordering: Can compute data dependences among
analyses, and figure out what order they should be run in order
to provide best results.
[1] Dawson Engler, Benjamin Chelf, Andy Chou and Seth Hallem. Checking
Systems Rules Using System-specific, Programmer-Written Compiler
Extensions. OSDI 2000, San Diego CA.
_______________________________________________
Cecil mailing list
Cecil@cs.washington.edu
http://majordomo.cs.washington.edu/mailman/listinfo/cecil
This archive was generated by hypermail 2b25 : Tue Mar 13 2001 - 23:42:06 PST