search for: superoptimizers

...g it for optimization purposes, I use this to automatically generate a LLVM backend based on a machine description using the ArchC architecture description lan- guage. The backend patterns are fixed and the implementation of the pattern is inferred using a search algorithm similar to the one used on superoptimizers. Thus, I have experience both on superoptimizer theory and LLVM code. References [1] Sorav Bansal and Alex Aiken. Automatic generation of peephole superopti- mizers. SIGPLAN Not., 41:394–403, October 2006. [2] Henry Massalin. Superoptimizer: a look at the smallest program. In ASPLOS-II: Proceed...

...tricks would be missed. The outcome would be a new LLVM pass that subsumes at least the instruction combiner, and probably a few other passes as well. Benefits would include not missing cases missed by the current combiner and also more easily adapting to changes in the LLVM IR. All previous superoptimizers have worked on linear sequences of code. It would seem much better to operate on small subgraphs of the program dependency graph. I haven't worked out the details... John Regehr

A bit of feedback on this proposal: It worries me that you talk about "extending the number of transformations." The point of a superoptimizer is that it has no specific model of transformations. Rather, it is simply looking for cheap code fragments that are equivalent to expensive ones. You have not specified how you will perform equivalence checking between code sequences. The

IMO super optimizer would yield less benefits on LLVM compared to other compilers. If you check the patch of the instcombine pass, you'll find out people keep dragging "correct" optimization out, not because the optimization violates the semantic of LLVM IR, but it will generate wrong code sequences when lowering to machine code. An example: %3 = fcmp %1, %2 %6 = fcmp %4, %5 %7 =

Hello all, thanks for the feedback! It sounds like you are planning to follow the approach of Joshi, Nelson and > Randall ("Denali: A Goal-directed Superoptimizer") in that you don't intend > to exhaustively enumerate all possible code sequences, and see if they are > the same as the original only better; but instead start from the original > code > sequence and

We (the folks working on Souper) would appreciate any feedback on these IR-level superoptimizer results: http://blog.regehr.org/extra_files/souper-jul-15.html My impression is that while there's clearly plenty of material in here that doesn't want to get implemented in an opt pass, there are a number of gems hiding in there that are worth implementing. Blog post containing

> example (x+y)-x -> y. Here the right-hand side "y" is a particularly simple > subexpression of the original :) Yeah. We have not found a lot of this kind of thing-- it looks like you and others scooped up a lot of the low-hanging fruit! John

One thing that is important to consider is where in the pipeline these kinds of optimizations fit. We normally try to put the IR into a canonical simplified form in the mid-level optimizer. This form is supposed to be whatever is most useful for exposing other optimizations, and for lowering, but only in a generic sense. We do have some optimizations near the end of our pipeline (vectorization,

Hi, On 23/07/15 19:11, Philip Reames wrote: > > > On 07/23/2015 07:24 AM, John Regehr wrote: >>> I guess another way to select interesting transformations could be to look >>> for sequences where the >>> result uses a "subset" of the input instruction sequence. >> >> Yeah, I had been noticing those subsets too. It sounds like it's

Hi Rafael, don't forget to submit your proposal to GSOC (via the GSOC web-page) - the deadline is today! > > It sounds like you are planning to follow the approach of Joshi, Nelson and > Randall ("Denali: A Goal-directed Superoptimizer") in that you don't intend > to exhaustively enumerate all possible code sequences, and see if they are > the same

On Wed, Jul 22, 2015 at 9:27 PM, John Regehr <regehr at cs.utah.edu> wrote: > I just noticed: most of the results in this batch seem to be about >> exploiting `[zs]ext i1` having cost 1 >> in order to replace a select of cost 3. >> Could you do a run where select has cost 1 and [zs]ext i1 (and trunc to >> i1) has cost 2 or 3? >> > > I tried this (or

I hope there's some useful material in here! http://blog.regehr.org/archives/1192 John

I strongly suspect pointer union and pointer int pair style classes are the source of these... But perhaps I'm wrong On Nov 26, 2014 9:29 AM, "Michael Zolotukhin" <mzolotukhin at apple.com> wrote: > John, > > That’s a great post and really interesting data, thank you! > > On Nov 25, 2014, at 9:58 AM, Reid Kleckner <rnk at google.com> wrote: > >

On 07/22/2015 01:28 PM, Sean Silva wrote: > > > On Wed, Jul 22, 2015 at 12:54 PM, Hal Finkel <hfinkel at anl.gov > <mailto:hfinkel at anl.gov>> wrote: > > One thing that is important to consider is where in the pipeline > these kinds of optimizations fit. We normally try to put the IR > into a canonical simplified form in the mid-level optimizer.

On Wed, Jul 22, 2015 at 11:33 PM, John Regehr <regehr at cs.utah.edu> wrote: > Interesting. Do you happen to have some examples laying around? >> > > Sorry, no, I'll have to re-run. I felt that the select-heavy results were > sort of humorous and clever at first, but then just annoying. > > Except for decode-limited situations, in general decreasing the critical

On 07/23/2015 07:24 AM, John Regehr wrote: >> I guess another way to select interesting transformations could be to >> look for sequences where the >> result uses a "subset" of the input instruction sequence. > > Yeah, I had been noticing those subsets too. It sounds like it's > worth a try doing a run that looks only for those. > > One nice thing

Hi Guys, I checked the open projects on LLVM site, and superoptimizer theme seems to be quite interesting for me. So im going to write the LLVM superoptimizer (http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf) :) Is this theme still actual? Could you please advise me some usefull articles? -- Best regards, Sergey 2012/5/26 Serg Anohovsky <serg.anohovsky at gmail.com>: >

> I guess another way to select interesting transformations could be to look for sequences where the > result uses a "subset" of the input instruction sequence. Yeah, I had been noticing those subsets too. It sounds like it's worth a try doing a run that looks only for those. One nice thing is that if we're just looking for subsets, we will not even give the

> Interesting. Do you happen to have some examples laying around? Sorry, no, I'll have to re-run. I felt that the select-heavy results were sort of humorous and clever at first, but then just annoying. > Except for decode-limited situations, in general decreasing the critical path length is more important > than eliminating instructions. The critical path length is a

On 07/22/2015 09:27 PM, John Regehr wrote: >> I just noticed: most of the results in this batch seem to be about >> exploiting `[zs]ext i1` having cost 1 >> in order to replace a select of cost 3. >> Could you do a run where select has cost 1 and [zs]ext i1 (and trunc >> to i1) has cost 2 or 3? > > I tried this (or something quite similar) earlier and it