search for: superoptimizer

Displaying 20 results from an estimated 42 matches for "superoptimizer".

2011 Apr 06
7
[LLVMdev] GSoC 2011: Superoptimization for LLVM IR
...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...
2009 Dec 14
1
[LLVMdev] project idea: llvm superoptimizer
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...
2011 Apr 07
0
[LLVMdev] GSoC 2011: Superoptimization for LLVM IR
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...
2011 Apr 08
0
[LLVMdev] GSoC 2011: Superoptimization for LLVM IR
...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...
2011 Apr 07
2
[LLVMdev] GSoC 2011: Superoptimization for LLVM IR
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...
2015 Jul 22
8
[LLVMdev] some superoptimizer results
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...
2015 Jul 24
0
[LLVMdev] some superoptimizer results
> 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
2015 Jul 22
2
[LLVMdev] some superoptimizer results
...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...
2015 Jul 24
2
[LLVMdev] some superoptimizer results
...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...
2011 Apr 08
0
[LLVMdev] GSoC 2011: Superoptimization for LLVM IR
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 >...
2015 Jul 23
0
[LLVMdev] some superoptimizer results
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
2014 Nov 24
2
[LLVMdev] new set of superoptimizer results
I hope there's some useful material in here! http://blog.regehr.org/archives/1192 John
2014 Nov 26
2
[LLVMdev] new set of superoptimizer results
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: > >
2015 Jul 22
3
[LLVMdev] some superoptimizer results
...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...
2015 Jul 23
0
[LLVMdev] some superoptimizer results
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
2015 Jul 23
0
[LLVMdev] some superoptimizer results
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
2012 Jun 20
0
[LLVMdev] Work in your project
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...
2015 Jul 23
3
[LLVMdev] some superoptimizer results
> 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
2015 Jul 23
3
[LLVMdev] some superoptimizer results
> 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
2015 Jul 23
0
[LLVMdev] some superoptimizer results
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