Sanjay Patel via llvm-dev
2017-Jul-13 23:37 UTC
[llvm-dev] failing to optimize boolean ops on cmps
This can't be an instsimplify though? The values we want in these cases do not exist already: %res = or i8 %b, %a %res = or i1 %cmp, %c On Thu, Jul 13, 2017 at 5:10 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> > > On Thu, Jul 13, 2017 at 2:12 PM, Sanjay Patel <spatel at rotateright.com> > wrote: > >> We have several optimizations in InstCombine for bitwise logic ops >> (and/or/xor) that fail to handle compare patterns with the equivalent >> bitwise logic. Example: >> >> define i8 @or_and_not(i8 %a, i8 %b) { >> %nota = xor i8 %a, -1 >> %and = and i8 %nota, %b >> %res = or i8 %and, %a >> ret i8 %res >> } >> >> define i1 @or_and_cmp_not(i32 %a, i32 %b, i1 %c) { >> %cmp = icmp sgt i32 %a, %b >> %cmp_inv = icmp sle i32 %a, %b ; this is 'not' of %cmp >> %and = and i1 %c, %cmp_inv >> %res = or i1 %cmp, %and >> ret i1 %res >> } >> >> $ ./opt -instcombine hidden_not.ll -S >> >> define i8 @or_and_not(i8 %a, i8 %b) { >> %res = or i8 %b, %a >> ret i8 %res >> } >> >> define i1 @or_and_cmp_not(i32 %a, i32 %b, i1 %c) { >> %cmp = icmp sgt i32 %a, %b >> %cmp_inv = icmp sle i32 %a, %b >> %and = and i1 %cmp_inv, %c >> %res = or i1 %cmp, %and >> ret i1 %res >> } >> >> --------------------------------------------------------------------- >> >> Would adding to the existing InstCombine logic folds to handle this kind >> of pattern be a welcome enhancement? I don't know if it's possible to make >> the matchers handle this case without adding a new matcher. Eg: >> >> > I would rather see this added to instsimplify than instcombine. > If you do that, GVN/et all will get this already. > > This probably does require a special matcher though: > > > We have: > if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), > m_Cmp(Pred, m_Value(), m_Value())) > > and you really want: > if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), > m_Cmp(m_Opposite(Pred), m_Value(), m_Value())) > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170713/6108341b/attachment.html>
Daniel Berlin via llvm-dev
2017-Jul-13 23:40 UTC
[llvm-dev] failing to optimize boolean ops on cmps
Ah yes, it can only return one instruction and you need two. NewGVN could still handle it if instsimplify was changed to return the right binary operators because it has infrastructure that can handle insertion. (it would need a little work). (At this point, InstCombine seems to have become worse to me than GCC's combining infrastructure, so i'd really like to see if we can stop putting things there. Otherwise, we just go farther down the path of 'let's just make everything one big graph rewrite) On Thu, Jul 13, 2017 at 4:37 PM, Sanjay Patel <spatel at rotateright.com> wrote:> This can't be an instsimplify though? The values we want in these cases do > not exist already: > %res = or i8 %b, %a > %res = or i1 %cmp, %c > > > > On Thu, Jul 13, 2017 at 5:10 PM, Daniel Berlin <dberlin at dberlin.org> > wrote: > >> >> >> On Thu, Jul 13, 2017 at 2:12 PM, Sanjay Patel <spatel at rotateright.com> >> wrote: >> >>> We have several optimizations in InstCombine for bitwise logic ops >>> (and/or/xor) that fail to handle compare patterns with the equivalent >>> bitwise logic. Example: >>> >>> define i8 @or_and_not(i8 %a, i8 %b) { >>> %nota = xor i8 %a, -1 >>> %and = and i8 %nota, %b >>> %res = or i8 %and, %a >>> ret i8 %res >>> } >>> >>> define i1 @or_and_cmp_not(i32 %a, i32 %b, i1 %c) { >>> %cmp = icmp sgt i32 %a, %b >>> %cmp_inv = icmp sle i32 %a, %b ; this is 'not' of %cmp >>> %and = and i1 %c, %cmp_inv >>> %res = or i1 %cmp, %and >>> ret i1 %res >>> } >>> >>> $ ./opt -instcombine hidden_not.ll -S >>> >>> define i8 @or_and_not(i8 %a, i8 %b) { >>> %res = or i8 %b, %a >>> ret i8 %res >>> } >>> >>> define i1 @or_and_cmp_not(i32 %a, i32 %b, i1 %c) { >>> %cmp = icmp sgt i32 %a, %b >>> %cmp_inv = icmp sle i32 %a, %b >>> %and = and i1 %cmp_inv, %c >>> %res = or i1 %cmp, %and >>> ret i1 %res >>> } >>> >>> --------------------------------------------------------------------- >>> >>> Would adding to the existing InstCombine logic folds to handle this kind >>> of pattern be a welcome enhancement? I don't know if it's possible to make >>> the matchers handle this case without adding a new matcher. Eg: >>> >>> >> I would rather see this added to instsimplify than instcombine. >> If you do that, GVN/et all will get this already. >> >> This probably does require a special matcher though: >> >> >> We have: >> if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), >> m_Cmp(Pred, m_Value(), m_Value())) >> >> and you really want: >> if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), >> m_Cmp(m_Opposite(Pred), m_Value(), m_Value())) >> >> >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170713/4597f58d/attachment.html>
Hal Finkel via llvm-dev
2017-Jul-14 01:18 UTC
[llvm-dev] failing to optimize boolean ops on cmps
On 07/13/2017 06:40 PM, Daniel Berlin via llvm-dev wrote:> Ah yes, it can only return one instruction and you need two. > > NewGVN could still handle it if instsimplify was changed to return the > right binary operators because it has infrastructure that can handle > insertion. > (it would need a little work). > > > (At this point, InstCombine seems to have become worse to me than > GCC's combining infrastructure, so i'd really like to see if we can > stop putting things there. Otherwise, we just go farther down the path > of 'let's just make everything one big graph rewrite)Perhaps something of a digression: My general impression is that if InstCombine were actually doing a principled graph rewrite, then we wouldn't have these problems. The problem we have, however, is that we have phase-ordering problems (even within the fixed-point iteration scheme): Patterns being matched depend on a canonical form, instructions nearly matching those patterns might be created, and then suboptimally consumed (i.e. further transformed), before being subject to the canonicalizing transformation(s) that would make the better pattern actually match. Except for TableGen'ing the whole thing, and making an actual graph automaton to match the patterns, it's not clear to me how to efficiently fix this. In the mean time, what we've been doing in practice, is that we have InstCombine patterns depend on canonical forms, until we hit some phase-ordering problem, and then we extend the pattern in question to match some non-canonical forms. We might do this here as well (if that's the problem here), but at some point I suspect we'll end up redoing everything. -Hal> > > On Thu, Jul 13, 2017 at 4:37 PM, Sanjay Patel <spatel at rotateright.com > <mailto:spatel at rotateright.com>> wrote: > > This can't be an instsimplify though? The values we want in these > cases do not exist already: > %res = or i8 %b, %a > %res = or i1 %cmp, %c > > > > On Thu, Jul 13, 2017 at 5:10 PM, Daniel Berlin > <dberlin at dberlin.org <mailto:dberlin at dberlin.org>> wrote: > > > > On Thu, Jul 13, 2017 at 2:12 PM, Sanjay Patel > <spatel at rotateright.com <mailto:spatel at rotateright.com>> wrote: > > We have several optimizations in InstCombine for bitwise > logic ops (and/or/xor) that fail to handle compare > patterns with the equivalent bitwise logic. Example: > > define i8 @or_and_not(i8 %a, i8 %b) { > %nota = xor i8 %a, -1 > %and = and i8 %nota, %b > %res = or i8 %and, %a > ret i8 %res > } > > define i1 @or_and_cmp_not(i32 %a, i32 %b, i1 %c) { > %cmp = icmp sgt i32 %a, %b > %cmp_inv = icmp sle i32 %a, %b ; this is 'not' of %cmp > %and = and i1 %c, %cmp_inv > %res = or i1 %cmp, %and > ret i1 %res > } > > $ ./opt -instcombine hidden_not.ll -S > > define i8 @or_and_not(i8 %a, i8 %b) { > %res = or i8 %b, %a > ret i8 %res > } > > define i1 @or_and_cmp_not(i32 %a, i32 %b, i1 %c) { > %cmp = icmp sgt i32 %a, %b > %cmp_inv = icmp sle i32 %a, %b > %and = and i1 %cmp_inv, %c > %res = or i1 %cmp, %and > ret i1 %res > } > > --------------------------------------------------------------------- > > Would adding to the existing InstCombine logic folds to > handle this kind of pattern be a welcome enhancement? I > don't know if it's possible to make the matchers handle > this case without adding a new matcher. Eg: > > > I would rather see this added to instsimplify than instcombine. > If you do that, GVN/et all will get this already. > > This probably does require a special matcher though: > > > We have: > if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), > m_Cmp(Pred, m_Value(), m_Value())) > > and you really want: > if (m_c_And(m_Cmp(Pred, m_Value(), m_Value()), > m_Cmp(m_Opposite(Pred), m_Value(), m_Value())) > > > > > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170713/1b8326df/attachment-0001.html>