similar to: [LLVMdev] some superoptimizer results

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,

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.

Cool! Looks like we do lots of provably unnecessary alignment checks. :) On Tue, Nov 25, 2014 at 9:03 AM, John Regehr <regehr at cs.utah.edu> wrote: > Actually, let me save you some time by pointing out the thing that is > perhaps immediately useful about our recent work, which is the fact that > Souper now supports "optimization profiling". > > If you build an

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

> 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 caused Souper to introduce *a lot* of selects. So the problem is that Souper's

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

While looking at optimizations where Souper exploits known bits, I realized that it would be easy to teach Souper to compute known bits. Comparing its results against computeKnownBits() from r246393, it looks like there are some easy (and some not-easy) opportunities for improvement, please see a few examples below. The expressions come from compiling LLVM itself. Happily, this exercise

> 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

> 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

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

In the section about poison values, the LLVM language reference manual says: "Values other than phi nodes depend on their operands." This implies that a select instruction's output can be poisoned by its not-selected argument value. If select were poisoned only by its selected argument, we would expect this fact to be mentioned specifically, as it is for phi. Next I'll

> Poison is a flawed concept. I proved it was flawed back in 2011 [0] Nice. My colleagues and I will dig through this material and possibly come back with some ideas. We're going to need some sort of semantics for UB in LLVM since otherwise these formal-methods-based tools like Souper and Alive risk not making sense. Thanks, John

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

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 the subject of undefined behavior and known bits, as I'm sure some of you are aware, code in ValueTracking.cpp is exploiting poison value rules to get a bit of extra precision in the known bits. These rules fire on examples like the ones below. Do we have a set of rules that clients of known bits need to follow to avoid unsoundness? I remember Nuno and/or David Majnemer saying

> 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

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

As you all have undoubtedly noticed, I recently did Yet Another Merge to Apple's GCC top-of-tree. This merge was prompted by several important fixes in the "blocks" implementation. There are still many testcases that need to be moved over, but those can come at our leisure. I compiled both the "Apple way" and the "FSF way". It also passed the tests in