search for: souper

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

...e 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 LLVM using Souper and then use that LLVM to build SPEC CPU > 2006, here are optimizations ranked by dynamic profile count: > > http://blog.regehr.org/extra_files/souper-nov-14/bydprofile.html > > In other wo...

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

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

...d: 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 preferences become skewed too far in the other direction. How about for the next run I give everything (except maybe div/rem) cost 1? Then the only thing Souper will tell us about is when it can eliminate instructions, whic...

...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 preferences > become skewed too far in the other direction. > Interesting. Do you happen to have some examples laying around? > > How about for the next run I give everything (except maybe div/rem) cost 1? T...

...do that? > > Michael > > > 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 LLVM using Souper and then use that LLVM to build SPEC >> CPU 2006, here are optimizations ranked by dynamic profile count: >> >> http://blog.regehr.org/extra_files/souper-nov-14/bydprofile.html &...

...e 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 something about this but I don't have it handy. John %0:i32 = var %1:i32 = lshr %0, 1:i32 %2:i32 = addnw 1:i32, %1 infer %2 known from Souper: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx known from compiler: 0xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx llvm is stronger %0:i32 = var (000000000000000xxxxxxxxxxxxxxxxx) %1:i32 = and 65535:i32, %0 %2:i16 = var %3:i32 = zext %2 %4:i32 = mulnw %1, %3 infer %4 known from Souper: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

...am contains no UB and the emitted code returns a poison value. Either there has been a miscompilation or else the LLVM documentation should be changed to make it clear that the select instruction only has a value dependence on the value that is selected. The immediate problem here is that both Souper and Alive are happy for foo() to return 0 instead of 1. Souper actually does this optimization -- legally, of course, according to the reference manual. Anyway this issue seemed tricky enough to bring up here instead of just filing a PR. Thanks, John

...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 > preferences become skewed too far in the other direction. > > How about for the next run I give everything (except maybe div/rem) > cost 1? Then the only thing Souper will tell us about is when it can >...

...gt; -- Sean Silva > > > > > > > > > > On Wed, Jul 22, 2015 at 10:15 AM, John Regehr < > regehr at cs.utah.edu <mailto:regehr at cs.utah.edu> > > > wrote: > > > > > > 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 > <https://urldefense.proofpoint.com/v2/url?u=http-3A__blog.regehr.org_extra-5Ffiles_souper-2Djul-2D15.html&d=AwMFaQ...

...ute in 2 cycles while the > latter takes 3. Modern OoO chips do in fact exploit this kind of > thing. > > > -- Sean Silva > > > > > On Wed, Jul 22, 2015 at 10:15 AM, John Regehr < regehr at cs.utah.edu > > wrote: > > > 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 ar...

> 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

...f z3 in debian is very ancient: > https://tracker.debian.org/pkg/z3 4.4.1-0.4 > > LLVM needs 4.7 or something. > There is a bug report: > https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=909494 > > This also affects other LLVM-"affiliated" projects, like alive and souper. > > > Kind regards, > > -- > > Paulo Matos > Roman. > > > _______________________________________________ > > cfe-dev mailing list > > cfe-dev at lists.llvm.org > > https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev > _____________________...

Hello all, I've seen some discussion that InstCombine is "too general" and that llvm should implement a proper graph rewrite mechanism: Link to llvm-dev discussion about this: http://lists.llvm.org/pipermail/llvm-dev/2017-May/113219.html, Link to review where this came up (and I first heard about it): https://reviews.llvm.org/D37195. I wanted to understand what the current issues

...lists.llvm.org> wrote: > Equality saturation is very cool work and Ross Tate mentioned to me that > he'd be happy to chat with you about this. > > But also, you might take a look at some existing projects in this > general space that are already integrated with LLVM, such as Souper and > Alive. > > InstCombine is pretty cool but developing techniques to build these > things automatically is awesome and on my wish list. There's potential > for improvements in all of: speed, code quality, and correctness. > > While we're on the subject: Are the cano...

...cal path length is more important > than eliminating instructions. The critical path length is a target-independent lower bound on the > maximum achievable execution speed; the number of instructions is not. Sounds easy enough. I'll give it a try. I've observed many situations where Souper can shorten the critical path but I hadn't really thought about making that into a top-level goal. Thanks, John

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

> 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

...rg/gmane.comp.compilers.llvm.devel/88488) for the 2015 LLVM Developers' meeting has now gone out. The submission deadline is August 20th. Registration is also [now open](https://www.eventbrite.com/e/2015-llvm-developers-meeting-tickets-17756357744). John Regehr and his collaborators working on Souper have [shared some initial results from the synthesizing superoptimizer](http://blog.regehr.org/archives/1252). John is very interested in collecting representative IR from frontends other than Clang. There is also some discussion about these results [on the mailing list](http://article.gmane.org/gm...