Re: [fonc] Compiler Passes
On Sun, Apr 14, 2013 at 04:20:41PM -0700, David Barbour wrote:
(Forwarded from Layers thread)
On Sun, Apr 14, 2013 at 1:44 PM, Gath-Gealaich
[1]gath.na.geala...@gmail.com wrote:
Isn't one of the points of idst/COLA/Frank/whatever-it-is-called-today
to simplify the development of domain-specific models to such an extent
that their casual application becomes conceivable, and indeed even
practical, as opposed to designing a new one-size-fits-all language
every decade or so?
I had another idea the other day that could profit from a
domain-specific model: a model for compiler passes. I stumbled upon the
nanopass approach [1] to compiler construction some time ago and found
that I like it. Then it occurred to me that if one could express the
passes in some sort of a domain-specific language, the total compilation
pipeline could be assembled from the individual passes in a much more
efficient way that would be the case if the passes were written in
something like C++.
I do that at amethyst. I extended ometa to support dataflow analysis and
match arbitrary objects. Then I use optimizations to optimize amethyst
like in compiler.
You will better when you abandon concept of pass. You have
transformations and conditions when you can done them. Idealy all of
them simplify code (according to some metric like size of binary) and you want
to apply them until none is possible.
Theoretists call this term rewriting system.
Here biggest problem is determining profitability of transformation. Well
gcc uses ordering that looks empiricaly as fastest.
This idea is nothing new, similar idea is here.
cseweb.ucsd.edu/~lerner/UW-CSE-01-11-01.pdf
I did not seek if this paper is used in practice.
You need to split transformations when you start getting cycles. Typical
example of this is CSE.
In order to do that, however, no matter what the intermediate values in
the pipeline would be (trees? annotated graphs?), the individual passes
would have to be analyzable in some way. For example, two passes may or
Why do you need that?
may not interfere with each other, and therefore may or may not be
commutative, associative, and/or fusable (in the same respect that, say,
Haskell maps over lists are fusable). I can't imagine that C++ code
would be analyzable in this way, unless one were to use some severely
restricted subset of C++ code. It would be ugly anyway.
Composing the passes by fusing the traversals and transformations would
decrease the number of memory accesses, speed up the compilation
process, and encourage the compiler writer to write more fine-grained
I tried that, does not work. When fusing you trasform memory access to random
access
which is slower. At gcc lot of effort is placed to cut off pass when it
starts produce reasonable results. This is hard to determine with
fusion.
A real reason of doing that combination of two analysis is stronger than
any sequential combination of them. Canonical example are optimizations X,Y
where X knows that A(0) is true and Y knows that B(y) is true. then
simplify following:
x=0
y=0
while (1){
if (A(x))
y=1;
if (B(y))
x=1;
}
passes, in the same sense that deep inlining in modern language
implementations encourages the programmer to write small and reusable
routines, even higher-order ones, without severe performance penalties.
Lowering the barrier to implementing such a problem-specific language
seems to make such an approach viable, perhaps even desirable, given how
convoluted most production compilers seem to be.
(If I've just written something that amounts to complete gibberish,
please shoot me. I just felt like writing down an idea that occurred to
me recently and bouncing it off somebody.)
- Gath
[1] Kent Dybvig, A nanopass framework for compiler education (2005),
[2]http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5578
___
fonc mailing list
[3]fonc@vpri.org
[4]http://vpri.org/mailman/listinfo/fonc
References
Visible links
1. mailto:gath.na.geala...@gmail.com
2. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5578
3. mailto:fonc@vpri.org
4. http://vpri.org/mailman/listinfo/fonc
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc
[fonc] Compiler Passes
(Forwarded from Layers thread) On Sun, Apr 14, 2013 at 1:44 PM, Gath-Gealaich gath.na.geala...@gmail.comwrote: Isn't one of the points of idst/COLA/Frank/whatever-it-is-called-today to simplify the development of domain-specific models to such an extent that their casual application becomes conceivable, and indeed even practical, as opposed to designing a new one-size-fits-all language every decade or so? I had another idea the other day that could profit from a domain-specific model: a model for compiler passes. I stumbled upon the nanopass approach [1] to compiler construction some time ago and found that I like it. Then it occurred to me that if one could express the passes in some sort of a domain-specific language, the total compilation pipeline could be assembled from the individual passes in a much more efficient way that would be the case if the passes were written in something like C++. In order to do that, however, no matter what the intermediate values in the pipeline would be (trees? annotated graphs?), the individual passes would have to be analyzable in some way. For example, two passes may or may not interfere with each other, and therefore may or may not be commutative, associative, and/or fusable (in the same respect that, say, Haskell maps over lists are fusable). I can't imagine that C++ code would be analyzable in this way, unless one were to use some severely restricted subset of C++ code. It would be ugly anyway. Composing the passes by fusing the traversals and transformations would decrease the number of memory accesses, speed up the compilation process, and encourage the compiler writer to write more fine-grained passes, in the same sense that deep inlining in modern language implementations encourages the programmer to write small and reusable routines, even higher-order ones, without severe performance penalties. Lowering the barrier to implementing such a problem-specific language seems to make such an approach viable, perhaps even desirable, given how convoluted most production compilers seem to be. (If I've just written something that amounts to complete gibberish, please shoot me. I just felt like writing down an idea that occurred to me recently and bouncing it off somebody.) - Gath [1] Kent Dybvig, A nanopass framework for compiler education (2005), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.72.5578 ___ fonc mailing list fonc@vpri.org http://vpri.org/mailman/listinfo/fonc ___ fonc mailing list fonc@vpri.org http://vpri.org/mailman/listinfo/fonc
Re: [fonc] Compiler Passes
Looking at some of the links associated with the paper A nanopass framework ... you find: http://www.cs.indiana.edu/eip/compile/ which may answer your question and help those looking at Maru. david On Sun, Apr 14, 2013 at 5:35 PM, David Barbour dmbarb...@gmail.com wrote: Do you have a list of the common 'kinds' of passes? Because any domain specific model be optimizing only conjunctions of only a few kinds. On Sun, Apr 14, 2013 at 1:44 PM, Gath-Gealaich gath.na.geala...@gmail.com wrote: I had another idea the other day that could profit from a domain-specific model: a model for compiler passes. I stumbled upon the nanopass approach [1] to compiler construction some time ago and found that I like it. Then it occurred to me that if one could express the passes in some sort of a domain-specific language, the total compilation pipeline could be assembled from the individual passes in a much more efficient way that would be the case if the passes were written in something like C++. In order to do that, however, no matter what the intermediate values in the pipeline would be (trees? annotated graphs?), the individual passes would have to be analyzable in some way. For example, two passes may or may not interfere with each other, and therefore may or may not be commutative, associative, and/or fusable (in the same respect that, say, Haskell maps over lists are fusable). I can't imagine that C++ code would be analyzable in this way, unless one were to use some severely restricted subset of C++ code. It would be ugly anyway. Composing the passes by fusing the traversals and transformations would decrease the number of memory accesses, speed up the compilation process, and encourage the compiler writer to write more fine-grained passes, in the same sense that deep inlining in modern language implementations encourages the programmer to write small and reusable routines, even higher-order ones, without severe performance penalties. Lowering the barrier to implementing such a problem-specific language seems to make such an approach viable, perhaps even desirable, given how convoluted most production compilers seem to be. ___ fonc mailing list fonc@vpri.org http://vpri.org/mailman/listinfo/fonc ___ fonc mailing list fonc@vpri.org http://vpri.org/mailman/listinfo/fonc
