search for: superoptimizer

...roblem and became known in literature as superoptimization, term coined by Massalin [2]. Using computer-aided optimization discovery, different kind of optimizations unnoticed by humans may be detected, specially those specific to the target machine code [1]. This project will focus on implementing a superoptimizer which will exhaustively investigate new optimizations for the LLVM IR. Using this approach, I hope to greatly contribute to the current LLVM instruction simplify phase, introducing new substitutions identified in this project. Methodology There is already a superoptimizer for LLVM in initial stag...

Here's an idea for a research project that I thought I'd put out there since probably nobody in my group will have time to follow up on it. It would be interesting to take ideas from this superoptimizer for x86: http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf http://theory.stanford.edu/~sbansal/superoptimizer.html and adapt them to run on LLVM code. It would seem that operating on LLVM code would save a lot of time because its semantics are much simpler than x86. The...

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 best answer that I know of is to use the technique fr...

...orem provers. Haohui On Thu, Apr 7, 2011 at 5:03 PM, Rafael Auler <rafaelauler at gmail.com> wrote: > 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 repeatedly apply transformations that change code t...

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 repeatedly apply transformations that change code to > equivalent > co...

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 add...

> 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

...lowering afterward. -Hal ----- Original Message ----- > From: "Sean Silva" <chisophugis at gmail.com> > To: "John Regehr" <regehr at cs.utah.edu> > Cc: llvmdev at cs.uiuc.edu > Sent: Wednesday, July 22, 2015 2:35:51 PM > Subject: Re: [LLVMdev] some superoptimizer results > > > > Are you taking into account critical path length? Because e.g. for: > > > > %0:i64 = var > %1:i1 = slt 18446744073709551615:i64, %0 > %2:i64 = subnsw 0:i64, %0 > %3:i64 = select %1, %0, %2 > infer %3 > %4:i64 = ashr %0, 63:i64 > %5:i64...

...make synthesis more >> likely to succeed (assuming that an optimization exists within the subset). > +1 - This sounds like a very interesting approach. I suspect it might also find > cases which are easier to hand generalize, but that's just a guess. this sounds like what my LLVM superoptimizer did: simplified expressions to subexpressions that were already present in the original expression, for example (x+y)-x -> y. Here the right-hand side "y" is a particularly simple subexpression of the original :) One big advantage is that you can process expressions very fast, typ...

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 as the original only better; but instead start from the original code > sequence and repeatedly apply transformations that change code to equivalent >...

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: > >

...l.com>> > > To: "John Regehr" <regehr at cs.utah.edu <mailto:regehr at cs.utah.edu>> > > Cc: llvmdev at cs.uiuc.edu <mailto:llvmdev at cs.uiuc.edu> > > Sent: Wednesday, July 22, 2015 2:35:51 PM > > Subject: Re: [LLVMdev] some superoptimizer results > > > > > > > > Are you taking into account critical path length? Because e.g. for: > > > > > > > > %0:i64 = var > > %1:i1 = slt 18446744073709551615:i64, %0 > > %2:i64 = subnsw 0:i64, %0 &gt...

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.a...

> 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