I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex. But it will also be interesting to know about the latest inventions in the field of peephole optimizations.
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ In my thesis (slides) I have discussed and implemented call-graph flattening in LLVM; basically it's an interprocedural transformation that gets rid of the notion of "function" because it merges all code together, allowing a bunch of interesting possibilities such as interprocedural code motion, callsite-optimized calling conventions, stackless execution and so on. $\endgroup$– CAFxXDec 1, 2011 at 21:16
-
$\begingroup$ @CAFxX: slides crashed Open Office .. do you happen to have online pictures instead? $\endgroup$– YttrillJan 5, 2012 at 16:07
-
$\begingroup$ @Yttrill: slideshare.net/CAFxX/… $\endgroup$– CAFxXJan 5, 2012 at 17:48
-
$\begingroup$ Thanks, able to view with that, although the graphs were to fine to be visible the text was good. $\endgroup$– YttrillJan 9, 2012 at 14:10
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
I'm not sure how novel it is, or if it's too much on the applied side for your interest, but Hoopl shows how a control/data flow optimization can be modularised, with propagation of facts about control-graph vertices being independent of the language and specific optimization.
They reference a 2002 algorithm of Lerner, Grove and Chambers which composes simple optimizations into a "superoptimization".
$\begingroup$
$\endgroup$
1
I suppose the Equality Saturation technique, as a different approach to the problem of optimization passes ordering, would be relevant. To my knowledge, it has however not yet been proved practical by a concrete implementation in a full-fledged compiler. The following Generating Compiler Optimizations from Proofs may also be of interest.
-
1
$\begingroup$
$\endgroup$
1
There has been a bit of a revival in verified optimizing compilers. In addition to Lerner's paper (mentioned in a previous comment), you might look at the CompCert project led by Xavier Leroy. They've done some cool stuff with specifying optimizations as machine-checkable proofs (using Coq). I haven't yet read the papers, but The Verified Software Toolchain project at Princeton also seems to be producing interesting results in this area.
-
1$\begingroup$ We are also working on a project similar to CompCert: CerCo (cerco.cs.unibo.it). Unlike CompCert, we aim to produce a verified concrete cost preserving compiler for a large subset of C (CompCert only shows that extensional properties of the source program are preserved by compilation). We are also implementing in the compiler a few moderately complex loop optimizations, as well as "mild" optimizations like CompCert employs, which will of course need verifying as being cost-preserving. $\endgroup$ Dec 1, 2011 at 17:21
$\begingroup$
$\endgroup$
Recognizing that baz[i] += force(foo[i],foo[j]) in a double FOR loop has independent results for (i,j) and reordering the calls into a space filling curve on (i,j) to cut down on cache misses.
Not quite "peephole" but getting cache oblivious behavior for "free" is nice.
